Finding all cycles in a directed graph

Question

How can I find (iterate over) ALL the cycles in a directed graph from/to a given node?

For example, I want something like this:

A->B->A
A->B->C->A

but not: B->C->B

Solution 1

I found this page in my search and since cycles are not same as strongly connected components, I kept on searching and finally, I found an efficient algorithm which lists all (elementary) cycles of a directed graph. It is from Donald B. Johnson and the paper can be found in the following link:

http://www.cs.tufts.edu/comp/150GA/homeworks/hw1/Johnson%2075.PDF

A java implementation can be found in:

http://normalisiert.de/code/java/elementaryCycles.zip

A Mathematica demonstration of Johnson's algorithm can be found here, implementation can be downloaded from the right ("Download author code").

Note: Actually, there are many algorithms for this problem. Some of them are listed in this article:

http://dx.doi.org/10.1137/0205007

According to the article, Johnson's algorithm is the fastest one.

Solution 2

Depth first search with backtracking should work here. Keep an array of boolean values to keep track of whether you visited a node before. If you run out of new nodes to go to (without hitting a node you have already been), then just backtrack and try a different branch.

The DFS is easy to implement if you have an adjacency list to represent the graph. For example adj[A] = {B,C} indicates that B and C are the children of A.

For example, pseudo-code below. "start" is the node you start from.

dfs(adj,node,visited):  
  if (visited[node]):  
    if (node == start):  
      "found a path"  
    return;  
  visited[node]=YES;  
  for child in adj[node]:  
    dfs(adj,child,visited)
  visited[node]=NO;

Call the above function with the start node:

visited = {}
dfs(adj,start,visited)

Solution 3

First of all - you do not really want to try find literally all cycles because if there is 1 then there is an infinite number of those. For example A-B-A, A-B-A-B-A etc. Or it may be possible to join together 2 cycles into an 8-like cycle etc., etc... The meaningful approach is to look for all so called simple cycles - those that do not cross themselves except in the start/end point. Then if you wish you can generate combinations of simple cycles.

One of the baseline algorithms for finding all simple cycles in a directed graph is this: Do a depth-first traversal of all simple paths (those that do not cross themselves) in the graph. Every time when the current node has a successor on the stack a simple cycle is discovered. It consists of the elements on the stack starting with the identified successor and ending with the top of the stack. Depth first traversal of all simple paths is similar to depth first search but you do not mark/record visited nodes other than those currently on the stack as stop points.

The brute force algorithm above is terribly inefficient and in addition to that generates multiple copies of the cycles. It is however the starting point of multiple practical algorithms which apply various enhancements in order to improve performance and avoid cycle duplication. I was surprised to find out some time ago that these algorithms are not readily available in textbooks and on the web. So I did some research and implemented 4 such algorithms and 1 algorithm for cycles in undirected graphs in an open source Java library here : http://code.google.com/p/niographs/ .

BTW, since I mentioned undirected graphs : The algorithm for those is different. Build a spanning tree and then every edge which is not part of the tree forms a simple cycle together with some edges in the tree. The cycles found this way form a so called cycle base. All simple cycles can then be found by combining 2 or more distinct base cycles. For more details see e.g. this : http://dspace.mit.edu/bitstream/handle/1721.1/68106/FTL_R_1982_07.pdf .

Solution 4

The simplest choice I found to solve this problem was using the python lib called networkx.

It implements the Johnson's algorithm mentioned in the best answer of this question but it makes quite simple to execute.

In short you need the following:

import networkx as nx
import matplotlib.pyplot as plt

# Create Directed Graph
G=nx.DiGraph()

# Add a list of nodes:
G.add_nodes_from(["a","b","c","d","e"])

# Add a list of edges:
G.add_edges_from([("a","b"),("b","c"), ("c","a"), ("b","d"), ("d","e"), ("e","a")])

#Return a list of cycles described as a list o nodes
list(nx.simple_cycles(G))

Answer: [['a', 'b', 'd', 'e'], ['a', 'b', 'c']]

Solution 5

The DFS-based variants with back edges will find cycles indeed, but in many cases it will NOT be minimal cycles. In general DFS gives you the flag that there is a cycle but it is not good enough to actually find cycles. For example, imagine 5 different cycles sharing two edges. There is no simple way to identify cycles using just DFS (including backtracking variants).

Johnson's algorithm is indeed gives all unique simple cycles and has good time and space complexity.

But if you want to just find MINIMAL cycles (meaning that there may be more then one cycle going through any vertex and we are interested in finding minimal ones) AND your graph is not very large, you can try to use the simple method below. It is VERY simple but rather slow compared to Johnson's.

