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 theattribute_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
andpath_vertices
. If either of those are true (andpath_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 withreflexive
.
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 arrayrefs with all the paths from $u to $v. Will ignore selfloops.
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 FloydWarshall for the minimum paths, which is O(V**3) in time, and the returned matrices are O(V**2) in space.
SEE ALSO
AUTHOR AND COPYRIGHT
Jarkko Hietaniemi jhi@iki.fi
LICENSE
This module is licensed under the same terms as Perl itself.