Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Perl > Perl Misc > Graph.0.69 Module---how to get a DAG from graph with cycles

Reply
Thread Tools

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

 
 
Sean
Guest
Posts: n/a
 
      01-23-2006
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 ####

================================================== ======================
 
Reply With Quote
 
 
 
 
Sean
Guest
Posts: n/a
 
      01-24-2006
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$(E-Mail Removed)>, Sean
> <(E-Mail Removed)> 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:ath_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

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Finding all cycles in a directed graph NoƩ Alejandro Ruby 2 10-10-2010 04:09 AM
Re: Finding all cycles within an undirected graph (disappearedng) disappearedng Python 0 07-22-2009 02:16 PM
Finding all cycles within an undirected graph disappearedng Python 0 07-22-2009 01:04 PM
Graph.0.69 Module---how to get a DAG from.... Sean Perl Misc 0 01-23-2006 06:07 PM
GD::Graph: "mixed" graph doesn't recognize "area" graph type Emilio Mayorga Perl Misc 6 10-08-2003 02:14 AM



Advertisments