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.

perl v5.20.2                                       2009-01-17              Graph::TransitiveClosure::Matrix(3pm)