IsCyclic fails when node has multiple edges

[holly-hacker]

I'm using IsCyclic(Graph) to check the attached graph and it returns true while I think it should return false. I assume this is because some nodes have multiple edges, since it reports true for simpler graphs.

Image


graph.dot

[Washi1337]

Good catch! It seems to already fail at a very simple graph of three nodes:

digraph G {
   1 -> 2
   1 -> 3
   2 -> 3
}

It seems it breaks because the DFS used in IsCyclic reaches node 3 twice (through edge 1->3, second through 2->3). Since IsCyclic bases its result on a set of all visited nodes, instead of just the nodes in the stack of the DFS, it leads to the conclusion that there was indeed a cycle.

This might be an indication the DFS algorithm (or the traversal interfaces in general) are too restricted and might need a change in API design, because there is currently no way to access the stack of DFS directly using the exposed events. Will have to think about changes there, as I'd rather not reimplement DFS just within the IsCyclic method. There are more algorithms that benefit from DFS and could perhaps benefit from access to the stack as well.