Finding all cycles in a directed graph

Discussion in 'Ruby' started by Noé Alejandro, Oct 9, 2010.

  1. 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.
    --
    Posted via http://www.ruby-forum.com/.
     
    Noé Alejandro, Oct 9, 2010
    #1
    1. Advertising

  2. 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/.
     
    Noé Alejandro, Oct 10, 2010
    #2
    1. Advertising

  3. Noé Alejandro

    Jeremy Bopp Guest

    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
     
    Jeremy Bopp, Oct 10, 2010
    #3
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Altu
    Replies:
    2
    Views:
    1,360
    Dimitre Novatchev
    Nov 14, 2007
  2. disappearedng
    Replies:
    0
    Views:
    374
    disappearedng
    Jul 22, 2009
  3. disappearedng
    Replies:
    0
    Views:
    1,458
    disappearedng
    Jul 22, 2009
  4. IRR
    Replies:
    2
    Views:
    411
  5. Sean
    Replies:
    1
    Views:
    325
Loading...

Share This Page