more useful options PerlMonks

### Transitive closure

by larsen (Parson)
 on Sep 10, 2001 at 16:19 UTC Need Help??
 Description: Conjuring on an adjacency matrix (thanks to Math::MatrixReal), this snippet finds every couple of nodes (i, j) such that there's a path from i to j. The matrix \$sum is called transitive closure of the graph \$graph.
```#!/usr/bin/perl

# Transitive closure of a directed graph

use strict;

use Math::MatrixReal;

my \$n = 4; # Matrix' size
my \$graph = Math::MatrixReal->new_from_string( <<'MATRIX' );
[ 0 1 0 1 ]
[ 0 0 1 0 ]
[ 0 0 0 0 ]
[ 1 1 0 0 ]
MATRIX

my \$sum = \$graph->shadow();
my \$p = \$graph->shadow();
\$p->one();

# "One Ring to rule them all, One Ring to find them..."

# Sum of A^i, for i = 0..n-1 (A is the adjacency matrix of our graph)

foreach (0 .. (\$n - 1)) {
\$p = \$p * \$graph;
\$sum = \$sum + \$p;
}

# Finished.
# Now we print every couple (i, j) such that
# there's a path from i to j.

foreach my \$i (1..\$n) {
foreach my \$j (1..\$n) {
print "There's a path from \$i to \$j.\n" if \$sum->element( \$i,
+\$j );
}
}
```
Replies are listed 'Best First'.
Re: Transitive closure
by Zaxo (Archbishop) on Sep 10, 2001 at 17:15 UTC

For efficient use on larger networks, Graph is my new favorite toy:

```use Graph::Directed;
my \$net = new Graph::Directed;
my \$tc = \$net->TransitiveClosure_Floyd_Warshall;

After Compline,
Zaxo

Yes, sure. I was interested in is the application of algebric methods to problems concerning directed graphs.

Interpreting a graph like a relation allows to compose such relation more and more, as in my snippet (the interesting part is that multiplying two matrices is like composing two relations).

So, x A y means there's an arc from x to y. And x AA y (i.e. x A2 y) means: there is some z such that x A z and z A y, so there's a path from x to y through z. When I learned that, I said "hey so those tricky rules for multiplying matrices make sense!".

Another interesting point is that working on algebric structures one could use different operators than sum and product, on condition that the underlying structure is preserved (this is the meaning of my Tolkien quote). Try to reimplement + and * in the matrix product algorithm with min and +.

Create A New User
Node Status?
node history
Node Type: snippet [id://111427]
help
Chatterbox?
 [LanX]: YT=youtube [Discipulus]: ;=) yes i'm not SO dumb [LanX]: SO=StackOverflow [Discipulus]: :=( [perldigious]: I watched some video on YT awhile back with auto-subtitle on and the speaker had a very thick cockney sort of English accent... hillarity ensued in the subtitles. [Discipulus]: IHAA=I hate acronyms anyway

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (7)
As of 2017-06-23 16:42 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
How many monitors do you use while coding?

Results (552 votes). Check out past polls.