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