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 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.

           path => boolean
                   If set true, sets "path_length" and "path_vertices". If either of those are
                   true (and "path_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 with
                   "reflexive".

   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 array-refs with all the paths from $u to $v. Will ignore self-loops.

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.