Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw
 
PerlMonks  

Re: Union/Intersection of Multiple Arrays

by JavaFan (Canon)
on Apr 21, 2010 at 14:35 UTC ( #836080=note: print w/replies, xml ) Need Help??


in reply to Union/Intersection of Multiple Arrays

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 n2.5 algorithm exists as well. Search on CPAN for "Graph" and "Transitive Closure" should give you a few pointers.
  • Comment on Re: Union/Intersection of Multiple Arrays

Replies are listed 'Best First'.
Re^2: Union/Intersection of Multiple Arrays
by VinsWorldcom (Prior) on Mar 07, 2018 at 20:18 UTC

    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"; } }

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://836080]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others perusing the Monastery: (8)
As of 2021-03-06 18:31 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    My favorite kind of desktop background is:











    Results (118 votes). Check out past polls.

    Notices?