Graph::TransitiveClosure::Matrix - create and query transitive closure of graph |
Graph::TransitiveClosure::Matrix - create and query transitive closure of graph
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); $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
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.
new($g)
attribute_name
=> attribute_namew
. You can
change that by giving another attribute name with the attribute_name
attribute to the new()
constructor.
reflexive
option.
NOTE: this behaviour has changed from Graph 0.2xxx: transitive closure graphs were by default reflexive.
path_length
also the path lengths will be computed,
they can be retrieved using the path_length()
method.
path_vertices
also the paths will be computed,
they can be retrieved using the path_vertices()
method.
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.
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.
the Graph::AdjacencyMatrix manpage
Jarkko Hietaniemi jhi@iki.fi
This module is licensed under the same terms as Perl itself.
Graph::TransitiveClosure::Matrix - create and query transitive closure of graph |