Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw
 
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 (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] }; } }
    لսႽ ᥲᥒ⚪⟊Ⴙᘓᖇ Ꮅᘓᖇ⎱ Ⴙᥲ𝇋ƙᘓᖇ
      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: (14)
As of 2015-07-02 12:37 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 (36 votes), past polls