Detect loops (cycles of length 1)

[mrkvon]

The library doesn't consistently detect loops, i.e. cycles of length 1, i.e. edges starting and finishing in the same vertex.

1. Loop is not detected

   findCircuits([[0]]); // returns []; expecting [[0, 0]]
   

2. Loop is detected

   findCircuits([[0, 1], [0]]); // returns [[0, 0], [0, 1, 0]] as expected
   

Is this a bug or a limit of the used algorithm? Are directed graphs with loops out of the scope?

[antoinerg]

Thanks for reporting @mrkvon !

The definition of a graph given in the original paper excludes loops. We should probably clean the adjacency list of any loops and update the README to be forthright about it.

[mrkvon]

For anybody interested, detecting loops is as simple as running

function findLoops(adjacencyList) {
  return adjacencyList.reduce((loops, adj, i) => {
    if (adj.includes(i))
      loops.push([i, i]);
    return loops;
  }, []);
}

Just be aware that the findCircuits(adjacencyList) sometimes finds the loops and sometimes not. So if you just concat the findLoops(adjacencyList) and findCircuits(adjacencyList), you may end up with duplicates.

[antoinerg]

If you're willing to make a PR that'd be great :)