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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe