| Name : perl-Algorithm-Tree-NCA
| |
| Version : 0.02
| Vendor : obs://build_opensuse_org/devel:languages:perl
|
| Release : 8.65
| Date : 2024-08-05 19:17:29
|
| Group : Development/Libraries/Perl
| Source RPM : perl-Algorithm-Tree-NCA-0.02-8.65.src.rpm
|
| Size : 0.02 MB
| |
| Packager : (none)
| |
| Summary : Constant time retrieval of I< Nearest Common Ancestor>
|
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.
* -
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) = AATT_;
$node->{\'_nca_number\'} = $value;
}
and the default get method is:
sub _get_method {
my($node) = AATT_;
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.
|
RPM found in directory: /packages/linux-pbone/ftp5.gwdg.de/pub/opensuse/repositories/devel:/languages:/perl:/CPAN-A/openSUSE_Tumbleweed/noarch |
