Amit Kumar Mondal - 7 months ago 73

Javascript Question

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).