Algorithm-Tree-NCA

 view release on metacpan or  search on metacpan

NCA.pm  view on Meta::CPAN

#
# This program is free software; you can redistribute it and/or modify
# it under the same terms as Perl itself. 

package Algorithm::Tree::NCA::Data;

use 5.006;
use strict;
use warnings;

use fields qw(_run _magic _number _parent _leader _max _node);

sub new ($%) {
    my $class = shift;
    # Default values first, then the provided parameters
    my %args = (_run => 0,        # Corresponds to I(v)
                _magic => 0,      # Corresponds to A_v
                _max => 0,        # Maximum number assigned to subtree
                _number => 0,     # The DFS number assigned to this node
                _parent => undef, # The parent node data for this node
                _leader => undef, # The leader node data for this node
                _node => undef,   # The node that the data is for
                @_);

    my $self = fields::new($class);
    @$self{keys %args} = values %args;
    return $self;
}

package Algorithm::Tree::NCA;

NCA.pm  view on Meta::CPAN

    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
# I(v) for each node. Also set the parent for each node.
sub _enumerate ($$$;$) {
    my($self,$node,$number,$parent) = @_;

    my $data = Algorithm::Tree::NCA::Data
	->new(_node => $node,
	      _run => $number, 
	      _parent => $parent,
	      _number => $number);

    $self->{_data}->[$number] = $data;

    $self->_set($node,$number);

    my $run = $number++;
    
    for my $c ($node->children()) {
	($number, $run) = $self->_enumerate($c, $number, $data);

NCA.pm  view on Meta::CPAN

    # c. Find the position k of the left-most 1-bit in A_x that is to
    #    the right of position j.
    my $k = _mssb(($j - 1) & $xd->{_magic});

    #    Form the number u consisting of the bits of I(x) to the left
    #    of position k, followed by a 1-bit in position k, followed by
    #    all zeroes. (u will be I(w))
    my $u = ~(($k - 1) | $k) & $xd->{_run} | $k;

    #    Look up node L(I(w)), which must be node w. nx is then the parent
    #    of node w.
    my $wd = $self->{_data}->[$u]->{_leader};

    return $wd->{_parent};
    
}

sub nca ($$$) {
    my($self,$x,$y) = @_;
    my $xd = $self->_data($x);
    my $yd = $self->_data($y);

    if ($xd->{_number} == $yd->{_number}) {
	return $x;

NCA.pm  view on Meta::CPAN

A number to identify the I<run> of the node (L<"ALGORITHM">)

=item -
The I<leader> for each run, which should be retrievable through its
node number

=item -
A I<magic> number (L<"ALGORITHM">)

=item -
The I<parent> node for each node

=item -
The I<maximum> number assigned to a any node in the subtree

=back

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

The node number has to be stored in the actual tree node in some

NCA.pm  view on Meta::CPAN

  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
of the node in the subtree with the largest height.

  Function Enumerate(node,parent:Node; num:Integer) : (Integer,Integer)
  Var run : Integer;
  Begin
      node.parent := parent;
      node.number := num;
      node.run := num;

      run := num;
      num := num + 1;

      Foreach child in node.children Do
	  (num,run) := Enumerate(child,node,num);
	  If height(run) > height(node.run) Then
	      node.run := run;

NCA.pm  view on Meta::CPAN

To find the node closest to a node I<n> but on the same run as the NCA
I<z> we need the I<j> supplied by the C<NCA> function above.

  Function Closest(n:Node; j:Integer) : Node;
  Begin
    l := LSSB(n.magic);
    If l = j Then Return x
    k := MSSB((j - 1) AND x.magic);
    u := ((NOT ((k - 1) OR k)) AND x.run) OR k
    w := Leader(u);
    Return w.parent;  (* z = w.parent *)
  End;

=head1 REFERENCES

=over 4

=item [1] I<Fast algorithms for finding nearest common ancestor> by
          D. Harel and R. E. Tarjan.

=item [2] I<On finding lowest common ancestor: simplifications and