The Perl Toolchain Summit needs more sponsors. If your company depends on Perl, please support this very important event.
 / 
Algorithm-Graphs-TransitiveClosure-Tiny-1.01
River stage zero No dependents
++
/ Algorithm::Graphs::TransitiveClosure::Tiny

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:

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.