.\" Automatically generated by Pod::Man 4.14 (Pod::Simple 3.43)
.\"
.\" Standard preamble:
.\" ========================================================================
.de Sp \" Vertical space (when we can't use .PP)
.if t .sp .5v
.if n .sp
..
.de Vb \" Begin verbatim text
.ft CW
.nf
.ne \\$1
..
.de Ve \" End verbatim text
.ft R
.fi
..
.\" Set up some character translations and predefined strings.  \*(-- will
.\" give an unbreakable dash, \*(PI will give pi, \*(L" will give a left
.\" double quote, and \*(R" will give a right double quote.  \*(C+ will
.\" give a nicer C++.  Capital omega is used to do unbreakable dashes and
.\" therefore won't be available.  \*(C` and \*(C' expand to `' in nroff,
.\" nothing in troff, for use with C<>.
.tr \(*W-
.ds C+ C\v'-.1v'\h'-1p'\s-2+\h'-1p'+\s0\v'.1v'\h'-1p'
.ie n \{\
.    ds -- \(*W-
.    ds PI pi
.    if (\n(.H=4u)&(1m=24u) .ds -- \(*W\h'-12u'\(*W\h'-12u'-\" diablo 10 pitch
.    if (\n(.H=4u)&(1m=20u) .ds -- \(*W\h'-12u'\(*W\h'-8u'-\"  diablo 12 pitch
.    ds L" ""
.    ds R" ""
.    ds C` ""
.    ds C' ""
'br\}
.el\{\
.    ds -- \|\(em\|
.    ds PI \(*p
.    ds L" ``
.    ds R" ''
.    ds C`
.    ds C'
'br\}
.\"
.\" Escape single quotes in literal strings from groff's Unicode transform.
.ie \n(.g .ds Aq \(aq
.el       .ds Aq '
.\"
.\" If the F register is >0, we'll generate index entries on stderr for
.\" titles (.TH), headers (.SH), subsections (.SS), items (.Ip), and index
.\" entries marked with X<> in POD.  Of course, you'll have to process the
.\" output yourself in some meaningful fashion.
.\"
.\" Avoid warning from groff about undefined register 'F'.
.de IX
..
.nr rF 0
.if \n(.g .if rF .nr rF 1
.if (\n(rF:(\n(.g==0)) \{\
.    if \nF \{\
.        de IX
.        tm Index:\\$1\t\\n%\t"\\$2"
..
.        if !\nF==2 \{\
.            nr % 0
.            nr F 2
.        \}
.    \}
.\}
.rr rF
.\" ========================================================================
.\"
.IX Title "Graph::TransitiveClosure::Matrix 3pm"
.TH Graph::TransitiveClosure::Matrix 3pm "2023-10-31" "perl v5.36.0" "User Contributed Perl Documentation"
.\" For nroff, turn off justification.  Always turn off hyphenation; it makes
.\" way too many mistakes in technical documents.
.if n .ad l
.nh
.SH "NAME"
Graph::TransitiveClosure::Matrix \- create and query transitive closure of graph
.SH "SYNOPSIS"
.IX Header "SYNOPSIS"
.Vb 2
\&    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 => \*(Aqlength\*(Aq);
\&    my $n = $tcm\->path_length($u, $v)
\&
\&    my @v = $tcm\->vertices
.Ve
.SH "DESCRIPTION"
.IX Header "DESCRIPTION"
You can use \f(CW\*(C`Graph::TransitiveClosure::Matrix\*(C'\fR 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 \f(CW\*(C`is_reachable()\*(C'\fR and
\&\f(CW\*(C`is_transitive()\*(C'\fR methods, and the paths by using the
\&\f(CW\*(C`path_length()\*(C'\fR and \f(CW\*(C`path_vertices()\*(C'\fR methods.
.PP
If you modify the graph after computing its transitive closure,
the transitive closure and minimum paths may become invalid.
.SH "Methods"
.IX Header "Methods"
.SS "Class Methods"
.IX Subsection "Class Methods"
.IP "new($g)" 4
.IX Item "new($g)"
Construct the transitive closure matrix of the graph \f(CW$g\fR.
.IP "new($g, options)" 4
.IX Item "new($g, options)"
Construct the transitive closure matrix of the graph \f(CW$g\fR with options
as a hash. The known options are
.RS 4
.ie n .IP """attribute_name"" => \fIattribute_name\fR" 8
.el .IP "\f(CWattribute_name\fR => \fIattribute_name\fR" 8
.IX Item "attribute_name => attribute_name"
By default the edge attribute used for distance is \f(CW\*(C`weight\*(C'\fR.  You can
change that by giving another attribute name with the \f(CW\*(C`attribute_name\*(C'\fR
attribute to the \fBnew()\fR constructor.
.IP "reflexive => boolean" 8
.IX Item "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 \f(CW\*(C`reflexive\*(C'\fR option.
.IP "path => boolean" 8
.IX Item "path => boolean"
If set true, sets \f(CW\*(C`path_length\*(C'\fR and \f(CW\*(C`path_vertices\*(C'\fR. If either of
those are true (and \f(CW\*(C`path_vertices\*(C'\fR is by default), then both are
calculated.
.IP "path_length => boolean" 8
.IX Item "path_length => boolean"
By default \*(L"false\*(R", but see above as overridden by default
\&\f(CW\*(C`path_vertices\*(C'\fR being true. If calculated,
they can be retrieved using the \fBpath_length()\fR method.
.IP "path_vertices => boolean" 8
.IX Item "path_vertices => boolean"
By default the paths are computed, with the boolean transitivity,
they can be retrieved using the \fBpath_vertices()\fR method.
.IP "path_count => boolean" 8
.IX Item "path_count => boolean"
As an alternative to setting \f(CW\*(C`path_length\*(C'\fR, if this is true then the
matrix will store the quantity of paths between the two vertices. This
is still retrieved using the \fBpath_length()\fR method. The path vertices
will not be available. You should probably only use this on a \s-1DAG,\s0
and not with \f(CW\*(C`reflexive\*(C'\fR.
.RE
.RS 4
.RE
.SS "Object Methods"
.IX Subsection "Object Methods"
.ie n .IP "is_reachable($u, $v)" 4
.el .IP "is_reachable($u, \f(CW$v\fR)" 4
.IX Item "is_reachable($u, $v)"
Return true if the vertex \f(CW$v\fR is reachable from the vertex \f(CW$u\fR,
or false if not.
.ie n .IP "path_length($u, $v)" 4
.el .IP "path_length($u, \f(CW$v\fR)" 4
.IX Item "path_length($u, $v)"
Return the minimum path length from the vertex \f(CW$u\fR to the vertex \f(CW$v\fR,
or undef if there is no such path.
.ie n .IP "path_vertices($u, $v)" 4
.el .IP "path_vertices($u, \f(CW$v\fR)" 4
.IX Item "path_vertices($u, $v)"
Return the minimum path (as a list of vertices) from the vertex \f(CW$u\fR to
the vertex \f(CW$v\fR, or an empty list if there is no such path, \s-1OR\s0 also return
an empty list if \f(CW$u\fR equals \f(CW$v\fR.
.ie n .IP "has_vertices($u, $v, ...)" 4
.el .IP "has_vertices($u, \f(CW$v\fR, ...)" 4
.IX Item "has_vertices($u, $v, ...)"
Return true if the transitive closure matrix has all the listed vertices,
false if not.
.ie n .IP "is_transitive($u, $v)" 4
.el .IP "is_transitive($u, \f(CW$v\fR)" 4
.IX Item "is_transitive($u, $v)"
Return true if the vertex \f(CW$v\fR is transitively reachable from the vertex \f(CW$u\fR,
false if not.
.IP "vertices" 4
.IX Item "vertices"
Return the list of vertices in the transitive closure matrix.
.ie n .IP "path_successor($u, $v)" 4
.el .IP "path_successor($u, \f(CW$v\fR)" 4
.IX Item "path_successor($u, $v)"
Return the successor of vertex \f(CW$u\fR in the transitive closure path towards
vertex \f(CW$v\fR.
.ie n .IP "all_paths($u, $v)" 4
.el .IP "all_paths($u, \f(CW$v\fR)" 4
.IX Item "all_paths($u, $v)"
Return list of array-refs with all the paths from \f(CW$u\fR to \f(CW$v\fR. Will ignore
self-loops.
.SH "RETURN VALUES"
.IX Header "RETURN VALUES"
For \fBpath_length()\fR the return value will be the sum of the appropriate
attributes on the edges of the path, \f(CW\*(C`weight\*(C'\fR by default.  If no
attribute has been set, one (1) will be assumed.
.PP
If you try to ask about vertices not in the graph, undefs and empty
lists will be returned.
.SH "ALGORITHM"
.IX Header "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.
.SH "SEE ALSO"
.IX Header "SEE ALSO"
Graph::AdjacencyMatrix
.SH "AUTHOR AND COPYRIGHT"
.IX Header "AUTHOR AND COPYRIGHT"
Jarkko Hietaniemi \fIjhi@iki.fi\fR
.SH "LICENSE"
.IX Header "LICENSE"
This module is licensed under the same terms as Perl itself.