# NAME

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

# VERSION

Version 0.03

# SYNOPSIS

```
use Algorithm::Graphs::TransitiveClosure::Tiny qw(floyd_warshall);
# The hash values here need not to be undef, but floyd_warshall()
# only adds undef.
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.

# SEE ALSO

Algorithm::Graphs::TransitiveClosure, Text::Table::Read::RelationOn::Tiny

# SUPPORT

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

` perldoc Algorithm::Graphs::TransitiveClosure::Tiny`

You can also look for information at:

RT: CPAN's request tracker (report bugs here)

https://rt.cpan.org/NoAuth/Bugs.html?Dist=Algorithm-Graphs-TransitiveClosure-Tiny

CPAN Ratings

https://cpanratings.perl.org/d/Algorithm-Graphs-TransitiveClosure-Tiny

Search CPAN

https://metacpan.org/release/Algorithm-Graphs-TransitiveClosure-Tiny

# LICENSE AND COPYRIGHT

This software is copyright (c) 2022 by Abdul al Hazred.

This is free software; you can redistribute it and/or modify it under the same terms as the Perl 5 programming language system itself.