++ed by:
11 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;

# 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 on 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 `weight`. 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.

path => boolean

If set true, sets `path_length` and `path_vertices`. If either of those are true (and `path_vertices` is by default), then both are calculated.

path_length => boolean

By default "false", but see above as overridden by default `path_vertices` being true. If calculated, they can be retrieved using the path_length() method.

path_vertices => boolean

By default the paths are computed, with the boolean transitivity, they can be retrieved using the path_vertices() method.

path_count => boolean

As an alternative to setting `path_length`, if this is true then the matrix will store the quantity of paths between the two vertices. This is still retrieved using the path_length() method. The path vertices will not be available. You should probably only use this on a DAG, and not with `reflexive`.

## 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_successor(\$u, \$v)

Return the successor of vertex \$u in the transitive closure path towards vertex \$v.

all_paths(\$u, \$v)

Return list of array-refs with all the paths from \$u to \$v. Will ignore self-loops.

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