Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl Monk, Perl Meditation
 
PerlMonks  

Finding connected components in a graph.

by zing (Beadle)
on Oct 02, 2012 at 17:57 UTC ( #996887=perlquestion: print w/ replies, xml ) 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++) { $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 C-A-B or D-E . Also how do I find the total number of connected components.

Comment on Finding connected components in a graph.
Select or Download Code
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 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 choroba (Abbot) 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] }; } }
    لսႽ ᥲᥒ⚪⟊Ⴙᘓᖇ Ꮅᘓᖇ⎱ Ⴙᥲ𝇋ƙᘓᖇ
      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 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.

      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: perlquestion [id://996887]
Approved by sundialsvc4
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (9)
As of 2014-07-31 21:16 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite superfluous repetitious redundant duplicative phrase is:









    Results (253 votes), past polls