So, one of the absolutely easiest way to find MINIMAL cycles is to use Floyd's algorithm to find minimal paths between all the vertices using adjacency matrix. This algorithm is nowhere near as optimal as Johnson's, but it is so simple and its inner loop is so tight that for smaller graphs (<=50-100 nodes) it absolutely makes sense to use it. Time complexity is O(n^3), space complexity O(n^2) if you use parent tracking and O(1) if you don't. First of all let's find the answer to the question if there is a cycle. The algorithm is dead-simple. Below is snippet in Scala.

  val NO_EDGE = Integer.MAX_VALUE / 2

  def shortestPath(weights: Array[Array[Int]]) = {
    for (k <- weights.indices;
         i <- weights.indices;
         j <- weights.indices) {
      val throughK = weights(i)(k) + weights(k)(j)
      if (throughK < weights(i)(j)) {
        weights(i)(j) = throughK
      }
    }
  }

Originally this algorithm operates on weighted-edge graph to find all shortest paths between all pairs of nodes (hence the weights argument). For it to work correctly you need to provide 1 if there is a directed edge between the nodes or NO_EDGE otherwise. After algorithm executes, you can check the main diagonal, if there are values less then NO_EDGE than this node participates in a cycle of length equal to the value. Every other node of the same cycle will have the same value (on the main diagonal).

To reconstruct the cycle itself we need to use slightly modified version of algorithm with parent tracking.

  def shortestPath(weights: Array[Array[Int]], parents: Array[Array[Int]]) = {
    for (k <- weights.indices;
         i <- weights.indices;
         j <- weights.indices) {
      val throughK = weights(i)(k) + weights(k)(j)
      if (throughK < weights(i)(j)) {
        parents(i)(j) = k
        weights(i)(j) = throughK
      }
    }
  }

Parents matrix initially should contain source vertex index in an edge cell if there is an edge between the vertices and -1 otherwise. After function returns, for each edge you will have reference to the parent node in the shortest path tree. And then it's easy to recover actual cycles.

All in all we have the following program to find all minimal cycles

  val NO_EDGE = Integer.MAX_VALUE / 2;

  def shortestPathWithParentTracking(
         weights: Array[Array[Int]],
         parents: Array[Array[Int]]) = {
    for (k <- weights.indices;
         i <- weights.indices;
         j <- weights.indices) {
      val throughK = weights(i)(k) + weights(k)(j)
      if (throughK < weights(i)(j)) {
        parents(i)(j) = parents(i)(k)
        weights(i)(j) = throughK
      }
    }
  }

  def recoverCycles(
         cycleNodes: Seq[Int], 
         parents: Array[Array[Int]]): Set[Seq[Int]] = {
    val res = new mutable.HashSet[Seq[Int]]()
    for (node <- cycleNodes) {
      var cycle = new mutable.ArrayBuffer[Int]()
      cycle += node
      var other = parents(node)(node)
      do {
        cycle += other
        other = parents(other)(node)
      } while(other != node)
      res += cycle.sorted
    }
    res.toSet
  }

and a small main method just to test the result

  def main(args: Array[String]): Unit = {
    val n = 3
    val weights = Array(Array(NO_EDGE, 1, NO_EDGE), Array(NO_EDGE, NO_EDGE, 1), Array(1, NO_EDGE, NO_EDGE))
    val parents = Array(Array(-1, 1, -1), Array(-1, -1, 2), Array(0, -1, -1))
    shortestPathWithParentTracking(weights, parents)
    val cycleNodes = parents.indices.filter(i => parents(i)(i) < NO_EDGE)
    val cycles: Set[Seq[Int]] = recoverCycles(cycleNodes, parents)
    println("The following minimal cycle found:")
    cycles.foreach(c => println(c.mkString))
    println(s"Total: ${cycles.size} cycle found")
  }

and the output is

The following minimal cycle found:
012
Total: 1 cycle found

View more solutions

Comments

[ShuggyCoUk]

Homework I assume? me.utexas.edu/~bard/IP/Handouts/cycles.pdf not that it's not a valid question :)

[Brian Postow]

Note that this is at least NP Hard. Possibly PSPACE, I'd have to think about it, but it's too early in the morning for complexity theory B-)

[CygnusX1]

If your input graph has v vertices and e edges then there are 2^(e - v +1)-1 different cycles (although not all might be simple cycles). That's quite a lot - you might not want to explicitly write all of them. Also, since the output size is exponential, the complexity of the algorithm cannot be polynomial. I think there is still no answer to this question.

[Melsi]

My best option for me was this: personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlg‌​or/…

[fernandosjp]

There is an implementation of this problem in the python lib called networkx. I gave a more detailed answer bellow. It is really simple to use!

[fernandosjp]

The answer I mention is the following: stackoverflow.com/questions/546655/finding-all-cycles-in-gra‌​ph/…

[StayOnTarget]

Possible duplicate of Best algorithm for detecting cycles in a directed graph

[fernandosjp]

