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 CWGraph::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 CWis_reachable() and CWis_transitive() methods, and the paths by using the CWpath_length() and CWpath_vertices() methods.

If you modify the graph after computing its transitive closure, the transitive closure and minimum paths may become invalid.

new($g)

Construct the transitive closure matrix of the graph CW$g.

new($g, options)

Construct the transitive closure matrix of the graph CW$g with options as a hash. The known options are By default the edge attribute used for distance is CWw. You can change that by giving another attribute name with the CWattribute_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 CWreflexive option. NOTE: this behaviour has changed from Graph 0.2xxx: transitive closure graphs were by default reflexive.

path_length => 1

By default the path lengths are not computed, only the boolean transitivity. By using true for CWpath_length also the path lengths will be computed, they can be retrieved using the path_length() method.

path_vertices => 1

By default the paths are not computed, only the boolean transitivity. By using true for CWpath_vertices also the paths will be computed, they can be retrieved using the path_vertices() method.

Return true if the vertex CW$v is reachable from the vertex CW$u, or false if not. Return the minimum path length from the vertex CW$u to the vertex CW$v, or undef if there is no such path. Return the minimum path (as a list of vertices) from the vertex CW$u to the vertex CW$v, or an empty list if there is no such path, OR also return an empty list if CW$u equals CW$v. Return true if the transitive closure matrix has all the listed vertices, false if not. Return true if the vertex CW$v is transitively reachable from the vertex CW$u, false if not.

vertices

Return the list of vertices in the transitive closure matrix.

path_predecessor

Return the predecessor of vertex CW$v in the transitive closure path going back to vertex CW$u.

For path_length() the return value will be the sum of the appropriate attributes on the edges of the path, CWweight 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.

Graph::AdjacencyMatrix

Jarkko Hietaniemi jhi@iki.fi

This module is licensed under the same terms as Perl itself.