What is the most efficient algorithm for detecting all cycles within a directed graph?

I have a directed graph representing a schedule of jobs that need to be executed, 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.

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

For other algorithm see Strongly connected components on Wikipedia

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.

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.

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.

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!

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

I believe phys wizard's solution will detect a loop in all cases.

I use Cormen's terminologies.

Start with a DFS. A cycle exists, if and only if, a back-edge is discovered during DFS. This is proved as a result of white-path theorum.

I had implemented this problem in sml ( imperative programming) . Here is the outline . Find all the nodes that either have an indegree or outdegree of 0 . Such nodes cannot be part of a cycle ( so remove them ) . Next remove all the incoming or outgoing edges from such nodes. Recursively apply this process to the resulting graph. If at the end you are not left with any node or edge , the graph does not have any cycles , else it has.

http://mathoverflow.net/questions/16393/finding-a-cycle-of-fixed-length I like this solution the best specially for 4 length:)

Also phys wizard says u have to do O(V^2). I believe that we need only O(V)/O(V+E). If the graph is connected then DFS will visit all nodes. If the graph has connected sub graphs then each time we run a DFS on a vertex of this sub graph we will find the connected vertices and wont have to consider these for the next run of the DFS. Therefore the possibility of running for each vertex is incorrect.

There is no algorithm which can find all the cycles in a directed graph in polynomial time. Suppose, the directed graph has n nodes and every pair of the nodes has connections to each other which means you have a complete graph. So any non-empty subset of these n nodes indicates a cycle and there are 2^n-1 number of such subsets. So no polynomial time algorithm exists. So suppose you have an efficient (non-stupid) algorithm which can tell you the number of directed cycles in a graph, you can first find the strong connected components, then applying your algorithm on these connected components. Since cycles only exist within the components and not between them.

If DFS finds an edge that points to an already-visited vertex, you have a circle there.

In my opinion, the most understandable algorithm for detecting cycle in a directed graph is the graph-coloring-algorithm.

Basically, the graph coloring algorithm walks the graph in a DFS manner (Depth First Search, which means that it explores a path completely before exploring another path). When it finds a back edge, it marks the graph as containing a loop.

For an in depth explanation of the graph coloring algorithm, please read this article: http://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/

Also, I provide an implementation of graph coloring in JavaScript https://github.com/dexcodeinc/graph_algorithm.js/blob/master/graph_algorithm.js

Similar Questions

I've been trying to code up an algorithm that takes a directed set of nodes (I have expressed as a sparse directed adjacency matrix, for now) say, A, B, C, and D, that, when called, gives me all possi

