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 of 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
"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 => boolean
- 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 => boolean
- 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.
SEE ALSO¶
Graph::AdjacencyMatrix
AUTHOR AND COPYRIGHT¶
Jarkko Hietaniemi
jhi@iki.fi
LICENSE¶
This module is licensed under the same terms as Perl itself.