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- gt B- gt A A- gt B- gt C- gt A   but not      B- C- B

User · Answer

If what you want is to find all elementary circuits in a graph you can use the EC algorithm, by JAMES C. TIERNAN, found on a paper since 1970.

The very original EC algorithm as I managed to implement it in php (hope there are no mistakes is shown below). It can find loops too if there are any. The circuits in this implementation (that tries to clone the original) are the non zero elements. Zero here stands for non-existence (null as we know it).

Apart from that below follows an other implementation that gives the algorithm more independece, this means the nodes can start from anywhere even from negative numbers, e.g -4,-3,-2,.. etc.

In both cases it is required that the nodes are sequential.

You might need to study the original paper, James C. Tiernan Elementary Circuit Algorithm

<?php
echo  "<pre><br><br>";

$G = array(
        1=>array(1,2,3),
        2=>array(1,2,3),
        3=>array(1,2,3)
);


define('N',key(array_slice($G, -1, 1, true)));
$P = array(1=>0,2=>0,3=>0,4=>0,5=>0);
$H = array(1=>$P, 2=>$P, 3=>$P, 4=>$P, 5=>$P );
$k = 1;
$P[$k] = key($G);
$Circ = array();


#[Path Extension]
EC2_Path_Extension:
foreach($G[$P[$k]] as $j => $child ){
    if( $child>$P[1] and in_array($child, $P)===false and in_array($child, $H[$P[$k]])===false ){
    $k++;
    $P[$k] = $child;
    goto EC2_Path_Extension;
}   }

#[EC3 Circuit Confirmation]
if( in_array($P[1], $G[$P[$k]])===true ){//if PATH[1] is not child of PATH[current] then don't have a cycle
    $Circ[] = $P;
}

#[EC4 Vertex Closure]
if($k===1){
    goto EC5_Advance_Initial_Vertex;
}
//afou den ksana theoreitai einai asfales na svisoume
for( $m=1; $m<=N; $m++){//H[P[k], m] <- O, m = 1, 2, . . . , N
    if( $H[$P[$k-1]][$m]===0 ){
        $H[$P[$k-1]][$m]=$P[$k];
        break(1);
    }
}
for( $m=1; $m<=N; $m++ ){//H[P[k], m] <- O, m = 1, 2, . . . , N
    $H[$P[$k]][$m]=0;
}
$P[$k]=0;
$k--;
goto EC2_Path_Extension;

#[EC5 Advance Initial Vertex]
EC5_Advance_Initial_Vertex:
if($P[1] === N){
    goto EC6_Terminate;
}
$P[1]++;
$k=1;
$H=array(
        1=>array(1=>0,2=>0,3=>0,4=>0,5=>0),
        2=>array(1=>0,2=>0,3=>0,4=>0,5=>0),
        3=>array(1=>0,2=>0,3=>0,4=>0,5=>0),
        4=>array(1=>0,2=>0,3=>0,4=>0,5=>0),
        5=>array(1=>0,2=>0,3=>0,4=>0,5=>0)
);
goto EC2_Path_Extension;

#[EC5 Advance Initial Vertex]
EC6_Terminate:
print_r($Circ);
?>

then this is the other implementation, more independent of the graph, without goto and without array values, instead it uses array keys, the path, the graph and circuits are stored as array keys (use array values if you like, just change the required lines). The example graph start from -4 to show its independence.

<?php

$G = array(
        -4=>array(-4=>true,-3=>true,-2=>true),
        -3=>array(-4=>true,-3=>true,-2=>true),
        -2=>array(-4=>true,-3=>true,-2=>true)
);


$C = array();


EC($G,$C);
echo "<pre>";
print_r($C);
function EC($G, &$C){

    $CNST_not_closed =  false;                          // this flag indicates no closure
    $CNST_closed        = true;                         // this flag indicates closure
    // define the state where there is no closures for some node
    $tmp_first_node  =  key($G);                        // first node = first key
    $tmp_last_node  =   $tmp_first_node-1+count($G);    // last node  = last  key
    $CNST_closure_reset = array();
    for($k=$tmp_first_node; $k<=$tmp_last_node; $k++){
        $CNST_closure_reset[$k] = $CNST_not_closed;
    }
    // define the state where there is no closure for all nodes
    for($k=$tmp_first_node; $k<=$tmp_last_node; $k++){
        $H[$k] = $CNST_closure_reset;   // Key in the closure arrays represent nodes
    }
    unset($tmp_first_node);
    unset($tmp_last_node);


    # Start algorithm
    foreach($G as $init_node => $children){#[Jump to initial node set]
        #[Initial Node Set]
        $P = array();                   // declare at starup, remove the old $init_node from path on loop
        $P[$init_node]=true;            // the first key in P is always the new initial node
        $k=$init_node;                  // update the current node
                                        // On loop H[old_init_node] is not cleared cause is never checked again
        do{#Path 1,3,7,4 jump here to extend father 7
            do{#Path from 1,3,8,5 became 2,4,8,5,6 jump here to extend child 6
                $new_expansion = false;
                foreach( $G[$k] as $child => $foo ){#Consider each child of 7 or 6
                    if( $child>$init_node and isset($P[$child])===false and $H[$k][$child]===$CNST_not_closed ){
                        $P[$child]=true;    // add this child to the path
                        $k = $child;        // update the current node
                        $new_expansion=true;// set the flag for expanding the child of k
                        break(1);           // we are done, one child at a time
            }   }   }while(($new_expansion===true));// Do while a new child has been added to the path

            # If the first node is child of the last we have a circuit
            if( isset($G[$k][$init_node])===true ){
                $C[] = $P;  // Leaving this out of closure will catch loops to
            }

            # Closure
            if($k>$init_node){                  //if k>init_node then alwaya count(P)>1, so proceed to closure
                $new_expansion=true;            // $new_expansion is never true, set true to expand father of k
                unset($P[$k]);                  // remove k from path
                end($P); $k_father = key($P);   // get father of k
                $H[$k_father][$k]=$CNST_closed; // mark k as closed
                $H[$k] = $CNST_closure_reset;   // reset k closure
                $k = $k_father;                 // update k
        }   } while($new_expansion===true);//if we don't wnter the if block m has the old k$k_father_old = $k;
        // Advance Initial Vertex Context
    }//foreach initial


}//function

?>

I have analized and documented the EC but unfortunately the documentation is in Greek.

User · Answer

Start at node X and check for all child nodes  parent and child nodes are equivalent if undirected    Mark those child nodes as being children of X   From any such child node A  mark it s children of being children of A  X   where X  is marked as being 2 steps away     If you later hit X and mark it as being a child of X    that means X is in a 3 node cycle   Backtracking to it s parent is easy  as-is  the algorithm has no support for this so you d find whichever parent has X     Note  If graph is undirected or has any bidirectional edges  this algorithm gets more complicated  assuming you don t want to traverse the same edge twice for a cycle

User · Answer

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

User · Answer

I was given this as an interview question once  I suspect this has happened to you and you are coming here for help   Break the problem into three questions and it becomes easier    how do you determine the next valid route how do you determine if a point has been used how do you avoid crossing over the same point again   Problem 1  Use the iterator pattern to provide a way of iterating route results  A good place to put the logic to get the next route is probably the  moveNext  of your iterator   To find a valid route  it depends on your data structure   For me it was a sql table full of valid route possibilities so I had to build a query to get the valid destinations given a source   Problem 2  Push each node as you find them into a collection as you get them  this means that you can see if you are  doubling back  over a point very easily by interrogating the collection you are building on the fly     Problem 3   If at any point you see you are doubling back  you can pop things off the collection and  back up    Then from that point try to  move forward  again   Hack  if you are using Sql Server 2008 there is are some new  hierarchy  things you can use to quickly solve this if you structure your data in a tree

User · Answer

DFS c   version for the pseudo-code in second floor s answer   void findCircleUnit int start  int v  bool  visited  vector lt int gt  amp  path        if visited v             if v    start                for auto c   path                  cout  lt  lt  c  lt  lt                   cout  lt  lt  endl              return                    else              return            visited v    true      path push back v       for auto i   G v           findCircleUnit start  i  visited  path       visited v    false      path pop back

User · Answer

DFS from the start node s  keep track of the DFS path during traversal  and record the path if you find an edge from node v in the path to s   v s  is a back-edge in the DFS tree and thus indicates a cycle containing s

User · Answer

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

User · Answer

http   www me utexas edu  bard IP Handouts cycles pdf

