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 );
}
}
For efficient use on larger networks, Graph is my new favorite toy:
use Graph::Directed;
my $net = new Graph::Directed;
# populate with $net->add_vertex(), $net->add_edge(),
# $net->add_edges(), $net->add_path()
my $tc = $net->TransitiveClosure_Floyd_Warshall;
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 +.
