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

Henning Thielemann lemming at henning-thielemann.de
Wed Jul 12 05:11:50 EDT 2006


On Wed, 12 Jul 2006, Daniel McAllansmith wrote:

> Hello.
> 
> I'm currently using Data.Graph.Inductive to represent a directed graph.  
> 
> 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?

There must be an algorithm for finding the minimal spanning tree or
forest. The edges that do not belong to the tree should be the labelled as
cycle-breakers.



More information about the Haskell-Cafe mailing list