Abdul al Hazred
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: