Good way to find ALL cycles within a graph

[disappearedng]

Hey everyone
I am looking for ways to detect ALL cycles within a graph. I will
build a graph with about 30,000 nodes and if possible, the most time-
efficient one.

This is what I have attempted:
First build a DFS tree. The for every node, add in a path that does
not exist in the spanning tree. After that detect cycle if present.
Recurse on whole tree.

However, this algorithm doesn't work if we have cycles that are formed
by adding two missing edges in the spanning tree. (meaning that the
spanning tree actually misses 2 edges)

[Dan Schult]

I think that finding all cycles of length k or less is typically done
by finding the cycles while doing a DFS. There must be published
algorithms on that, but a crude algorithm could be:
1) start at some node,
2) do a DFS building a spanning tree (during which you have to
check if an edge connects to an already considered node.
3) Any edge from the (still forming) spanning tree to an already
considered node is a "back edge" and represents a cycle. Record
these cycles.
4) when you have finished with the spanning tree you have a base
for all cycles in the graph. By that I mean that any cycle is
an exclusive OR of two or more base cycles.

The code would be very similar to all_pairs_shortest_path()
in networkx, so you might start with that code. You need to
add a few lines to check for a cycle/back edge and record it.

A quick google search yielded this explanation:
http://www.me.utexas.edu/~bard/IP/Handouts/cycles.pdf

With 30,000 nodes, if your network is at all dense,
it is likely to take a long time---


Dan