Possible Duplicate:
Best algorithm for detecting cycles in a directed graph
I'm searching for an algorithm to find loops in a directed graph.
My graph has labels only in the nodes, not in the edges, and it can get pretty huge.
The output of the algorithm should be the loops as a set of lists, each list should contain the labels of the nodes involved in a loop, thus, the first and the last element in the list should be the same.
The graphs I'm using will most likely have only one connected component and no strongly connected components. The number of cycles is expected to be low (I still have to check that).
Any good algorithm for exactly this or something similar is welcome.
Thank you very much.
PS: If something is not clear feel free to ask me for more details, for instance, the graph is stored (so far) as a set of sets of edges, from one node to several nodes, usually one, this should be irrelevant, IMHO.
