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

Author

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

Sean

2006-01-23, 6:56 pm

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 ####

========================================
================================

Jim Gibson

2006-01-23, 6:56 pm

In article <dr3c1l$gib$1@mailhub227.itcs.purdue.edu>, Sean
<seanatpurdue@hotmail.com> 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

2006-01-24, 6:56 pm

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$1@mailhub227.itcs.purdue.edu>, Sean
> <seanatpurdue@hotmail.com> wrote:
>
>
>
>
> 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

Sponsored Links