zing has asked for the
wisdom of the Perl Monks concerning the following question:
I have two arrays having the connection information "from >to"
{@a=(a,b,d) ,
@b=(c,c,e)}
The following code finds the connected components based on the content of these two arrays.
Code
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]);
}
my @subgraphs = $g>connected_components;
my $V = $g>vertices;
print "\n$V\n";
print "connected components";
use YAML; print Dump \@subgraphs;
OUTPUT
5
connected components

 c
 a
 b

 e
 d
My question is how do I access only one of the connected components? I.e. either CAB or DE .
Also how do I find the total number of connected components.
Re: Finding connected components in a graph. by SuicideJunkie (Priest) on Oct 02, 2012 at 18:15 UTC 
I haven't read YAML before, (Data::Dumper is nice and perly), so I'm partly guessing at the structure here.
@subgraphs looks like a list of the connected components. Pick one element of the array, and you're looking at one subgraph. The number of connected components is just 0+@subgraphs.
 [reply] 

Hi there,
As per your suggestion I added these two lines, but as you can see in the output section the results are totally invalid.
print "First connected component == $subgraphs[1]\n";
print "Number of connected components== $#subgraphs\n";
OUTPUT
5
connected components

 c
 b
 a

 e
 d
First connected component == ARRAY(0x9a8e308)
Number of connected components== 1
 [reply] [d/l] [select] 

Yes. The subgraph is an array reference. Dig in! foreach my element (@{ $subgraphs[0] }) {...}
As expected, the last index in your two element array is 1. The other index is 0. As I wrote, you want to print 0+@subgraphs, or more explicitly, scalar(@subgraphs).
 [reply] [d/l] 
Re: Finding connected components in a graph. by choroba (Canon) on Oct 02, 2012 at 18:20 UTC 
print "Number: ", scalar @subgraphs, "\n";
print "First: ", @{ $subgraphs[0] }, "\n";
Update: If you also want to generate the subgraphs corresponding to the components, you can use the following code:
my @subg;
for my $component (0 .. @subgraphs  1) {
$subg[$component] = Graph::Undirected>new;
for my $i (0 .. $#a) {
$subg[$component]>add_edge($a[$i], $b[$i])
if grep $_ eq $a[$i], @{ $subgraphs[$component] };
}
}
 [reply] [d/l] [select] 

Hi guys, I have this code which takes in input in the form of triplets of vertices(see DATA)
use strict;
use warnings;
use Data::Dumper;
my @S;
while (<DATA>) {
push @S, [split];
}
print "TRIPLETS\n";
print Dumper \@S;
__DATA__
b c a
a c d
d e b
What Im stuck with is this :: Suppose I have these points=(a,b,c,d);
Then I want to find the set of triplets induced by these 4 vertices.
For example for above four points the induced triplets should be:
b c a
a c d
Whereas for vertices=(d,e,a) there isn't any triplet in the data.
Similarly for vertices=(b,e,d) there is a triplet (d e b) in the data(the last one).  [reply] [d/l] [select] 

This is barely related to the post you replied to. Please, if you have a new question, start a new thread. It can bring you more attention.
 [reply] 

Re: Finding connected components in a graph. by remiah (Hermit) on Oct 02, 2012 at 20:57 UTC 
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.
 [reply] [d/l] 

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.
 [reply] 

