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

NAME

Algorithm::Graphs::Reachable::Tiny - Compute rechable nodes in a graph.

VERSION

Version 0.01

SYNOPSIS

   use Algorithm::Graphs::Reachable::Tiny qw(all_reachable);

   my %g = (
            0 => {1 => undef},
            1 => {2 => undef, 4 => undef},
            2 => {3 => undef},
            4 => {5 => undef},
            6 => {7 => undef},
            7 => {8 => undef},
            8 => {9 => undef},
            9 => {7 => undef, 10 => undef}
           );

   my $reachable = all_reachable(\%g, [4, 7]);

or

   my $reachable = all_reachable(\%g, {4 => undef, 7 => undef});

DESCRIPTION

Provides a function to determine all nodes reachable from a set of nodes in a graph.

A graph must be represented like this:

    my $graph = {
                 this => {that => undef,
                          # ...

                         },
                 # ...
                };

In this example, there is an edge from 'this' to 'that'. Note that you are not forced to use undef as hash value.

FUNCTIONS

all_reachable(GRAPH, NODES)

GRAPH must be a reference to a hash. It represents the graph as described above. NODES must be a reference to a hash or an array.

The function determines all nodes in GRAPH that are reachable from one of the nodes in NODES. It returns a reference to a hash representing this set.

  • If NODES is empty, then the function returns an empty set.

  • If GRAPH is empty, then the returned set contains exactly the nodes in NODES.

  • If NODES contains elements that are not in GRAPH, then those elements are still in the result set.

Example:

   my %g = (
            0 => {1 => undef},
            1 => {2 => undef, 4 => undef},
            2 => {3 => undef},
            4 => {5 => undef},
            6 => {7 => undef},
            7 => {8 => undef},
            8 => {9 => undef},
            9 => {7 => undef, 10 => undef}
           );

   my $reachable = all_reachable(\%g, {4 => undef, 7 => undef});

$reachable containes:

          {
            4  => undef,
            5  => undef,
            7  => undef,
            8  => undef,
            9  => undef,
            10 => undef,
          }

The following call would lead to the same result:

   my $reachable = all_reachable(\%g, [4, 7]);

AUTHOR

Abdul al Hazred, <451 at gmx.eu>

BUGS

Please report any bugs or feature requests to bug-algorithm-graphs-reachable-tiny at rt.cpan.org, or through the web interface at https://rt.cpan.org/NoAuth/ReportBug.html?Queue=Algorithm-Graphs-Reachable-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::Reachable::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.

SEE ALSO

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