Algorithm::Tree::NCA 0.01

Algorithm::Tree::NCA is a constant time retrieval of nearest common ancestor.

SYNOPSIS

use Algorithm::Tree::NCA;

my $tree = ...;
my $nca = new Algorithm::Tree::NCA(-tree => $tree);

my $x = $tree->get_node(...);
my $y = $tree->get_node(...);
my $z = $nca->nca($x,$y);

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.

- A node number assigned to the node in a pre-order fashion
- A number to identify the run of the node ("ALGORITHM")
- The leader for each run, which should be retrievable through its node number
- A magic number ("ALGORITHM")
- The parent node for each node
- The maximum number assigned to a any node in the subtree

All data above, with the exception of the node number, is stored in an array inside the Algorithm::Tree::NCA object.

The node number has to be stored in the actual tree node in some manner (alternative solutions would be to slow to give constant-time retrieval), which requires a set method and a get method for the nodes. Since the most common case is using hashes to represent nodes, there are default implementations of the set and get methods.

The default set method is:

sub _set_method {
my($node,$value) = @_;

$node->{_nca_number} = $value;
}
and the default get method is:
sub _get_method {
my($node) = @_;

return $node->{_nca_number};
}

If have chosen another representation of your nodes, you can provide alternative set and get methods by using the -set and -get options when creating the Algorithm::Tree::NCA object.