Algorithm::Graphs::TransitiveClosure::Tiny - Calculate the transitive closure.
Version 1.03
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});
This module provides a single function, floyd_warshall, which is exported on demand. It is an implementation of the well known Floyd-Warshall algorithm for computing the transitive closure of a graph.
floyd_warshall
The code is taken from Algorithm::Graphs::TransitiveClosure but has been modified. The difference is that this implementation of floyd_warshall():
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),
undef
exists()
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:
floyd_warshall($g)
{ 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:
2=>{}
$g
Algorithm::Graphs::TransitiveClosure::Tiny
{ 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.
floyd_warshall($graph)
$graph
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 => {}.
floyd_warshall($graph, 1)
that => {}
For convenience, floyd_warshall returns $graph.
For further information refer to Algorithm::Graphs::TransitiveClosure.
Abdul al Hazred, <451 at gmx.eu>
<451 at gmx.eu>
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.
bug-algorithm-graphs-transitiveclosure-tiny at rt.cpan.org
Algorithm::Graphs::TransitiveClosure, Text::Table::Read::RelationOn::Tiny
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
Search CPAN
https://metacpan.org/release/Algorithm-Graphs-TransitiveClosure-Tiny
GitHub Repository
https://github.com/AAHAZRED/perl-Algorithm-Graphs-TransitiveClosure-Tiny.git
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.
To install Algorithm::Graphs::TransitiveClosure::Tiny, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Algorithm::Graphs::TransitiveClosure::Tiny
CPAN shell
perl -MCPAN -e shell install Algorithm::Graphs::TransitiveClosure::Tiny
For more information on module installation, please visit the detailed CPAN module installation guide.