user7305, would mind accepting my answer bellow

[user202729]

@DaveInCaz Determining the existence of a cycle is not enough to list all cycles.

[Gleno]

I find it such a hassle to implement from the paper, and ultimately this aglorithm still requires an implementation of Tarjan. And the Java-code is hideous too. :(

[eminsenay]

@Gleno Well, if you mean that you can use Tarjan to find all cycles in the graph instead of implementing the rest, you are wrong. Here, you can see the difference between strongly connected components and all cycles (The cycles c-d and g-h won't be returned by Tarjan's alg)(@batbrat The answer of your confusion is also hidden here: All possible cycles are not returned by Tarjan's alg, so its complexity could be smaller than exponential). The Java-Code could be better, but it saved me the effort of implementing from the paper.

[Gleno]

After a little research you are 100% correct. I'm confused to why your answer isn't accepted.

[eminsenay]

@Gleno The answer was a little bit late :)

[Domenic]

Thank you!! I have been staring at my Tarjan implementation for about an hour, trying to figure out why it was detecting cycles that didn't exist, until I realized I was misinterpreting the output and it was giving me SCCs instead of cycles. Much appreciated for clarifying the difference and providing material that goes the extra step!

[redcalx]

Thanks. I prefer this approach to some of the others noted here as it is simple(r) to understand and has reasonable time complexity, albeit perhaps not optimal.

[codehippo]

This answer is much better than the answer selected. I struggled for quite a while trying to figure out how to get all simple cycles from the strongly connected components. It turns out this is non-trivial. The paper by Johnson contains a great algorithm, but is a little difficult to wade through. I looked at the Java implementation and rolled my own in Matlab. The code is available at gist.github.com/1260153.

[izilotti]

The question was about removing cycles in directed graphs, but this document is on undirected ones.

[brain storm]

how does this find all the cycles?

[brain storm]

if (node == start): -- what is node and start in the first call

[moteutsch]

As noted in the answer, this will only find elementary cycles in the graph. As such, it doesn't really answer the question. The asker listed A->B->A and A->B->C->A as required solutions, and the latter is not elementary.

[Bernhard Barker]

@user1988876 This appears to find all cycles involving a given vertex (which would be start). It starts at that vertex and does a DFS until it gets back to that vertex again, then it knows it found a cycle. But it doesn't actually output the cycles, just a count of them (but modifying it to do that instead shouldn't be too difficult).

[brain storm]

@Dukeling: where is the count stored? and it probably detects cycles only from start, to detect all cycles in the graph, I have to do this call for all the vertices, but before each call, I clear the visited flags correct?

[Bernhard Barker]

@user1988876 Well, it just prints "found a path" an amount of times equal to the number of cycles found (this can easily be replaced by a count). Yes, it will detect cycles only from start. You don't really need to clear the visited flags as each visited flag will be cleared due to visited[node]=NO;. But keep in mind that if you have a cycle A->B->C->A, you'll detect that 3 times, as start can be any 3 of those. One idea to prevent this is to have another visited array where every node that has been the start node at some point is set, and then you don't revisit these.

[brain storm]

@Dukeling: I tried to implement this but have some issues which I posted here: "stackoverflow.com/questions/20576638/…". kindly pass me your comments

[brain storm]

@Dukeling: what would be the runtime for this? I have left a note in your answer to the above question. can you comment there please

[psmears]

@moteutsch: Maybe I'm missing something, but according to the Johnson paper (and other sources), a cycle is elementary if no vertex (apart from the start/finish) appears more than once. By that definition, isn't A->B->C->A elementary too?

[sky_coder123]

How can a cycle exist in a DAG(Directed Acyclic Graph)?

[Joel]

Note for anyone using python for this: the Johnson algorithm is implemented as simple_cycle in networkx.

[Luke Miles]

You can also cnovert a dictionary to a networkx graph: nx.DiGraph({'a': ['b'], 'b': ['c','d'], 'c': ['a'], 'd': ['e'], 'e':['a']})

[Joel]

Should it bother me that about 1.5 years later I'm looking for a way to find the cycles, and it's my own comment that tells me what to do?

[Jehandad]

An implementation of Johnson's algorithm in Python for the networkx library can be found here

[Vishrant]

As an example how to use jgrapht which is used in http://code.google.com/p/niographs/ you can take example from github.com/jgrapht/jgrapht/wiki/DirectedGraphDemo

[Sean L]

Good, but this is not what OP is looking for: find all cycle, likely minimal.

[Vishwa Ratna]

This does not find all cycles.

[nosense]

How do I specify a starting vertex?

[Yossarian42]

this can find cycles, but not able to list all possible cycles in the graph

[blurry]

@eminsenay did you by any chance mean c-d and d-h?

[milahu]

searching for Johnson cycles on github gives 500K hits ...