Re: Union/Intersection of Multiple Arrays

[JavaFan]

QUESTION: How can I compute the sub-groups of nodes that can communicate based on signal strength and print the lists? I don't necessarily need to know "full adjacencies"; rather, just like the example above, if 1-2 and 2-3, then 1,2,3 are in a "group".

What you want is called a Transitive Closure, which is a well known problem from graph theory. There are simple algorithms that run in cubic time worst case, but IIRC, an n^2.5 algorithm exists as well. Search on CPAN for "Graph" and "Transitive Closure" should give you a few pointers.

[VinsWorldcom]

Shame I'm only getting around to updating this little gem now, but funny how $work has a way of leading you astray just to bring you back to the same thing years later.

Indeed you are *CORRECT* - "transitive closure", and the module Graph has a submodule Graph::TransitiveClosure::Matrix that handles this. Following is code that simply replaces the "print_union" sub from my original post.

use Graph;
use Graph::TransitiveClosure::Matrix;

...

sub print_union {
    my ( $node, $signal ) = @_;

    my $g = Graph->new();
    for my $i ( 1 .. $#{$node} - 1 ) {
        for my $j ( 2 .. $#{$node} ) {
            if ( defined( $signal->[$i][$j] ) and ( $signal->[$i][$j] 
+> 0 ) ) {
                $g->add_edge( $i, $j );
            }
        }
    }

    my $tcm = Graph::TransitiveClosure::Matrix->new( $g, reflexive => 
+0 );

    print "    ";
    for my $i ( 2 .. $#{$node} ) {
        printf "%2i ", $i;
    }
    print "\n    ";
    for my $i ( 2 .. $#{$node} ) {
        printf "-- ",;
    }
    print "\n";
    for my $i ( 1 .. $#{$node} - 1 ) {
        printf "%2i] ", $i;
        for my $j ( 2 .. $#{$node} ) {
            printf "%2s ", ( $tcm->is_transitive( $i, $j ) ) ? "X" : "
+ ";
        }
        print "\n";
    }
}