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

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