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

[Daniel McAllansmith]

On Wednesday 12 July 2006 21:11, Henning Thielemann wrote:
> 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.

I don't think that will give me the solution I'm looking for.

I'll try to rephrase my problem, I think it was a little unclear.


Given a directed graph I want to find the minimal set of edges such that 
deletion of those edges from the graph will result in a new graph with 0 
strongly connected components, ie no cycles, possibly disconnected.
Perhaps the correct term is the minimal _full_ disconnecting set of edges?


Once I've got that set of edges, instead of deleting them, I'll insert one of 
my special 'cycle-breaking' nodes, but that's nothing to do with the core 
graph analysis really.

Examples:

{(A->A)} => {(A->A)}
{(A->B), (B->C)} => {}
{(A->B), (B->C), (B->D), (C->A), (D->A)} => {(A->B)} because it is the least 
number of edges, other solutions would require deleting 2 edges.


A possible solution might be to recursively break the graph into strongly 
connected components, delete an edge from the component then break again 
until there are no more sub components.

That'll probably have pretty poor performance.
It could be made to provide a stable solution easily though which, as Jason 
Dagit points out, is useful for QuickChecking a more complex algorithm.


Daniel