On 7/12/06, Jens Fisseler <[EMAIL PROTECTED]> wrote:
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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
