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

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

1. ### SeanGuest

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*)/) {
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

2. ### SeanGuest

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*)/) {
>> 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