[Haskell-cafe] Breaking cycles in a directed graph.
jens.fisseler at FernUni-Hagen.de
Wed Jul 12 03:19:48 EDT 2006
> 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,
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,
More information about the Haskell-Cafe