Graph::TransitiveClosure − create and query transitive closure of graph
use
Graph::TransitiveClosure;
use Graph::Directed; # or Undirected
my $g = Graph::Directed−>new;
$g−>add_...(); # build $g
# Compute the transitive closure graph.
my $tcg = Graph::TransitiveClosure−>new($g);
$tcg−>is_reachable($u, $v) # Identical to
$tcg−>has_edge($u, $v)
# Being reflexive is the default, meaning that null
transitions
# (transitions from a vertex to the same vertex) are
included.
my $tcg = Graph::TransitiveClosure−>new($g,
reflexive => 1);
my $tcg = Graph::TransitiveClosure−>new($g,
reflexive => 0);
# is_reachable(u, v) is always reflexive.
$tcg−>is_reachable($u, $v)
# You can check any graph for transitivity.
$g−>is_transitive()
my $tcg = Graph::TransitiveClosure−>new($g,
path_length => 1);
$tcg−>path_length($u, $v)
# path_vertices is on by default so this is a no−op.
my $tcg = Graph::TransitiveClosure−>new($g,
path_vertices => 1);
$tcg−>path_vertices($u, $v)
# see how many paths exist from $u to $v
my $tcg = Graph::TransitiveClosure−>new($g,
path_count => 1);
$tcg−>path_length($u, $v)
# Both path_length and path_vertices.
my $tcg = Graph::TransitiveClosure−>new($g, path
=> 1);
$tcg−>path_vertices($u, $v)
$tcg−>length($u, $v)
my $tcg = Graph::TransitiveClosure−>new($g,
attribute_name => 'length');
$tcg−>path_length($u, $v)
You can use "Graph::TransitiveClosure" to compute the transitive closure graph 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.
For further documentation, see the Graph::TransitiveClosure::Matrix.
new($g, %opt)
Construct a new transitive closure object. Note that strictly speaking the returned object is not a graph; it is a graph plus other stuff. But you should be able to use it as a graph plus a couple of methods inherited from the Graph::TransitiveClosure::Matrix class.
These are only
the methods ’native’ to the class: see
Graph::TransitiveClosure::Matrix for more.
is_transitive($g)
Return true if the Graph $g is transitive.
transitive_closure_matrix
Return the transitive closure matrix of the transitive closure object.