---
name: "Graph::TransitiveClosure::Matrix"
section: "3pm"
platform: "linux"
package: "libgraph-perl"
version: "1:0.9735-1"
release: "Debian 13 (Trixie)"
platforms: ["linux"]
url: "https://new.carta.tech/Graph::TransitiveClosure::Matrix"
---

# Graph::TransitiveClosure::Matrix(3pm)

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

## SEE ALSO

Graph::AdjacencyMatrix

## AUTHOR AND COPYRIGHT

Jarkko Hietaniemi *jhi@iki.fi*

## LICENSE

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