Re: Transitive closure

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;
[download]

After Compline,
Zaxo

Comment on Re: Transitive closure Download Code

Replies are listed 'Best First'.
Re: Re: Transitive closure by larsen (Parson) on Sep 11, 2001 at 11:19 UTC
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 A² 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 `+`.	[reply] [d/l] [select]

Replies are listed 'Best First'.

Re: Re: Transitive closure
by larsen (Parson) on Sep 11, 2001 at 11:19 UTC

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 A² 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 +.

[reply]
[d/l]
[select]