Finding cycles in a directed graph

From: Steinar H. Gunderson (sgunderson_at_bigfoot.com)
Date: 02/25/04 

Date: Wed, 25 Feb 2004 16:05:01 +0000 (UTC)

Hi,

Is there a standard algorithm for finding cycles in a directed graph?
Basically, I want to find any cycle (if any), that is, node A has an
edge to B, which in turn has an edge to C, which has an edge back again
to A (of any length, of course). I also need to be able to "wind up" the
cycle back again to find out what nodes are involved; just knowing that
there _is_ a loop somewhere is not good enough.

I'm currently using Floyd-Warshall to find the transitive closure of the
graph, and then checking if any node has an edge to itself (from there
it's quite simple to find any cycle, by finding a node has both an edge
to itself and from the node I already knew was part of a cycle), but
this is O(V^3) and I was wondering if there was something more
efficient. (The big advantage is of course that it's simple; the
Floyd-Warshall code itself is five lines of C, and I'd rather not
implement full Fibonacci heaps etc. if I can help it :-) )

I'm currently working with data sets of about V=500, E=1500, but this
might grow in the future, and I'm not really guaranteed a very fast
machine either, so an improvement down to something along the lines of
O(V^2) would be very helpful. It should be noted that _if_ there is a
cycle, it's very likely to be quite short (about 15-20 nodes long); I
don't know if I can take advantage of this somehow.

Any help or pointers would be much appreciated. :-)

/* Steinar */ 

-- 
Homepage: http://www.sesse.net/

Relevant Pages

  • Re: basis for directed graph, more efficient algorithm?
    ... G has more than one basis, then G has a cycle (to see this assume there ... directed graph has a unique basis, and it can be found by the algorithm ...
    (comp.theory)
  • Re: How to detect circle in a directed graph?
    ... > My application needs a feature to detect whether a directed graph contains ... > circle. ... Does anyone know any efficient implementation? ... that most graphs will have a cycle somewhere near the root, ...
    (comp.lang.java.help)
  • Re: Finding cycles in a directed graph
    ... > Is there a standard algorithm for finding cycles in a directed graph? ... > cycle back again to find out what nodes are involved; ... This can be done very easily by performing a depth-first-search. ...
    (comp.theory)
  • Re: Finding cycles in a directed graph
    ... >Is there a standard algorithm for finding cycles in a directed graph? ... >cycle back again to find out what nodes are involved; ... >graph, and then checking if any node has an edge to itself (from there ... You should look for the Tarjan algorithm to compute the "strongly ...
    (comp.theory)
  • Re: Determining the cycle length of a PRNG-ideas?
    ... consider finding cycles in a derived version of your ... where you iterate the state-change function without ... Any cycle found on the later system will reveal a cycle on ... which in itself reveals a cycle in ...
    (sci.crypt)