Graph:...Matrix(3pm)

💖 Graph::TransitiveClosure::Matrix — the manual page, but make it make sense 💖

okay bestie, welcome to Graph:...Matrix(3pm), a User Contributed Perl Documentation situation, and honestly? it's a bop. we're gonna build a transitive closure matrix and then interrogate it about who can reach whom. let's go 🦋

---

✨ 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 💅

so like. you can use Graph::TransitiveClosure::Matrix to compute the transitive closure matrix of a graph — and if you're feeling extra, you can also get the minimum paths (both the lengths and the actual vertices) between vertices. then afterwards you can query the transitiveness between vertices with the is_reachable() and is_transitive() methods, and query the paths with the path_length() and path_vertices() methods. it's giving full-service, no cap. 🎀

⚠️ real talk bestie: if you modify the graph after computing its transitive closure, the transitive closure and minimum paths may become invalid. so compute, then query, then maybe don't touch anything. 👑💀

🧚 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. yes it's cubic, yes it's iconic, we don't discuss it. 😭

---

👀 SEE ALSO 👀

• Graph::AdjacencyMatrix

---

💖 AUTHOR AND COPYRIGHT 💖

Jarkko Hietaniemi jhi@iki.fi

---

🎀 LICENSE 🎀

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

---

and that's the whole page, bestie. 🫶 this one shipped as perl v5.40.1, dated 2025-03-28, and it lives in the Graph:...Matrix(3pm) corner of the manual — go forth and close some transitively, you've got this. 💅✨