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.