views:

11696

answers:

6

What is the most effiecent alogrithm for detecting all cycles within a directed graph?

or

I have a directed graph representing a schedule of jobs that need to be exectuted, a job being a node and a dependency being an edge. I need to detect the error case of a cycle within this graph leading to cyclic dependencies.

+13  A: 

Tarjan's strongly connected components algorithm has O(E + V) complexity

For other algorithm see Strongly connected components on Wikipedia

aku
Thanks Aku, this should work and will also mean i can show the sub graphs causing the issue.
Peauters
How does finding the strongly connected components tell you about the cycles that exist in the graph?
Peter
@Peter,http://stackoverflow.com/questions/546655/finding-all-cycles-in-graph
aku
May be somebody can confirm but the Tarjan algorithm does not support cycles of nodes pointing directly to themselves, like A->A.
Cedrik
+7  A: 

Given that this is a schedule of jobs, I suspect that at some point you are going to sort them into a proposed order of execution.

If that's the case, then a topological sort implementation may any case detect cycles. UNIX tsort certainly does. I think it is likely that it is therefore more efficient to detect cycles at the same time as tsorting, rather than in a separate step.

So the question might become, "how do I most efficiently tsort", rather than "how do I most efficiently detect loops". To which the answer is probably "use a library", but failing that http://en.wikipedia.org/wiki/Topological_sorting has pseudo-code for one algorithm, and a brief description of another from Tarjan. Both have O(V + E) complexity.

Steve Jessop
+1  A: 

If you can't add a "visited" property to the nodes, use a set (or map) and just add all visited nodes to the set unless they are already in the set. Use a unique key or the address of the objects as the "key".

This also gives you the information about the "root" node of the cyclic dependency which will come in handy when a user has to fix the problem.

Another solution is to try to find the next dependency to execute. For this, you must have some stack where you can remember where you are now and what you need to do next. Check if a dependency is already on this stack before you execute it. If it is, you've found a cycle.

While this might seem to have a complexity of O(N*M) you must remember that the stack has a very limited depth (so N is small) and that M becomes smaller with each dependency that you can check off as "executed" plus you can stop the search when you found a leaf (so you never have to check every node -> M will be small, too).

In MetaMake, I created the graph as a list of lists and then deleted every node as I executed them which naturally cut down the search volume. I never actually had to run an independent check, it all happened automatically during normal execution.

If you need a "test only" mode, just add a "dry-run" flag which disables the execution of the actual jobs.

Aaron Digulla
reason for downvote please?
Gnark
A: 

The way I do it is to do a Topological Sort, counting the number of vertices visited. If that number is less than the total number of vertices in the DAG, you have a cycle.

Steve
That does not make sense. If the graph has cycles, there is no topological sorting, which means any correct algorithm for topological sorting will abort.
sleske
+1  A: 

Hi,well the simplest way to do it is to do a depth first traversal of the graph. If the graph has v vertices, this is of O(v). Since you will (possibly) have to do a DFT starting from each possible vertex, the total complexity becomes O(v^2). you have to maintain a stack containing all vertices in the current depth first traversal with its first element being the root node. if you come across an element which is already in the stack during the DFT then you have a cycle!

This would be true for a "regular" graph, but is false for a *directed* graph. For example, consider the "diamond dependency diagram" with four nodes: A with edges pointing to B and C, each of which has an edge pointing to D. Your DFT traversal of this diagram from A would incorrectly conclude that the "loop" was actually a cycle - although there is a loop, it is not a cycle because it cannot be traversed by following the arrows.
Peter
A: 

if a graph satisfy this property if |e|>|v|-1; than a graph contain at least on cycle in the graph

dharmendra singh