From: "Noé Alejandro" <casanejo@...>
Date: 2010-10-10T10:27:37+09:00
Subject: Re: Finding all cycles in a directed graph

Jeremy Bopp wrote:
> On 10/09/2010 11:21 AM, Noé Alejandro wrote:
>> (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

Hello Jeremy, nice to meet you.

Well, I came to that conclusion because that is what documentation says:
http://rgl.rubyforge.org/rgl/classes/RGL/MutableGraph.html#M000084

cycles()
Returns an array of all minimum cycles in a graph.
This is not an efficient implementation O(n^4)...

At least that was I understood.

Greetings.
-- 
Posted via http://www.ruby-forum.com/.