Algorithm::Tree::NCA Algorithm::Tree::NCA is a constant time retrieval of Nearest Common Ancestor.
Download

Algorithm::Tree::NCA Ranking & Summary

Algorithm::Tree::NCA Tags

time Perl module retrieval time retrieval common ancestor

Algorithm::Tree::NCA Description

Algorithm::Tree::NCA is a constant time retrieval of Nearest Common Ancestor. 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 subtreeAll 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. Requirements: · Perl

Algorithm::Tree::NCA Related Software