—

              
package Graph::TransitiveClosure;
use strict;
use warnings;
# COMMENT THESE OUT FOR TESTING AND PRODUCTION.
# $SIG{__DIE__ } = \&Graph::__carp_confess;
# $SIG{__WARN__} = \&Graph::__carp_confess;
use base 'Graph';
use Graph::TransitiveClosure::Matrix;
sub _G () { Graph::_G() }
sub new {
    my ($class, $g, %opt) = @_;
    Graph::__carp_confess(__PACKAGE__."->new given non-Graph '$g'")
        if !(ref $g and $g->isa('Graph'));
    %opt = (path_vertices => 1) unless %opt;
    # No delete $opt{ attribute_name } since we need to pass it on.
    my $attr = exists $opt{ attribute_name } ? $opt{ attribute_name } : Graph::_defattr();
    $opt{ reflexive } = 1 unless exists $opt{ reflexive };
    my $tcg = $g->new(
        multiedged => 0,
        ($opt{ reflexive } ? (vertices => [$g->vertices]) : ()),
    );
    my $tcm = $g->_check_cache('transitive_closure_matrix', [],
        \&_transitive_closure_matrix_compute, %opt);
    my $tcm00 = $tcm->[0][0]; # 0=am, 0=bitmatrix
    my $tcm01 = $tcm->[0][1]; #     , 1=hash mapping v-name to the offset into dm data structures (in retval of $g->vertices)
    my @edges;
    for my $u ($tcm->vertices) {
        my $tcm00i = $tcm00->[ $tcm01->{ $u } ];
        for my $v ($tcm->vertices) {
            next if $u eq $v && ! $opt{ reflexive };
            my $j = $tcm01->{ $v };
            push @edges, [$u, $v] if vec($tcm00i, $j, 1);
                                      # $tcm->is_transitive($u, $v)
                                      # $tcm->[0]->get($u, $v)
        }
    }
    $tcg->add_edges(@edges);
    $tcg->set_graph_attribute('_tcm', [ $g->[ _G ], $tcm ]);
    bless $tcg, $class;
}
sub _transitive_closure_matrix_compute {
    Graph::TransitiveClosure::Matrix->new(@_);
}
sub is_transitive {
    my $g = shift;
    $g->expect_no_args(@_);
    Graph::TransitiveClosure::Matrix::is_transitive($g);
}
sub transitive_closure_matrix {
    $_[0]->get_graph_attribute('_tcm')->[1];
}
1;
HideShow 91 lines of Pod
__END__
=pod
=head1 NAME
Graph::TransitiveClosure - create and query transitive closure of graph
=head1 SYNOPSIS
    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)
=head1 DESCRIPTION
You can use C<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 C<is_reachable()> and
C<is_transitive()> methods, and the paths by using the
C<path_length()> and C<path_vertices()> methods.
For further documentation, see the L<Graph::TransitiveClosure::Matrix>.
=head2 Class Methods
=over 4
=item 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.
=back
=head2 Object Methods
These are only the methods 'native' to the class: see
L<Graph::TransitiveClosure::Matrix> for more.
=over 4
=item is_transitive($g)
Return true if the Graph $g is transitive.
=item transitive_closure_matrix
Return the transitive closure matrix of the transitive closure object.
=back
=cut