finding a circular reference

Topics: algorithm, graph
Jun 24, 2009 at 7:27 PM

Hi,

I'm using QuickGraph to create a graph for a critical path calculation (CPM/PERT). One thing that is not allowed in such a graph is a circular reference, where directly or indirectly nodes point to each other.

At this moment I'm finding out that I have a circular reference by a StackOverflow, but I would like to find out more gentle. Does anyone know of an algorithm or a way to find out you have a circular reference in the graph?

Thanks for any suggestions.

Coordinator
Jun 24, 2009 at 11:36 PM

You can simply execute a depth first search over the graph. If the graph is cyclic, it will throw an exception. You should also be able to detect cycles as you go while you are computing the critical path.

Jun 26, 2009 at 11:54 AM

Hi Pelikhan,

Thanks for getting back so quickly. I search for circular and found nothing, once I started looking for cycle I found loads of posts.

Two questions I have on DFS:

  • Is the exception generated because of an active check for a cycle or because of an stack overflow?
  • Is there also a way to obtain the actual list of nodes that is causing the cycle?

I found a post that seems to do exactly what I need ( http://www.cs.utk.edu/~parker/Courses/CS302-fall03/Notes/GraphIntro/CycleTest2.cpp ) but I'm unsure as to how easy it would be to implement this for Quickgraph and to what extend I can reuse part of DFS to do this.

Thanks for your help and of course for the great library!

Coordinator
Jun 26, 2009 at 5:24 PM

One correction: the topological sort algorithm will throw an exception but the DFS is a better solution for you.

The DFS will raise the ForwardOrCrossEdge event when it detects an edge that creates a loop. You can listen to that event which gives you the problematic edge. Using a vertex predecessor recorder, you can also figure the path to that edge from the root.

See http://quickgraph.codeplex.com/Wiki/View.aspx?title=Depth%20First%20Search%20Example&referringTitle=Home for more info on how DFS and observers work. 

 

 

Jun 26, 2009 at 7:57 PM

Thanks for your help.

Sep 14, 2010 at 3:05 AM

Shouldn't it be the BackEdge event instead of ForwardOfCrossEdge? Here's an article that does cycle detection with boost graph using a DFS, and it uses back edges: http://www.informit.com/articles/article.aspx?p=25777&seqNum=7