Finding all cycles in a directed graph

  • Thread starter Noé Alejandro
  • Start date
N

Noé Alejandro

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.
 
N

Noé Alejandro

Jeremy said:
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.
 
J

Jeremy Bopp

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.

I see. Do you need the minimum cycles passing through each vertex of
the graph, or is it sufficient that you identify the clusters of
vertexes which participate in one or more interconnected cycles? For
instance, say you have the following graph:

A -> B -> C -> A
A -> D -> E -> A
A -> F -> G

The minimum cycles should be:

[A, B, C]
[A, D, E]

However, the strongly connected components would be:

[A, B, C, D, E]
[F]
[G]

You could then filter out the trivial components that contain only a
single vertex; however, doing so will hide any vertexes that point back
to themselves directly. The strongly connected component computation is
much more efficient at the moment apparently, so if you think that might
satisfy your needs, you should give it try:

require 'rgl/connected_components'
inv_comp_map = {}
# g is your graph instance...
g.strongly_connected_components.comp_map.each do |v, n|
(inv_comp_map[n] ||= []) << v
end
# This will yield a list of lists of vertexes representing
# the non-trivial strongly connected components of the graph.
inv_comp_map.values.delete_if { |scc| scc.size == 1 }

I wish that the strongly_connected_components method automatically
returned a ready-to-use list of the strongly connected components rather
than the TarjanSccVisitor instance used to compute the list.
Unfortunately, due to ongoing discussions with my employer, I'm not able
to publish any code myself at the moment, but I'm more than happy to
accept patches from others. :)

-Jeremy
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,733
Messages
2,569,440
Members
44,831
Latest member
HealthSmartketoReviews

Latest Threads

Top