From: Jeremy Bopp <jeremy@...>
Date: 2010-10-10T02:18:25+09:00
Subject: Re: Finding all cycles in a directed graph

On 10/09/2010 11:21 AM, No辿 Alejandro wrote:
> Hello everybody.
> 
> I need to find all the cycles in a directed graph. For example:
> A->B->C->A
> 
> I know about some algorithms as used by Donald B. Johnson, Chang Liu and
> Lu Ruan, Tarjan, Gabows or Kosaraju and so on, but does anyone know a
> ruby implementation of any of this algorithms?
> 
> Actually, I'm using the Ruby Graph Library (RGL), but its not efficient
> (O(n^4)... it last 10 to 15 minutes to find the cycles in a graph with
> 33000 edges).
> 
> Thanks in advance.

Hi.  I'm sort of the de facto maintainer of RGL these days since the
original author (Horst Duch棚ne) left the Ruby community and transitioned
to Groovy.

RGL, in fact, uses Tarjan's algorithm for detection of strongly
connected components:

http://rdoc.info/gems/rgl/0.4.0/RGL/Graph#strongly_connected_components-instance_method

Horst wrote that code, and I have an application that uses the
functionality frequently, although with graphs that have significantly
fewer than 33,000 edges.  How did you come to the conclusion that the
complexity of RGL's implementation is O(n^4)?  The implementation should
be O(|V||E|) assuming Tarjan's algorithm is properly implemented, but I
admit that I haven't performed an examination of RGL's implementation
personally.

-Jeremy