JointJs 循环检测

Question

我正在尝试使用 JointJS 实现一种算法来检测有向图中的循环（仅出站连接）。我编写了以下代码，但未按预期执行。

        var _elements = graph.getElements();
        var visited = [];
        var level = 0;
        var isCycleExists;
        for (var i = 0; i < _elements.length; i++) {
            var elem = _elements[i];
            //only checking nodes which do have predecessors
            if ((graph.getPredecessors(elem).length > 0) && !elem.isLink()
                    && hasCycle(elem, visited, level)) {
                isCycleExists = true;
                break;
            }
        }

     function hasCycle(comp, visited, level) {
        var successors = graph.getSuccessors(comp);
        visited.push(comp.id);
        for (var i = 0; i < successors.length; i++) {
            var c = successors[i];
            var _successors = graph.getSuccessors(c);
            if (_successors.length == 0) {
                continue;
            }
            if (visited.indexOf(c.id) > -1) {
                return true;
            }
            visited.push(c.id);
            if (hasCycle(c, visited.slice(), ++level)) {
                return true;
            }
        }
        return false;
    }

如果有人能在这方面帮助我，那将非常有帮助。

Answer 1

问题是继任者与直接继任者不同。查看 graph.getSuccessors(comp) 值：如果库使用一致的函数名称，则第一个运行应包含 B、C、D 和 E。所以你标记那些访问过的，还有运行 hasCycle(c, visited.slice(), ++level) 你再次检查从 D 开始的节点（我猜 D 是第一个你得到 "already visited" 案例的节点）。

首先，我建议不要在你的函数中加倍迭代，像这样

 function hasCycle(comp, visited, level) {
    var successors = graph.getSuccessors(comp), i;

    if (visited.indexOf(comp.id) > -1)
        return true;
    visited.push(comp.id);

    for (i = 0; i < successors.length; i++)
        if (hasCycle(successors[i], visited.slice(), ++level))
            return true;

    return false;
}

其次，更重要的是，尝试 graph.getNeighbors 方法而不是 graph.getSuccessors（记住只检查一个方向的邻居）。

Answer 2

我相信我已经使用此算法找到了这种不稳定行为的根本原因。

实际上是 JointJS API 方法 getElements() returns 元素数组在图形单元格中的条目顺序。这意味着如果您创建 3 个元素 A, B, C 来创建类似 A-->B-->C 的图形，但您添加这些元素的顺序是首先 A，然后是 C，然后是 B在末尾。现在根据if条件(graph.getPredecessors(elem).length > 0) && !elem.isLink() && hasCycle(elem, visited, level)，循环检测实际上是从C开始的。在这种情况下，C 没有任何出站邻居，它被标记为已访问。现在，在下一次迭代中，检查 B（因为它在 C 之后进入图表）并且它有 C 作为其出站邻居。现在 C 再次被评估，但 C 已被标记为已访问。因此，它表明存在循环。

所以，我认为，我们在图中的搜索应该从没有任何先行者的节点开始。例如，在前面的示例中，我们的搜索必须始终以 A 开头。该图还可能包含一个或多个没有任何前任节点的节点。同样在这种情况下，我们需要从没有任何前驱的节点开始搜索。例如，A1-->B, A1-->C, A2-->B, A2-->C 是这样的。我们的检测必须从A1和A2.

开始

我修改了方法如下，符合之前的策略：

function checkForCycleExistence() {
    var visited = [];
    var level = 0;
    var isCycleExists;
    var _elements = graph.getElements();
    for (var i = 0; i < _elements.length; i++) {
        var elem = _elements[i];
        if ((graph.getPredecessors(elem).length == 0)
                && hasCycle(elem, visited, level)) {
            isCycleExists = true;
            break;
        }
    }
    if (isCycleExists) {
        console.log("Cycle Exists");
    }
    return isCycleExists;
}

function hasCycle(comp, visited, level) {
    var neighbors = graph.getNeighbors(comp, {
        outbound : true
    }), i;

    if (visited.indexOf(comp.id) > -1)
        return true;

    visited.push(comp.id);

    for (i = 0; i < neighbors.length; i++)
        if (hasCycle(neighbors[i], visited.slice(), ++level))
            return true;

    return false;
}

JointJs 循环检测

JointJs Cycle Detection

javascript

jointjs