in reply to results from pairs combination

You are looking for connected subgraphs. Use the Graph module. 


use Graph;

my @pairs=("a,b","c,b","d,f","e,b","f,g");

my $g = new Graph;

for ( @pairs )
{
    my($x,$y) = split /,/;
    $g->add_edge($x,$y);
}

my @subgraphs = $g->weakly_connected_components;

for my $subgraph ( @subgraphs )
{
    print "\nA subgraph:\n";
    for my $v ( @$subgraph )
    {
        my @s = $g->successors($v);
        print "  $v-$_\n" for @s;
    }
}

[download]
Or: 
use Graph;
use Data::Dumper;
use strict;
use warnings;

my @pairs = qw( a,b c,b d,f e,b f,g );

my $g = new Graph edges => [ map [ split /,/ ], @pairs ];

my @av = map [ map { my $v = $_; map [$v,$_], $g->successors($v) } @$_
+ ], $g->weakly_connected_components;

print Dumper @av;

[download]
Between the mind which plans and the hands which build, there must be a mediator... and this mediator must be the heart.

Replies are listed 'Best First'.
Re^2: results from pairs combination
by JadeNB (Chaplain) on Oct 01, 2008 at 22:34 UTC
    An equivalent way of looking at this is that the poster wants the transitive closure of a relation (or graph). Thus, Graph::TransitiveClosure (which is a submodule of Graph—if that terminology makes sense—and is probably what it calls to find (weakly) connected components anyway) or Algorithms::Graphs::TransitiveClosure are also suitable, and may suggest more directly what's going on.

    (Of course, having to call weakly_connected_components instead of the probably more natural connected_components is an artifact of working with directed graphs, which could be avoided by getting a new Graph::Undirected instead.)

    UPDATE: Directed graphs, not graphics.

[reply]
[d/l]
[select]
      a submodule of Graph—if that terminology makes sense

      In some languages, but [un]fortunately not in Perl.

      an artifact of working with directed graphics

      One method name is as good as another. I originally sought to solve this using undirected graphs, but switched because it looks (lacking any other information) that the input graph is directed. If you treat the graph as undirected, then you might have b,a in the output when the input edge was a,b, and I'd rather have not made the assumption that that would be valid.

      What lacks in both methods is a way to get the result in terms of edges rather than vertices. This forced me to do a bit more work to retrieve the relevant original edges from the vertices returned.

      Between the mind which plans and the hands which build, there must be a mediator... and this mediator must be the heart.
[reply]
[d/l]
[select]
        I think that it is a little misleading to say that one method name is as good as another. Certainly your point about the differences in results is an important one that I hadn't considered; but, absent such peculiarities, I think it's good practice to use a name that's very suggestive to the maintenance programmer of what's going on—no one would name a constructor destroy, even though it could be done; and I think that weakly_connected_components would make a maintainer scratch his or her head over the meaning of 'weakly'. (This is not to say that my suggestion of Algorithms::Graphs::TransitiveClosure, which has one call floyd_warshall to achieve the desired goal, is any better.)
[reply]
[d/l]
[select]

In Section Seekers of Perl Wisdom