# NAME

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

# VERSION

Version 1.01

# 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 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.

# 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.