findCycles only finds longest cycle when there is some overlap

[graemian]

Consider this example:

g2 = new graphlib.Graph({directed: true});

g2.setNode("1");
g2.setNode("2");
g2.setNode("3");

g2.setEdge("1", "2");
g2.setEdge("2", "3");
g2.setEdge("3", "1");

graphlib.alg.findCycles(g2);
// [ [ '3', '2', '1' ] ]

g2.setNode("4");

g2.setEdge("3", "4");
g2.setEdge("4", "1");

graphlib.alg.findCycles(g2);
// [ [ '4', '3', '2', '1' ] ]

Surely the cycle [3, 2, 1] should also be found by the last statement?

[temitope]

@graemian was this ever resolved?

[graemian]

@temitope Nope, I don't think so

[mstou]

Another example where it fails:

var g = new Graph();

g.setEdge(1, 2);
g.setEdge(2, 3);
g.setEdge(3, 4);
g.setEdge(3, 1);
g.setEdge(4, 1);
g.setEdge(4, 5);
g.setEdge(5, 3);

alg.findCycles(g);
// [ [ '5', '4', '3', '2', '1' ] ]

The output should have been: [ [ 1, 2, 3,], [1, 2, 3, 4], [3, 4, 5] ]

In fact 5-4-3-2-1 is not even a simple cycle on the graph ( '3' needs to be traversed twice while not being the starting node )

[mstou]

Looking at the source code, the findCycles() implementation is the following:

function findCycles(g) {
  return _.filter(tarjan(g), function(cmpt) {
    return cmpt.length > 1 || (cmpt.length === 1 && g.hasEdge(cmpt[0], cmpt[0]));
  });
}

tarjan(g) returns an array with all the strongly connected components of the graph We filter that array ,removing singleton arrays whose nodes have no self edges, and return it. So, the returned array is just the strongly connected components filtered.

This falsely assumes that a strongly connected component contains only one cycle.

Finding all the simple cycles in a graph is a bit more complex, we need to run Johnson's Algorithm I will try to implement it and open a pull request

[kimchirichie]

@mstou implementation PR would be greatly appreciated!

[ctfvdheijden]

@mstou would be awesome!

[VotingTool]

This is a severe bug because "findCycles" simply does not return all cycles and users like me have a hard time to figure out why our projects break! Please fix this and until then, make clear in the wiki that it's only "findSomeCycles" at the moment!