and 1 contributors

# NAME

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

Version 1.01

# 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 module provides a single function, `floyd_warshall`, which is exported on demand. It is an implementation of the well known Floyd-Warshall algorithm computing the transitive closure of a graph.

The code is taken from Algorithm::Graphs::TransitiveClosure but has been modified. 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`),

• fixes following problem of Algorithm::Graphs::TransitiveClosure:

Example:

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

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

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

No change. The edge 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)` from `Algorithm::Graphs::TransitiveClosure::Tiny`, then the result is correct:

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

Edge from 1 to 2 has been added! (Also note that it was possible to use 1 instead of `undef` as hash value. This value is kept, but the value added by the function is still `undef`!)

• By default, `floyd_warshall(\$graph)` removes empty subhashes from `\$graph`, e.g.

``````    my \$graph = {
this => {that => undef},
that => {}
};
floyd_warshall(\$graph);``````

will result in

``````   {
this => {that => undef}
}``````

This behavior can be changed by setting optional second argument of `floyd_warshall` to a true value, i.e., calling `floyd_warshall(\$graph, 1)` with the above example hash will not remove `that => {}`.

For convenience, `floyd_warshall` 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: