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

# 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 of the reflexivity
# of the transitive closure.
\$tcg->is_transitive(\$u, \$v)```
```    my \$tcm = Graph::TransitiveClosure::Matrix->new(\$g, path_length => 1);
\$tcm->path_length(\$u, \$v)```
```    my \$tcm = Graph::TransitiveClosure::Matrix->new(\$g, path_vertices => 1);
\$tcm->path_vertices(\$u, \$v)```
```    my \$tcm = Graph::TransitiveClosure::Matrix->new(\$g, attribute_name => 'length');
\$tcm->path_length(\$u, \$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 => 1
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 => 1
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.