++ed by:

14 PAUSE users
6 non-PAUSE users.

Ed J
and 1 contributors

# NAME

Graph::TransitiveClosure::Matrix - create and query transitive closure of graph

# SYNOPSIS

``````    use Graph::TransitiveClosure::Matrix;
use Graph::Directed; # or Undirected

my \$g  = Graph::Directed->new;
\$g->add_...(); # build \$g

# Compute the transitive closure matrix.
my \$tcm = Graph::TransitiveClosure::Matrix->new(\$g);

# Being reflexive is the default,
# meaning that null transitions are included.
my \$tcm = Graph::TransitiveClosure::Matrix->new(\$g, reflexive => 1);
\$tcm->is_reachable(\$u, \$v)

# is_reachable(u, v) is always reflexive.
\$tcm->is_reachable(\$u, \$v)

# The reflexivity of is_transitive(u, v) depends of the reflexivity
# of the transitive closure.
\$tcg->is_transitive(\$u, \$v)

my \$tcm = Graph::TransitiveClosure::Matrix->new(\$g, path_length => 1);
my \$n = \$tcm->path_length(\$u, \$v)

my \$tcm = Graph::TransitiveClosure::Matrix->new(\$g, path_vertices => 1);
my @v = \$tcm->path_vertices(\$u, \$v)

my \$tcm =
Graph::TransitiveClosure::Matrix->new(\$g,
attribute_name => 'length');
my \$n = \$tcm->path_length(\$u, \$v)

my @v = \$tcm->vertices``````

# DESCRIPTION

You can use `Graph::TransitiveClosure::Matrix` to compute the transitive closure matrix of a graph and optionally also the minimum paths (lengths and vertices) between vertices, and after that query the transitiveness between vertices by using the `is_reachable()` and `is_transitive()` methods, and the paths by using the `path_length()` and `path_vertices()` methods.

If you modify the graph after computing its transitive closure, the transitive closure and minimum paths may become invalid.

# Methods

## Class Methods

new(\$g)

Construct the transitive closure matrix of the graph \$g.

new(\$g, options)

Construct the transitive closure matrix of the graph \$g with options as a hash. The known options are

`attribute_name` => attribute_name

By default the edge attribute used for distance is `w`. You can change that by giving another attribute name with the `attribute_name` attribute to the new() constructor.

reflexive => boolean

By default the transitive closure matrix is not reflexive: that is, the adjacency matrix has zeroes on the diagonal. To have ones on the diagonal, use true for the `reflexive` option.

NOTE: this behaviour has changed from Graph 0.2xxx: transitive closure graphs were by default reflexive.

path_length => boolean

By default the path lengths are not computed, only the boolean transitivity. By using true for `path_length` also the path lengths will be computed, they can be retrieved using the path_length() method.

path_vertices => boolean

By default the paths are not computed, only the boolean transitivity. By using true for `path_vertices` also the paths will be computed, they can be retrieved using the path_vertices() method.

## Object Methods

is_reachable(\$u, \$v)

Return true if the vertex \$v is reachable from the vertex \$u, or false if not.

path_length(\$u, \$v)

Return the minimum path length from the vertex \$u to the vertex \$v, or undef if there is no such path.

path_vertices(\$u, \$v)

Return the minimum path (as a list of vertices) from the vertex \$u to the vertex \$v, or an empty list if there is no such path, OR also return an empty list if \$u equals \$v.

has_vertices(\$u, \$v, ...)

Return true if the transitive closure matrix has all the listed vertices, false if not.

is_transitive(\$u, \$v)

Return true if the vertex \$v is transitively reachable from the vertex \$u, false if not.

vertices

Return the list of vertices in the transitive closure matrix.

path_predecessor

Return the predecessor of vertex \$v in the transitive closure path going back to vertex \$u.

# RETURN VALUES

For path_length() the return value will be the sum of the appropriate attributes on the edges of the path, `weight` by default. If no attribute has been set, one (1) will be assumed.

If you try to ask about vertices not in the graph, undefs and empty lists will be returned.

# ALGORITHM

The transitive closure algorithm used is Warshall and Floyd-Warshall for the minimum paths, which is O(V**3) in time, and the returned matrices are O(V**2) in space.

# SEE ALSO

Graph::AdjacencyMatrix

# AUTHOR AND COPYRIGHT

Jarkko Hietaniemi jhi@iki.fi

# LICENSE

This module is licensed under the same terms as Perl itself.