/ 
Algorithm-Graphs-Reachable-Tiny-0.02
River stage zero No dependents
/ Algorithm::Graphs::Reachable::Tiny

NAME

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

VERSION

Version 0.02

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

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