如何防止 jointjs / rappid 中的循环

Question

我正在构建一个使用 jointjs / rappid 的应用程序，我希望能够避免跨多个单元格发生循环。

Jointjs 已经有一些关于如何在单个单元格中避免这种情况的示例（将 "out" 端口连接到同一单元格的 "in" 端口）但没有关于如何检测和防止链中进一步发生的循环。

为了帮助理解，将论文中的每个单元格想象成一个要完成的步骤。每一步都应该只运行一次。如果最后一步有一个 "out" 端口连接到第一个单元格的 "in" 端口，它将永远循环。这是我想避免的。

非常感谢任何帮助。

Answer 1

通过graphlib解决

基于, instead of findCycles to test for loops, the graphlib docs suggests to use the isAcyclic function，其中：

returns true if the graph has no cycles and returns false if it does. This algorithm returns as soon as it detects the first cycle.

因此这个条件：

if(graphlib.alg.findCycles(graph.toGraphLib()).length > 0)

可以缩短为：

if(!graphlib.alg.isAcyclic(graph))

JointJS函数解决方案

查找 ancestors and successors of a newly connected element and intersect 个数组：

// invoke inside an event which tests if a specific `connectedElement` is part of a loop

function isElementPartOfLoop (graph, connectedElement) {
  var elemSuccessors = graph.getSuccessors(connectedElement, {deep: true});

  var elemAncestors = connectedElement.getAncestors();
  //       *** OR *** graph.getPredecessors(connectedElement, {deep: true});

  var commonElements = _.intersection(elemSuccessors, elemAncestors);

  // if an element is repeated (non-empty intersection), then it's part of a loop
  return !_.isEmpty(commonElements);
}

我没有对此进行测试，但您尝试完成的测试背后的理论应该是相似的。此解决方案不如直接使用 graphlib 函数有效。

预防

防止将 link 添加到图表中的一种方法是在事件中处理它：

graph.on('add', _.bind(addCellOps, graph));

function addCellOps (cell, collection, opt) {
  if (cell.isLink()){
    // test link's target element: if it is part of a loop, remove the link
    var linkTarget = cell.getTargetElement();
    // `this` is the graph
    if(target && isElementPartOfLoop(this, linkTarget)){
      cell.remove();
    }
  }
  // other operations ....
}

Answer 2

我实际上找到了一个非常简单的方法来为任何希望实现同样目标的人做这件事。只需包含 graphlib 依赖项并使用以下内容：

        paper.on("link:connect", function(linkView) {
            if(graphlib.alg.findCycles(graph.toGraphLib()).length > 0) {
                linkView.model.remove();
                // show some error message here
            }
        });

这一行：

graphlib.alg.findCycles(graph.toGraphLib())

Returns 一个包含任何循环的数组，因此通过检查长度我们可以确定论文是否包含任何循环，如果是，则删除用户尝试的 link创造。

注意：这并不完全full-proof因为如果论文已经包含一个循环（在用户添加link之前）然后简单地删除用户正在创建的 link 不会删除任何存在的循环。对我来说这很好，因为我所有的论文都是从头开始创建的，所以只要这个逻辑始终存在，就永远不会创建循环。

如何防止 jointjs / rappid 中的循环

How to prevent loops in jointjs / rappid

jointjs

通过graphlib解决

JointJS函数解决方案

预防