P is for Practical PerlMonks

### Finding connected components in a graph.

 on Oct 02, 2012 at 17:57 UTC Need Help??
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++) {
}

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 C-A-B or D-E . Also how do I find the total number of connected components.

Replies are listed 'Best First'.
Re: Finding connected components in a graph.
by choroba (Bishop) 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) {
if grep \$_ eq \$a[\$i], @{ \$subgraphs[\$component] };
}
}
لսႽ† ᥲᥒ⚪⟊Ⴙᘓᖇ Ꮅᘓᖇ⎱ Ⴙᥲ𝇋ƙᘓᖇ
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).

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.
لսႽ† ᥲᥒ⚪⟊Ⴙᘓᖇ Ꮅᘓᖇ⎱ Ⴙᥲ𝇋ƙᘓᖇ
Re: Finding connected components in a graph.
by SuicideJunkie (Vicar) on Oct 02, 2012 at 18:15 UTC

I haven't read YAML before, (Data::Dumper is nice and perl-y), 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.

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

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).

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++) {
}

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

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.

Create A New User
Node Status?
node history
Node Type: perlquestion [id://996887]
Approved by sundialsvc4
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (5)
As of 2018-03-18 23:42 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
When I think of a mole I think of:

Results (231 votes). Check out past polls.

Notices?