Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris
 
PerlMonks  

Re: Finding connected components in a graph.

by remiah (Hermit)
on Oct 02, 2012 at 20:57 UTC ( #996918=note: print w/ replies, xml ) Need Help??


in reply to Finding connected components in a graph.

Hello zing

I was looking at the same Graph module for several days...
I want to ask the same question for directed graph. I wonder if this module lacks for 'list all path', or whether I miss something.

You can list all shortest path in your graph, if you do like this.

use strict; use warnings; use Graph; my @a=qw(a b d); my @b=qw(c c e); my $g = Graph->new( undirected => 1 ); for (my $r = 0; $r <= 2; $r++) { $g->add_edge($a[$r], $b[$r]); } #get path from apsp my $apsp=$g->APSP_Floyd_Warshall(); #...with all pattern using glob my @v=$g->vertices; my $ptn=join(",", @v); for (glob "{$ptn},{$ptn}"){ my($u,$v)=split(/,/, $_); next if( $u eq $v ); #skip same combination, or ignore self cyc +le my @p=$apsp->path_vertices($u,$v); if (@p){ print join(',', @p), "\n"; } }
So, for just listing all path, it may be faster if I do recursive call by myself. I am feeling missing something.

I would like to ask for a good way, if you find one.
regards.


Comment on Re: Finding connected components in a graph.
Download Code
Replies are listed 'Best First'.
Re^2: Finding connected components in a graph.
by zing (Beadle) on Oct 03, 2012 at 15:55 UTC
    Dear remiah, I'll certainly look into that(as I do need what you are doing) and will let you know when i cross over your problem and a solution for the same very soon.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://996918]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others musing on the Monastery: (19)
As of 2015-07-31 21:01 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (282 votes), past polls