and 1 contributors

NAME

Algorithm::Graphs::TransitiveClosure::Tiny - Calculate the transitive closure.

Version 0.03

SYNOPSIS

use Algorithm::Graphs::TransitiveClosure::Tiny qw(floyd_warshall);

# The hash values here need not to be undef, but floyd_warshall()
my \$graph = {
0 => {0 => undef},
1 => {1 => undef, 2 => undef, 3 => undef},
2 => {1 => undef, 2 => undef},
3 => {0 => undef, 2 => undef, 3 => undef},
};

floyd_warshall \$graph;

print "There is a path from 2 to 0.\n" if
exists(\$graph->{2}) && exists(\$graph->{2}->{0});

The latter can also be written shorter provided you accept autovivification:

print "There is a path from 2 to 0.\n" if exists(\$graph->{2}->{0});

DESCRIPTION

This is taken from Algorithm::Graphs::TransitiveClosure. The difference is that this implementation of floyd_warshall():

• works on hashes only,

• uses undef for hash values, so an incidence must be checked with exists() (but for the input hash you are not forced to use undef),

• assumes that the hash keys are integers 0, ..., N-1 (for some positive integer N) and this N must be passed as second argument. This is needed to fix a problem in the original implementation (see next item).

• The following problem of Algorithm::Graphs::TransitiveClosure is resolved:

Example:

my \$g = {
0 => { 2 => 1},
1 => { 0 => 1},
};

So there is a vertice from 0 to 2 and a vertice from 1 to 0. So the transitive closure would contain a vertice from 1 to 2. But calling floyd_warshall(\$g) from Algorithm::Graphs::TransitiveClosure results in:

{
0 => { 2 => 1},
1 => { 0 => 1},
}

No change. The vertice from 1 to 2 is missing (you would need to add 2=>{} to \$g to get it right). But if you call floyd_warshall(\$g, 3) from Algorithm::Graphs::TransitiveClosure::Tiny, then the result is correct:

{
0 => { 2 => 1},
1 => { 0 => 1,
2 => undef},
}

Vertice from 1 to 2 has been added! (Also note that you could use 1 instead of undef as hash value, but the value added by the function is undef anyway!)

For convenience, floyd_warshall(\$graph, \$n) returns \$graph.

For further information refer to Algorithm::Graphs::TransitiveClosure.

AUTHOR

Abdul al Hazred, <451 at gmx.eu>

BUGS

Please report any bugs or feature requests to bug-algorithm-graphs-transitiveclosure-tiny at rt.cpan.org, or through the web interface at https://rt.cpan.org/NoAuth/ReportBug.html?Queue=Algorithm-Graphs-TransitiveClosure-Tiny. I will be notified, and then you'll automatically be notified of progress on your bug as I make changes.

SUPPORT

You can find documentation for this module with the perldoc command.

perldoc Algorithm::Graphs::TransitiveClosure::Tiny

You can also look for information at: