[Haskell-cafe] Breaking cycles in a directed graph.
Daniel McAllansmith
dm.maillists at gmail.com
Wed Jul 12 19:44:26 EDT 2006
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
More information about the Haskell-Cafe
mailing list