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

[Jason Dagit]

On 7/12/06, Jens Fisseler <jens.fisseler at fernuni-hagen.de> 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