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

NAME

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

VERSION

Version 0.07

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});

or

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

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

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.

If your vertices are integers, you can also specify the graph as an array of hashes. Non-existent or unconnected vertices can be specified by an empty hash or by undef.

FUNCTIONS

all_reachable(GRAPH, NODES)

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

The function determines the set of all nodes in GRAPH that are reachable from one of the nodes in NODES. It returns a reference to a hash that represents 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.

    Note: If GRAPH is an array reference, then NODES must contain integers only.

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