I was looking for an algorithm to print all possible paths between two nodes in a directed graph . I saw this : procedure FindAllPaths(u, dest) { push u to stack; if(u == dest) { print stack; } else

I'm looking for a simple algorithm to 'serialize' a directed graph. In particular I've got a set of files with interdependencies on their execution order, and I want to find the correct order at compi

I would like to find a minimum spanning tree (MST) on a weighted directed graph. I have been trying to use Chu-Liu/Edmond's algorithm, which I have implemented in Python (code below). A simple, clear

I am using force directed graph to show topology data on graphical view. I have written below code: var force = d3.layout.force() .charge(-120) .alpha(0) .linkDistance(65) .gravity(0.03) .size([width,

I have a directed, weighted graph. Each node of the graph is represented as a 2-tuple, whose first element is the name of the node and whose second element is a tuple containing all vertices originati

There is a directed graph having a single designated node called root from which all other nodes are reachable. Each terminal node (no outgoing edges) takes an string value. Intermediate nodes have on

I am looking for a concurrent algorithm which would help me in detecting cycles in a directed graph. I know that the sequential algorithm uses a dfs with colouring, however I think that it will fail

I'm looking for opinions on how to model a directed graph that contains one special node. Special node: Cannot have any edges leading to it. Cannot be removed. Current design: Tables: Nodes, Edges.

I'm developing a PHP class able to calculate the route from two points in a unweighted and directed graph system (for EVE Online in particular). I've never developed graph solutions, so I don't really

Out of curiosity, what is the best cryptography algorithm for you as a programmer, given both security and ease of implementation?

I need to find the complexity of finding all the cycles in a undirected graph consisting of 50 nodes. Moreover, if the graph grows large, will the complexity be changed and what will be it if the netw

The graph is composed of many vertices each of which have some properties, and directed edges between two vertices. What's a good XML format to store such? <graph> <vertices> <vertex>

I have a directed graph which has cycles. All edges are weighted, and the weights can be negative. There can be negative cycles. I want to find a path from s to t, which minimizes the total weight on

I'd like to draw a rectangular grid with arrows pointing from each cell to its 4 neighbors. It can also be a directed graph with nodes and labelled edges. Any suggestions to do this in a less tedious

I'm reading boost::graph documentation for future usage. I'm particularly interested in A* algorithm. Having a look to boost::graph::astar_search usage example, it seems the way to stop the algorithm

How would I convert a simple directed graph to a simple undirected one? Is this possible?

a little out of my depth here and need to phone a friend. I've got a directed acyclical graph I need to traverse and I'm stumbling into to graph theory for the first time. I've been reading a lot abou

I am interested in deriving dominance metrics (as in a dominance hierarchy) for nodes in a dominance directed graph, aka a tournament graph. I can use R and the package igraph to easily construct such

Question: Is DFS complexity different for a directed and undirected graph ? If yes, then directed graph complexity is O(V + E), and undirected graph complexity is O(E) ?, where E is edges and V is th

What is the difference between a Directed Graph and a Finite State Machine, in Computer Science/Software Engineering ?

I'm conducting research now on ASL hand recognition in real time using Opencv for my thesis (I'm a beginner). Others say that the first thing to do is detecting the hand, so I want to know what is the

I work a lot with directed graphs resulting from heap dumps of Java programs. One thing that characterizes them is that they contain lots of repeating patterns. I would like to find a way of compressi

I was thinking about the algorithm of finding a negative weight cycle in a directed graph. The Problem is: we have a graph G(V,E), we need to find an efficient algorithm to find a cycle with negative

does anyone know the Donald B. Johnson's algorithm which enumerates all the elementary circuits (cycles) in a Directed graph? link text I have the paper he had published in 1975 but I cannot understan

I am currently working with a rather plain, but large force directed graph and I want my users to be able organize the graph however they see fit at the time. To do this, I want to allow them to inter

Please suggest resources to learn how to find a minimal spanning tree in a directed graph using Prim's algorithm, as well as Bellman-Ford algorithm to calculate the shortest path in a directed graph.

Can someone explain how to find the number of Hamiltonian cycles in a complete undirected graph? Wikipedia says that the formula is (n-1)!/2, but when I calculated using this formula, K3 has only one

I'm trying to implement algoritm to convert Directed Acyclic Graph to Tree (for fun, learining, kata, name it). So I come up with the data structure Node: /// <summary> /// Represeting a node i

Given an adjacency matrix A for a weighted, directed graph (so matrix elements are not just 0/1 and the matrix is not symmetric), are there any good methods for predicting new edges? I have a VERY lar

I want to generate all the Hamiltonian Cycles of a complete undirected graph (permutations of a set where loops and reverses count as duplicates, and are left out). For example, permutations of {1,2,3

Given G, a directed graph, is there a path (not necessarily a simple path) that goes through all the vertices in G? I first need to examine what happens in an acyclic graph and in a strongly-connected

(This is derived from a recently completed programming contest) You are given G, a connected graph with N nodes and N-1 edges. (Notice that this implies G forms a tree.) Each edge of G is directed. (n

I have a directed graph implemented with the adjacency lists using a Java HashMap. Graph class stores only a pointer like this: HashMap<Node<V>, List<Edge<V>>> graph; I'm tryin

Before diving in and rolling my own implementation in Objective-C, I'm looking around to try and find an iPhone SDK-compatible directed graph (digraph) implementation. For the sake of this question,

Given a directed graph G, what is the best way to go about finding a vertex v such that there is a path from v to every other vertex in G? This algorithm should run in linear time. Is there an existin

I am writing program which has a multitude of Directed Graph helper functions in order to gain a deeper understanding of C++. One of the central objects is called a Node which has member functions to

I've got a graph (or unrooted tree) of N nodes and N-1 connections. Each connection has a distance of 1. How can i find a node v that has the maximum distance between v and a set of nodes E{}, when v

Let's say I have a programming language where I can write: x = f(g(1), h(1)) in this case the directed acyclic graph will show the dependencies of calculation like in a spreadsheet (assuming non recur

I've been stock since yesterday with this problem. Unfurturenately/furturenately this problem makes only about 0.5% of the my super huge (for me, a c++ newbie) algorithm thus the need for a library of

I've tried to use this this arrow-head force directed graph example (based on d3.js) And I want to dynamically add nodes/links to the graph, without restarting the animation. I'm no expert of javascri

We currently have a dynamically updated network graph with around 1,500 nodes and 2,000 edges. It's ever-growing. Our current layout engine uses Prefuse - the force directed layout in particular - and

Also are there any randomized algorithms for that. I need to find a single cycle as fast as possible, not all cycles.

I'm looking for an algorithm to be implemented in C++ that when given the adjacency matrix of a directed and unweighted graph, will calculate them number of walks between 2 given nodes. I tried Googli

I have a class Graph with two lists types namely nodes and edges I have a function List<int> GetNodesInRange(Graph graph, int Range) when I get these parameters I need an algorithm that will g

I am looking for the best way to solve this variation on the shortest-path problem: I have a directed graph with unweighted edges. I need to be able to find the shortest path between any two nodes, if

is there an algorithm for finding all the independent sets of an directed graph ? From what i've read an independent set represents a set formed by the nodes that are not adjacent. So for this exampl

Many cases have been shown for force directed graph geometric zooming by SVG Geometric Zooming. In geometric zooming, I only need to add a transform attribute in zoom function. However, in sematic zoo

I am trying to write a program using a directed graph (which I know about but have never implemented) to simulate a network of transportation. The user will input a planet name followed by an integer

I have a directed graph. New edges are added and removed dynamically at run time. If an edge that is about to be added to the graph creates a cycle, then that edge should not be added. How would I do