Breaking cycles in a directed graph.
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? Thanks Daniel
Hi Daniel,
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?
I've had a similar problem as I needed to find all (even-length) cycles in an undirected graph. To the best of my knowledge the algorithm, described in R.C. Read, R.E. Tarjan. Bounds on Backtrack Algorithms for Listing Cycles, Paths and Spanning Trees. Networks 5: 237-252, 1975, has the (currently) best known running time of O(V+E+EN), N being the number of cycles found. As the algorithm is not that easy to understand (at least for me), you should perhaps have a look at section 8.3, "Cycles", of Edward M. Reingold, Jurg Nievergelt, Narsing Deo. Combinatorial Algorithms: Theory and Practice. Prentice-Hall, Englewood Cliffs, 1977. The algorithm described there is easier to understand and implement. You can also find a survey in Prabhaker Mateti, Narsing Deo. On Algorithms for Enumerating All Circuits of a Graph. SIAM Journal on Computing, 5(1): 90-99, 1976. -- Hope this helps, Jens
On 7/12/06, Jens Fisseler
Hi Daniel,
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?
I've had a similar problem as I needed to find all (even-length) cycles in an undirected graph. To the best of my knowledge the algorithm, described in
R.C. Read, R.E. Tarjan. Bounds on Backtrack Algorithms for Listing Cycles, Paths and Spanning Trees. Networks 5: 237-252, 1975,
has the (currently) best known running time of O(V+E+EN), N being the number of cycles found.
As the algorithm is not that easy to understand (at least for me), you should perhaps have a look at section 8.3, "Cycles", of
Edward M. Reingold, Jurg Nievergelt, Narsing Deo. Combinatorial Algorithms: Theory and Practice. Prentice-Hall, Englewood Cliffs, 1977.
The algorithm described there is easier to understand and implement.
Assuming the solution is unique, this would be a good place to use QuickCheck. The simpler algorithm could be implemented and verified through some tests + code inspection until you're convinced it's correct (enough). Then you can use QuickCheck on the harder to understand algorithm using the simpler algorithm as the check. Although, this may fail to work if some graphs have multiple solutions and each algorithm picks a different solution. Just a thought, Jason
On Wednesday 12 July 2006 19:19, Jens Fisseler wrote:
R.C. Read, R.E. Tarjan. Bounds on Backtrack Algorithms for Listing Cycles, Paths and Spanning Trees. Networks 5: 237-252, 1975,
section 8.3, "Cycles", of Edward M. Reingold, Jurg Nievergelt, Narsing Deo. Combinatorial Algorithms: Theory and Practice. Prentice-Hall, Englewood Cliffs, 1977.
You can also find a survey in
Prabhaker Mateti, Narsing Deo. On Algorithms for Enumerating All Circuits of a Graph. SIAM Journal on Computing, 5(1): 90-99, 1976.
Hi, Jens. You don't know if there is an overview, or implementation, of these algorithms online do you? I don't have (easy) access to these references. Another that might be applicable is: Donald B. Johnson. Finding all the elementary circuits of a directed graph. SIAM J. Comput, 5:77--84, 1975. Though I don't have access to that either. Also I gather Combinatorica, a Mathematica module, has algorithms covering this sort of thing. I understand it has a restrictive licence so I haven't looked at those either. Thanks Daniel
Hi Daniel,
R.C. Read, R.E. Tarjan. Bounds on Backtrack Algorithms for Listing Cycles, Paths and Spanning Trees. Networks 5: 237-252, 1975,
section 8.3, "Cycles", of Edward M. Reingold, Jurg Nievergelt, Narsing Deo. Combinatorial Algorithms: Theory and Practice. Prentice-Hall, Englewood Cliffs, 1977.
You can also find a survey in
Prabhaker Mateti, Narsing Deo. On Algorithms for Enumerating All Circuits of a Graph. SIAM Journal on Computing, 5(1): 90-99, 1976.
Hi, Jens.
You don't know if there is an overview, or implementation, of these algorithms online do you? I don't have (easy) access to these references.
Another that might be applicable is: Donald B. Johnson. Finding all the elementary circuits of a directed graph. SIAM J. Comput, 5:77--84, 1975.
Johnson's algorithm is the one described in the book by Reingold et al. I have only hardcopies of all references, although I have a PROLOG-implementation of Tarjan's algorithm. One possibility would be to scan the hardcopies and send them to you by e-mail. Regards, Jens
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.
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
participants (4)
-
Daniel McAllansmith -
Henning Thielemann -
Jason Dagit -
Jens Fisseler