On 10/09/2010 08:27 PM, NoÃ© Alejandro wrote:

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