Graph.0.69 Module---how to get a DAG from graph with cycles

Discussion in 'Perl Misc' started by Sean, Jan 23, 2006.

  1. Sean

    Sean Guest

    Here I use an example to illustrate the problem I met when using Graph
    Theory Module: I have a directed graph looks like the following (see the
    figure).
    Edges in the original directed graph:
    [main] -> [foo]; [main] -> [bar];
    [foo] -> [trouble];
    [trouble] -> [foo];

    I want to find all the cycles in the graph. whenever I find a cycle, I
    want to break it by deleting an edge starting from a vertex farthest
    away from node [main] to get the following graph ---in this case,
    deleting [trouble] -> [foo] because [trouble] is the farthest node in
    this cycle.
    So, edges after the desired manipulation are:
    [main] -> [foo]; [main] -> [bar];
    [foo] -> [trouble];
    -----------------------fiugre of original graph------------
    [main]
    / \
    [foo] [bar]
    / /
    / /
    [trouble]
    -----------------------end of the figure-------------------

    I tried to use @v = $g->connected_component_by_index($i), but it seems
    to return single nodes (which is deemed as strongly connected component
    itself), which is not what I want.
    $g->find_a_cycle does not work either, because it returns same cycle no
    matter how many times you call it.

    I am newbie in perl. Can someone give me a suggestion how to utilize
    the existing APIs in Graph.0.69 to achieve what I want?
    Here is what I experimented a bit(which failed), and it may give a
    better background of my question.

    ====================================================================
    #mycode.pl
    6
    7 use Graph;
    8 my $gcall = Graph->new;
    11
    12 while (<>) {
    13 chomp;
    14 if (/^(.*)\t->\t(.*)\t=>\w*\t->(\d*)/) {
    15 $gcall->add_edge($1, $2);
    16 print $1, " to ", $2, " with ", $3, "\n";
    17 #print $2, "\n";
    18 }
    19
    20 }
    21########at this point, the graph has been built#############
    46
    47 foreach (1..5) {
    48 print "SCC $_:",
    $gcall->strongly_connected_component_by_index($_), "\n\n";
    49 print "cycle $_:",
    $gcall->find_a_cycle;
    50}
    ######### my tries to try to report cycles, FAILED ####

    ========================================================================
     
    Sean, Jan 23, 2006
    #1
    1. Advertising

  2. Sean

    Sean Guest

    Hi Jim,
    Thanks so much for the prompt help. It is exactly what I wanted, and
    I'll port it to my program.

    Best regards,

    Jim Gibson wrote:
    > In article <dr3c1l$gib$>, Sean
    > <> wrote:
    >
    >
    >>Here I use an example to illustrate the problem I met when using Graph
    >>Theory Module: I have a directed graph looks like the following (see the
    >>figure).
    >>Edges in the original directed graph:
    >>[main] -> [foo]; [main] -> [bar];
    >>[foo] -> [trouble];
    >>[trouble] -> [foo];
    >>
    >>I want to find all the cycles in the graph. whenever I find a cycle, I
    >>want to break it by deleting an edge starting from a vertex farthest
    >>away from node [main] to get the following graph ---in this case,
    >>deleting [trouble] -> [foo] because [trouble] is the farthest node in
    >>this cycle.
    >>So, edges after the desired manipulation are:
    >>[main] -> [foo]; [main] -> [bar];
    >>[foo] -> [trouble];
    >>-----------------------fiugre of original graph------------
    >> [main]
    >> / \
    >> [foo] [bar]
    >> / /
    >> / /
    >> [trouble]
    >>-----------------------end of the figure-------------------
    >>
    >>I tried to use @v = $g->connected_component_by_index($i), but it seems
    >>to return single nodes (which is deemed as strongly connected component
    >>itself), which is not what I want.
    >>$g->find_a_cycle does not work either, because it returns same cycle no
    >>matter how many times you call it.
    >>
    >>I am newbie in perl. Can someone give me a suggestion how to utilize
    >>the existing APIs in Graph.0.69 to achieve what I want?
    >>Here is what I experimented a bit(which failed), and it may give a
    >>better background of my question.
    >>
    >>====================================================================
    >>#mycode.pl
    >> 6
    >> 7 use Graph;
    >> 8 my $gcall = Graph->new;
    >> 11
    >> 12 while (<>) {
    >> 13 chomp;
    >> 14 if (/^(.*)\t->\t(.*)\t=>\w*\t->(\d*)/) {
    >> 15 $gcall->add_edge($1, $2);
    >> 16 print $1, " to ", $2, " with ", $3, "\n";
    >> 17 #print $2, "\n";
    >> 18 }
    >> 19
    >> 20 }
    >> 21########at this point, the graph has been built#############
    >> 46
    >> 47 foreach (1..5) {
    >> 48 print "SCC $_:",
    >> $gcall->strongly_connected_component_by_index($_), "\n\n";
    >> 49 print "cycle $_:",
    >> $gcall->find_a_cycle;
    >> 50}
    >> ######### my tries to try to report cycles, FAILED ####
    >>
    >>========================================================================

    >
    >
    > You have posted 19 lines of an at-least 50-line program, so your posted
    > program is not complete. Also, you do not show your data. Here is a way
    > to create a graph equivalent to your sample graph without reading
    > external data:
    >
    > my $gcall = my $g = Graph->new( edges =>
    > [ ['a','b'], ['a','c'], ['b','d'], ['d','b']] );
    >
    > Disclaimer: I don't know much about graphs, and I don't know about all
    > the graph terminology used by the Graph module. In particular, I don't
    > know what "connected" (strongly or weakly) means, so I don't know how
    > that concept might be pertinent to your problem.
    >
    > It is true that Graph::find_a_cycle() will find a random cycle if one
    > exists in your graph, and will only return one. However, if you then
    > break that cycle by removing an edge, then you can go on to finding and
    > breaking the next one.
    >
    > I am not sure how to find the vertex "farthest from node [main]" in
    > cases more complex than your example. Here is a sample program that
    > uses Graph::APSP_Floyd_Warshall() to find the "all pairs shortest
    > paths" and Graph::path_length() to find the shortest path length from
    > the root of the graph to any node. If these do not give the results you
    > are looking for, then you will have to substitute some other method for
    > picking which edge from a cycle of vertices to delete. The program adds
    > a 3-vertex cycle to your original sample:
    >
    > #!/usr/local/bin/perl
    > use strict;
    > use warnings;
    > use Graph;
    >
    > my $g = Graph->new(
    > edges =>
    > [
    > ['a','b'],
    > ['a','c'],
    > ['b','d'],
    > ['d','b'],
    > ['c','e'],
    > ['e','f'],
    > ['f','c'],
    > ]
    > );
    >
    > print "Graph: ", $g->stringify(), "\n";
    > my @v = sort $g->vertices();
    > print "Vertices: @v\n";
    >
    > # find and remove all cycles
    > while( my @cyc = $g->find_a_cycle() ) {
    > print "\nFound cycle: @cyc\n";
    > my $apsp = $g->APSP_Floyd_Warshall();
    > my %dist = map { $_ => $apsp->path_length('a',$_) } @cyc;
    > my $far = (sort { $dist{$a} <=> $dist{$b} } keys %dist )[-1];
    > print "Farthest vertex is $far\n";
    > CYC: for my $v ( @cyc ) {
    > next if $v eq $far;
    > next unless $g->has_edge($far,$v);
    > print "Remove edge (${far}->$v)\n";
    > $g->delete_edge($far,$v);
    > print "Graph is now: ", $g->stringify(), "\n";
    > last CYC;
    > }
    > }
    > ... which gives as output:
    >
    > Graph: a-b,a-c,b-d,c-e,d-b,e-f,f-c
    > Vertices: a b c d e f
    >
    > Found cycle: b d
    > Farthest vertex is d
    > Remove edge (d->b)
    > Graph is now: a-b,a-c,b-d,c-e,e-f,f-c
    >
    > Found cycle: e f c
    > Farthest vertex is f
    > Remove edge (f->c)
    > Graph is now: a-b,a-c,b-d,c-e,e-f
    >
    > __END__
    >
    > Note: this program can be made more efficient, but you should only
    > worry about that if your graph is very large.
    >
    > Posted Via Usenet.com Premium Usenet Newsgroup Services
    > ----------------------------------------------------------
    > ** SPEED ** RETENTION ** COMPLETION ** ANONYMITY **
    > ----------------------------------------------------------
    > http://www.usenet.com
     
    Sean, Jan 24, 2006
    #2
    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. Mohun Biswas

    tools for drawing a DAG

    Mohun Biswas, Jul 15, 2003, in forum: Java
    Replies:
    3
    Views:
    2,771
  2. disappearedng
    Replies:
    0
    Views:
    379
    disappearedng
    Jul 22, 2009
  3. disappearedng
    Replies:
    0
    Views:
    1,469
    disappearedng
    Jul 22, 2009
  4. Noé Alejandro

    Finding all cycles in a directed graph

    Noé Alejandro, Oct 9, 2010, in forum: Ruby
    Replies:
    2
    Views:
    325
    Jeremy Bopp
    Oct 10, 2010
  5. Sean
    Replies:
    0
    Views:
    91
Loading...

Share This Page