Finding cycles in a graph

[Amirdana115]

Hey,

I've been using this library for a while now and me and my coworkers encountered a problem with cycles.
We wrote a function that finds all cycles in a given graph and I would be happy to share it with you.
I'll be glad to get a response and share the idea :)

[Yomguithereal]

Sure @Amirdana115 it would be nice to add such function to graphology standard library. I guess it would go in a new internal graphology-cycles rather than graphology-dag. But before that, what kind of cycles are we speaking of? Simple cycles, like those ?

[Amirdana115]

Yeah, the function gets a graph and returns an array of cycles

[Yomguithereal]

Yes but are we speaking of what is known as "simple" cycles in graph theory (https://en.wikipedia.org/wiki/Cycle_(graph_theory))? Not chordless or peripheral or whatever other cycle kind?

[Amirdana115]

Oh yeah sorry, we are speaking about simple cycles

[Yomguithereal]

Ok, if you want to contribute it to the lib then, I might need some time to scaffold the graphology-cycles subpackage so you can add your code to it. Or if you feel confident you can understand how the monorepo works, you can also try to scaffold it on your end.

In any case we can also review your code in this discussion if you want early feedback regarding optimization etc.

[Amirdana115]

This is the function:

  const findGraphCycles = graph => {
  const visited = new Set();
  const stack = new Set();
  const cycles = [];

  const dfs = (node, path) => {
    visited.add(node);
    stack.add(node);
    path.push(node);

    for (const neighbor of graph.outNeighbors(node)) {
      if (!visited.has(neighbor)) {
        dfs(neighbor, [...path]);
      } else if (stack.has(neighbor)) {
        const cycle = [...path.slice(path.indexOf(neighbor)), neighbor];
        cycles.push(cycle);
      }
    }

    stack.delete(node);
  };

  for (const node of graph.nodes()) {
    if (!visited.has(node)) {
      dfs(node, []);
    }
  }

  return cycles;
};