Algorithm-Tree-NCA
view release on metacpan or search on metacpan
Changes
Release
Makefile.PL
MANIFEST
NCA.pm
README
e/timing.pl
e/execution.log
t/preprocess.t
t/basic.t
t/random.t
META.yml Module meta-data (added by MakeMaker)
$o{-get} = \&_get_method unless defined $o{-get};
$o{-set} = \&_set_method unless defined $o{-set};
my $self = fields::new($class);
$self->{_get} = $o{'-get'}; # Get method to use
$self->{_set} = $o{'-set'}; # Set method to use
$self->{_data} = []; # Array of node data
# Preprocess the tree if there is one supplied
$self->preprocess($o{-tree}) if exists $o{-tree};
return $self;
}
sub _get ($$) {
my($self,$node) = @_;
$self->{_get}->($node);
}
sub _set ($$$) {
$v |= $v >> 16;
return $v - ($v >> 1);
}
sub _data ($$) {
my($self,$node) = @_;
return $self->{_data}->[$self->_get($node)];
}
sub preprocess ($$) {
my($self,$root) = @_;
# Enumeration phase
$self->_enumerate($root, 1);
# Computing magic number and leaders
$self->_compute_magic($root, $self->_data($root), 0);
}
# Enumerate each node of the tree with a number v and compute the run
my $nyd = $self->_closest($yd,$j);
# 4. If nx < ny then z is nx, else z is ny
if ($nxd->{_number} < $nyd->{_number}) {
return $nxd->{_node};
} else {
return $nyd->{_node};
}
}
# Autoload methods go after =cut, and are processed by the autosplit program.
1;
__END__
=head1 NAME
Algorithm::Tree::NCA - Constant time retrieval of I<Nearest Common Ancestor>
=head1 SYNOPSIS
my $nca = new Algorithm::Tree::NCA(-tree => $tree);
my $x = $tree->get_node(...);
my $y = $tree->get_node(...);
my $z = $nca->nca($x,$y);
=head1 DESCRIPTION
This package provides constant-time retrieval of the Nearest Common
Ancestor (NCA) of nodes in a tree. The implementation is based on the
algorithm by Harel and which can, after linear-time preprocessing,
retrieve the nearest common ancestor of two nodes in constant time.
To implement the algorithm it is necessary to store some data for each
node in the tree.
=over 4
=item -
A I<node number> assigned to the node in a pre-order fashion
If have chosen another representation of your nodes, you can provide
alternative set and get methods by using the B<-set> and B<-get>
options when creating the C<Algorithm::Tree::NCA> object.
=head1 CLASS AND OBJECT METHODS
=head1 EXAMPLES
=head2 ALGORITHM
This section describes the algorithm used for preprocessing and for
nearest common ancestor retrieval. It does not provide any intuition
to I<why> the algorithm works, just a description how it works. For
the algorithm description, it is assumed that the nodes themself
contain all necessary information. The algorithm is described in a
Pascal-like fashion. For detailed information about the algorithm,
please have a look in [1] or [2].
The I<height> of a non-zero integer is the number of zeros at the
right end of the integer. The I<least significant set bit> (LSSB) of a
non-zero number is the the number with only the least significant bit
-------- -------- ------
01001101 00000001 0
01001100 00000100 2
Important to note here is that for numbers I<i> and I<j>, I<height(i)
E<lt> height(j)> if and only if I<LSSB(i) E<lt> LSSB(j)>, which means
that we can replace a test of I<height(i) E<lt> height(j)> with
I<LSSB(i) E<lt> LSSB(j)>. Since I<LSSB(i)> is easier to compute, this
will speed up the computation.
=head2 Preprocessing the tree
Preprocessing the tree requires the computation of three numbers: the
I<node number>, the I<run>, and a I<magic> number. It also requires
computation of the I<leader> of each run. These computations are done
in two recursive descents and ascents of the tree.
Procedure Preprocess(root:Node)
Var x,y : Integer; (* Dummy variables *)
Begin
(x,y) := Enumerate(root,nil,1);
ComputeMagic(root,root,0);
End;
In the first phase, we enumerate the tree, compute the I<run> for each
node, the I<max> number assigned to a node in the subtree, and also
the I<parent> of each node. If the parent is already available through
other means, that part is redundant. The run of a node is the number
Announcing the release of Perl Module Algorithm::Tree::NCA Version 0.01
Algorithm::Tree::NCA - Constant-time retrieval of nearest common ancestor
This package provides constant-time retrieval of the Nearest Common
Ancestor (NCA) of nodes in a tree. The implementation is based on an
algorithm by Harel and Tarjan which can, after linear-time (and
linear-space) preprocessing, retrieve the nearest common ancestor of
two nodes in constant time.
This release also contains a comparison between this algorithm and the
naive straight-forward implementation of the same algorithm with
linear complexity but with a low constant factor.
Module Entry
6) Data Types and Data Type Utilities (see also Database Interfaces)
e/timing.pl view on Meta::CPAN
foreach my $count (@counts) {
my($root, $nodesref) = make_tree($seed, $size);
{
my $before = new Benchmark;
for (1..$Times) {
my $nca = new Algorithm::Tree::NCA;
my $z;
my $i = 0;
my $cnt = $count;
$nca->preprocess($root);
while ($cnt-- > 0) {
my $x = $nodesref->[$i];
$i = ($i + 23) % (@$nodesref - 1);
my $y = $nodesref->[$i];
$z = $nca->nca($x,$y);
}
}
my $after = new Benchmark;
$T{'tarjan'}->[$size][$count]
[undef, 1, 1, 1, 1, 5, 5, 5, 5, 5, 5], # Node 5
[undef, 1, 1, 1, 1, 5, 6, 5, 5, 5, 5], # Node 6
[undef, 1, 1, 1, 1, 5, 5, 7, 5, 5, 5], # Node 7
[undef, 1, 1, 1, 1, 5, 5, 5, 8, 8, 8], # Node 8
[undef, 1, 1, 1, 1, 5, 5, 5, 8, 9, 8], # Node 9
[undef, 1, 1, 1, 1, 5, 5, 5, 8, 8,10]]; # Node 10
ok(1);
{
my $nca = new Algorithm::Tree::NCA;
$nca->preprocess($Tree);
my $bad = 0;
my @Nodes;
$Tree->make_preorder_list(\@Nodes);
foreach my $x (@Nodes) {
foreach my $y (@Nodes) {
my $xn = $nca->_data($x)->{_number};
my $yn = $nca->_data($y)->{_number};
my $p = $nca->nca($x,$y);
t/preprocess.t view on Meta::CPAN
Node->new()),
Node->new(Node->new(),
Node->new(),
Node->new(Node->new(),
Node->new())));
ok(2);
use Data::Dumper;
my $nca = new Algorithm::Tree::NCA;
$nca->preprocess($Tree);
# Check that the leader is correct
{
my $bad = 0;
foreach my $d (@{$nca->{_data}}) {
if (defined($d)
&& ($Leader[$d->{_number}] != $d->{_leader}->{_number}))
{
++$bad;
}
sub nr { return $_[0]->{_number} }
# print "Made a tree\n";
# $root->display(0);
foreach my $a (@cases) {
my($seed,$count) = @$a;
my($root, $nodesref) = make_tree($seed, $count);
my $nca = new Algorithm::Tree::NCA;
$nca->preprocess($root);
my $bad = 0;
foreach my $x (@$nodesref) {
foreach my $y (@$nodesref) {
my $z = $nca->nca($x,$y);
my $n = $root->naive_nca($x,$y);
++$bad unless $z == $n;
}
}
ok($bad,0);
( run in 0.391 second using v1.01-cache-2.11-cpan-8d75d55dd25 )