Amit Kumar Mondal Amit Kumar Mondal - 2 months ago 30
Javascript Question

JointJs Cycle Detection

I am trying to implement an algorithm to detect cycles in a directed graph (only outbound connections) using JointJS. I have written the following code which does not perform expectedly.

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;
}


It would be really helpful if anyone could help me in this.

Answer

The problem is successor is not the same as direct successor. Check out graph.getSuccessors(comp) value: if the lib uses consistent function names, that should contain B,C,D and E for the first run. So you mark those visited, but also run hasCycle(c, visited.slice(), ++level) where you are checking nodes starting from D again (I guess D is the first one for which you get the "already visited" case).

First, I'd recommend to get rid of doubling the iteration in your function, do smth like

 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;
}

And second, more importantly, try the graph.getNeighbors method instead of graph.getSuccessors (remember to check only neighbors in one direction).