[Haskell-cafe] Breaking cycles in a directed graph.

[Jens Fisseler]

Hi Daniel,

> I want to detect all cycles within the graph and 'break' them by inserting a 
> minimal number of nodes that are labelled with a special cycle-breaker label.
> 
> Can anyone give me advice on a good algorithm for finding the cycles and 
> finding the optimum edges to insert the cycle-breaking nodes on?

I've had a similar problem as I needed to find all (even-length) cycles
in an undirected graph. To the best of my knowledge the algorithm,
described in

R.C. Read, R.E. Tarjan. Bounds on Backtrack Algorithms for Listing
Cycles, Paths and Spanning Trees. Networks 5: 237-252, 1975,

has the (currently) best known running time of O(V+E+EN), N being the
number of cycles found.

As the algorithm is not that easy to understand (at least for me), you
should perhaps have a look at section 8.3, "Cycles", of

Edward M. Reingold, Jurg Nievergelt, Narsing Deo. Combinatorial
Algorithms: Theory and Practice. Prentice-Hall, Englewood Cliffs, 1977.

The algorithm described there is easier to understand and implement.

You can also find a survey in

Prabhaker Mateti, Narsing Deo. On Algorithms for Enumerating All
Circuits of a Graph. SIAM Journal on Computing, 5(1): 90-99, 1976.

--

Hope this helps,

	Jens