Loop Detection In Graph

Topics: algorithm, graph
Jun 7, 2008 at 5:19 AM
Hello all,

I have downloaded the QuickGraph solutions. I have to say it is brilliant and thank you for sharing it.
It saves a lot of people a lot of time and heartache.

I have been trying to write some code to detect a loop in a directional graph. For example:

A->B
B->C
C->A
B->A

contains couple of loops. Now, I used the quick graph and tried to use the events, to build up my
list of paths and anyway, it got a bit complicated, as I don't seem to be able to think clear about
this problem?

Can someone please help and let me know how I could detect the loops in a graph and even better
give the list of loops(e.g A->B->C->A and A->B->A)?

I appreciate your help. Sorry if the solution looks trivial to you but I am really stuck.

Thanks and cheers,
Ben.
Coordinator
Jun 10, 2008 at 7:52 AM
You can detect loops by doing a depth first search and listening to back edges (gray edges). There's no algorithm in Pex that can enumerate all cycles. I suggest looking in the literature for such algorithm.
Jun 11, 2008 at 5:10 AM
I actually found a way to do it. What I did was I only created a graph and then wrote a recursive function to enumerate each of the outedges and check to see if the next node is in the current
list of visited nodes. Seems to work. I also didn't use any of the algorithms or events.
Thanks anyway.
Coordinator
Aug 25, 2008 at 5:24 PM
Ben,

If you use a recursive function and a graph that is big enough, you will have a stack overflow - and it will take down your process. Just to let you know.
Aug 26, 2008 at 12:52 AM
pelikhan,

Thank you. Yes I was aware as the number of nodes grow the process time explodes, but for my situation this was good enough as I didn't have that many nodes.

Thanks again.
Ben.
Coordinator
Aug 26, 2008 at 8:45 AM
Look at AlgoUtility.IsDirectedAcyclicGraph, it detects loop using the DFS.
Jan 29, 2013 at 5:37 PM

ben123,

 I am really interested in the solution you found to detect all the cycles in graph. I am actually working on a project where i am supposed to do the same. Do you mind sending me your code ? 

Thank you 

Jan 29, 2013 at 11:23 PM

Hi cgadjoro,

Wow, that was about 5 years ago. Honestly I can't even remember where I used this or any details about it. I can't even believe I managed to guess my password for this site. 

Sorry I wish I could help out but this doesn't ring a bell.

Cheers,

Ben.

Feb 17, 2015 at 2:44 PM
Hi all,

just for clarification: I am using the latest Nuget version of Quickgraph (v4.0.30319).

I was reading a lot of posts regarding the topic of cycle detection within QuickGraph. At first i tried to apply DFS on a cyclic graph. As it was written in several posts, this should have led to an exception. In my situation, i encountered none. To have the check being performed by "IsDirectedAcyclicGraph" is working fine, but in my case, it would be cool to know which node or edge closes the cycle.

If one is able to shed light on the actual behaviour of DFS and which event should be tracked i would be very happy.

Cheers.