On 7/12/06, 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.
Assuming the solution is unique, this would be a good place to use QuickCheck. The simpler algorithm could be implemented and verified through some tests + code inspection until you're convinced it's correct (enough). Then you can use QuickCheck on the harder to understand algorithm using the simpler algorithm as the check. Although, this may fail to work if some graphs have multiple solutions and each algorithm picks a different solution. Just a thought, Jason