Loop detection in graph

Topics: algorithm, graph
Oct 30, 2009 at 4:40 AM

Is there an algorithm to identify all the loops in a graph?

Currently, I am using a DFS with the adjacency graph to identify the loops. The way I am doing it is,

1) Monitor StartVertex event till FinishVertex to consider a group of vertices as a part of same tree   

- All back edges would result in a loop

- All forwardorcross edges with both the vertices in the same tree form a loop

- Store all other forwardorcross edges to post process after the DFS.

- Store the vertex predecessor list of the tree

2) By the end of DFS we have a list of trees and list of forwardorcross edges across trees. I am having a problem with post processing these cross edges to identify the loop paths.

- Each tree can form a loop with other tree if it has atleast 2 cross edges so remove all cross edges that does not satisy this criteria.

I am not sure where to head from here because I need to handle cases like mulitple cross edges between two trees, a loop formed by cross edges spanning across trees :(((

I am sure there should be a better way than this to acheive the task and any pointers would definitely help me. Thanks a lot.