User · Answer

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   lt  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  lt - weights indices           i  lt - weights indices           j  lt - weights indices          val throughK   weights i  k    weights k  j        if  throughK  lt  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  lt - weights indices           i  lt - weights indices           j  lt - weights indices          val throughK   weights i  k    weights k  j        if  throughK  lt  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  lt - weights indices           i  lt - weights indices           j  lt - weights indices          val throughK   weights i  k    weights k  j        if  throughK  lt  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  lt - 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   gt  parents i  i   lt  NO EDGE      val cycles  Set Seq Int     recoverCycles cycleNodes  parents      println  The following minimal cycle found        cycles foreach c   gt  println c mkString       println s Total    cycles size  cycle found         and the output is   The following minimal cycle found  012 Total  1 cycle found

User · Answer

I stumbled over the following algorithm which seems to be more efficient than Johnson s algorithm  at least for larger graphs   I am however not sure about its performance compared to Tarjan s algorithm  Additionally  I only checked it out for triangles so far  If interested  please see  Arboricity and Subgraph Listing Algorithms  by Norishige Chiba and Takao Nishizeki  http   dx doi org 10 1137 0214017

User · Answer

In the case of undirected graph  a paper recently published  Optimal listing of cycles and st-paths in undirected graphs  offers an asymptotically optimal solution  You can read it here http   arxiv org abs 1205 2766 or here http   dl acm org citation cfm id 2627951 I know it doesn t answer your question  but since the title of your question doesn t mention direction  it might still be useful for Google search

User · Answer

There are two steps  algorithms  involved in finding all cycles in a DAG    The first step is to use Tarjan s algorithm to find the set of strongly connected components     Start from any arbitrary vertex  DFS from that vertex  For each node x  keep two numbers  dfs index x  and dfs lowval x   dfs index x  stores when that node is visited  while dfs lowval x    min dfs low k   where k is all the children of x that is not the directly parent of x in the dfs-spanning tree  All nodes with the same dfs lowval x  are in the same strongly connected component    The second step is to find cycles  paths  within the connected components  My suggestion is to use a modified version of Hierholzer s algorithm    The idea is     Choose any starting vertex v  and follow a trail of edges from that vertex until you return to v   It is not possible to get stuck at any vertex other than v  because the even degree of all vertices ensures that  when the trail enters another vertex w there must be an unused edge leaving w  The tour formed in this way is a closed tour  but may not cover all the vertices and edges of the initial graph  As long as there exists a vertex v that belongs to the current tour but that has adjacent edges not part of the tour  start another trail from v  following unused edges until you return to v  and join the tour formed in this way to the previous tour     Here is the link to a Java implementation with a test case    http   stones333 blogspot com 2013 12 find-cycles-in-directed-graph-dag html

User · Answer

To clarify    Strongly Connected Components will find all subgraphs that have at least one cycle in them  not all possible cycles in the graph  e g  if you take all strongly connected components and collapse group merge each one of them into one node  i e  a node per component   you ll get a tree with no cycles  a DAG actually   Each component  which is basically a subgraph with at least one cycle in it  can contain many more possible cycles internally  so SCC will NOT find all possible cycles  it will find all possible groups that have at least one cycle  and if you group them  then the graph will not have cycles   to find all simple cycles in a graph  as others mentioned  Johnson s algorithm is a candidate

User · Answer

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

User · Answer

Regarding your question about the Permutation Cycle  read more here  https   www codechef com problems PCYCLE  You can try this code  enter the size and the digits number       include lt cstdio gt  using namespace std   int main         int n      scanf   d   amp n        int num 1000       int visited 1000   0       int vindex 2000       for int i 1 i lt  n i            scanf   d   amp num i         int t visited 0      int cycles 0      int start 0  index       while t visited  lt  n                for int i 1 i lt  n i                          if visited i   0                                vindex start  i                  visited i  1                  t visited                    index start                  break                                  while true                        index                vindex index  num vindex index-1                 if vindex index   vindex start                   break              visited vindex index   1              t visited                      vindex   index  0          start index 1          cycles               printf   d n  cycles vindex 0         for int i 0 i lt  n 2 cycles  i                  if vindex i   0              printf   n            else             printf   d   vindex i

User · Answer

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

[algorithm] Finding all cycles in a directed graph

Examples related to algorithm

Examples related to graph-theory

Examples related to graph-algorithm