Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
Public Types | Public Member Functions | Private Types | Private Member Functions | Private Attributes | Static Private Attributes | List of all members
Aleph::Gen_Binary_Lifting_LCA< GT, SA > Class Template Reference
Graphs

LCA via binary lifting on a rooted tree. More...

#include <LCA.H>

Collaboration diagram for Aleph::Gen_Binary_Lifting_LCA< GT, SA >:
[legend]

Public Types

using Node = typename GT::Node
 

Public Member Functions

 Gen_Binary_Lifting_LCA (const GT &g, Node *root, SA sa=SA())
 Construct from graph + explicit root.
 
 Gen_Binary_Lifting_LCA (const GT &g, SA sa=SA())
 Construct using the first graph node as root.
 
size_t size () const noexcept
 Total number of nodes in the tree.
 
bool is_empty () const noexcept
 Returns true if the tree has no nodes.
 
Node * root () const noexcept
 Returns the root node of the tree.
 
size_t root_id () const noexcept
 Returns the internal ID of the root node.
 
size_t num_levels () const noexcept
 Returns the number of levels in the jump table ( \(\lceil \log_2 n \rceil \)).
 
Node * node_of (const size_t id) const
 Map an internal ID [0, n-1] back to a Node pointer.
 
size_t id_of (const Node *node) const
 Map a Node pointer to its internal ID [0, n-1].
 
size_t depth_of_id (const size_t id) const
 Distance from root to node by ID.
 
size_t depth_of (const Node *node) const
 Distance from root to node.
 
size_t parent_id (const size_t id) const
 Parent ID of node id, or NONE if root.
 
Node * parent_of (const Node *node) const
 Parent of node, or nullptr if root.
 
bool is_ancestor_id (const size_t u, const size_t v) const
 Returns true if node u is an ancestor of v (or u == v).
 
bool is_ancestor (const Node *u, const Node *v) const
 Returns true if node u is an ancestor of v (or u == v).
 
size_t kth_ancestor_id (const size_t id, const size_t k) const
 k-th ancestor by id in O(log n).
 
Node * kth_ancestor (const Node *node, const size_t k) const
 k-th ancestor by node pointer in O(log n).
 
size_t lca_id (size_t u, size_t v) const
 LCA query by node ids in O(log n).
 
Node * lca (const Node *u, const Node *v) const
 LCA query by node pointers in O(log n).
 
size_t distance_id (const size_t u, const size_t v) const
 Number of edges on the path between two ids in O(log n).
 
size_t distance (const Node *u, const Node *v) const
 Number of edges on the path between two nodes in O(log n).
 

Private Types

using Topology = lca_detail::Rooted_Tree_Data< GT, SA >
 

Private Member Functions

size_t n () const noexcept
 
size_t & up_at (const size_t k, const size_t v) noexcept
 
size_t up_at (const size_t k, const size_t v) const noexcept
 
void ensure_not_empty (const char *where) const
 
void build_jump_table ()
 
size_t lift (size_t v, size_t delta) const
 

Private Attributes

Topology topology_
 
size_t levels_ = 0
 
Array< size_t > up_
 

Static Private Attributes

static constexpr size_t NONE = Topology::NONE
 

Detailed Description

template<class GT, class SA = Dft_Show_Arc<GT>>
class Aleph::Gen_Binary_Lifting_LCA< GT, SA >

LCA via binary lifting on a rooted tree.

Binary lifting is a technique that uses a jump table (sparse table) to find ancestors efficiently. For each node, we precompute its 1st, 2nd, 4th, 8th, ... \(2^k\)-th ancestor.

To find the LCA of \(u\) and \(v\):

  1. Lift the deeper node until it is at the same depth as the other.
  2. If they are now the same node, that is the LCA.
  3. Otherwise, jump upwards by the largest possible powers of 2 such that the resulting nodes are still different. The parent of the final nodes is the LCA.

Build time is \(O(n \log n)\), each LCA query costs \(O(\log n)\).

Template Parameters
GTGraph type (List_Graph, List_SGraph, Array_Graph).
SAArc filter type (default: Dft_Show_Arc<GT>).

Definition at line 439 of file LCA.H.

Member Typedef Documentation

◆ Node

template<class GT , class SA = Dft_Show_Arc<GT>>
using Aleph::Gen_Binary_Lifting_LCA< GT, SA >::Node = typename GT::Node

Definition at line 442 of file LCA.H.

◆ Topology

template<class GT , class SA = Dft_Show_Arc<GT>>
using Aleph::Gen_Binary_Lifting_LCA< GT, SA >::Topology = lca_detail::Rooted_Tree_Data<GT, SA>
private

Definition at line 445 of file LCA.H.

Constructor & Destructor Documentation

◆ Gen_Binary_Lifting_LCA() [1/2]

template<class GT , class SA = Dft_Show_Arc<GT>>
Aleph::Gen_Binary_Lifting_LCA< GT, SA >::Gen_Binary_Lifting_LCA ( const GT &  g,
Node *  root,
SA  sa = SA() 
)
inline

Construct from graph + explicit root.

The constructor validates that the filtered graph is a tree.

Parameters
[in]gRooted tree topology (filtered by sa).
[in]rootRoot node pointer (must belong to g).
[in]saArc filter.
Exceptions
ah_domain_errorif the filtered graph is not a tree.

Definition at line 511 of file LCA.H.

References Aleph::Gen_Binary_Lifting_LCA< GT, SA >::build_jump_table().

◆ Gen_Binary_Lifting_LCA() [2/2]

template<class GT , class SA = Dft_Show_Arc<GT>>
Aleph::Gen_Binary_Lifting_LCA< GT, SA >::Gen_Binary_Lifting_LCA ( const GT &  g,
SA  sa = SA() 
)
inline

Construct using the first graph node as root.

Parameters
[in]gRooted tree topology (filtered by sa).
[in]saArc filter.

Definition at line 522 of file LCA.H.

References Aleph::Gen_Binary_Lifting_LCA< GT, SA >::build_jump_table().

Member Function Documentation

◆ build_jump_table()

template<class GT , class SA = Dft_Show_Arc<GT>>
void Aleph::Gen_Binary_Lifting_LCA< GT, SA >::build_jump_table ( )
inlineprivate

Definition at line 470 of file LCA.H.

References Aleph::Array< T >::create(), Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Binary_Lifting_LCA< GT, SA >::is_empty(), k, Aleph::Gen_Binary_Lifting_LCA< GT, SA >::levels_, Aleph::Gen_Binary_Lifting_LCA< GT, SA >::n(), Aleph::Gen_Binary_Lifting_LCA< GT, SA >::NONE, Aleph::lca_detail::Rooted_Tree_Data< GT, SA >::parent(), Aleph::Gen_Binary_Lifting_LCA< GT, SA >::topology_, Aleph::Gen_Binary_Lifting_LCA< GT, SA >::up_, and Aleph::Gen_Binary_Lifting_LCA< GT, SA >::up_at().

Referenced by Aleph::Gen_Binary_Lifting_LCA< GT, SA >::Gen_Binary_Lifting_LCA(), and Aleph::Gen_Binary_Lifting_LCA< GT, SA >::Gen_Binary_Lifting_LCA().

◆ depth_of()

template<class GT , class SA = Dft_Show_Arc<GT>>
size_t Aleph::Gen_Binary_Lifting_LCA< GT, SA >::depth_of ( const Node *  node) const
inline

Distance from root to node.

Definition at line 563 of file LCA.H.

References Aleph::Gen_Binary_Lifting_LCA< GT, SA >::depth_of_id(), and Aleph::Gen_Binary_Lifting_LCA< GT, SA >::id_of().

◆ depth_of_id()

template<class GT , class SA = Dft_Show_Arc<GT>>
size_t Aleph::Gen_Binary_Lifting_LCA< GT, SA >::depth_of_id ( const size_t  id) const
inline

Distance from root to node by ID.

Definition at line 556 of file LCA.H.

References Aleph::lca_detail::Rooted_Tree_Data< GT, SA >::depth(), Aleph::Gen_Binary_Lifting_LCA< GT, SA >::topology_, and Aleph::lca_detail::Rooted_Tree_Data< GT, SA >::validate_id().

Referenced by Aleph::Gen_Binary_Lifting_LCA< GT, SA >::depth_of().

◆ distance()

template<class GT , class SA = Dft_Show_Arc<GT>>
size_t Aleph::Gen_Binary_Lifting_LCA< GT, SA >::distance ( const Node *  u,
const Node *  v 
) const
inline

Number of edges on the path between two nodes in O(log n).

Definition at line 663 of file LCA.H.

References Aleph::Gen_Binary_Lifting_LCA< GT, SA >::distance_id(), and Aleph::Gen_Binary_Lifting_LCA< GT, SA >::id_of().

◆ distance_id()

template<class GT , class SA = Dft_Show_Arc<GT>>
size_t Aleph::Gen_Binary_Lifting_LCA< GT, SA >::distance_id ( const size_t  u,
const size_t  v 
) const
inline

Number of edges on the path between two ids in O(log n).

Definition at line 656 of file LCA.H.

References Aleph::lca_detail::Rooted_Tree_Data< GT, SA >::depth(), Aleph::Gen_Binary_Lifting_LCA< GT, SA >::lca_id(), and Aleph::Gen_Binary_Lifting_LCA< GT, SA >::topology_.

Referenced by Aleph::Gen_Binary_Lifting_LCA< GT, SA >::distance().

◆ ensure_not_empty()

template<class GT , class SA = Dft_Show_Arc<GT>>
void Aleph::Gen_Binary_Lifting_LCA< GT, SA >::ensure_not_empty ( const char *  where) const
inlineprivate

Definition at line 464 of file LCA.H.

References ah_domain_error_if, Aleph::divide_and_conquer_partition_dp(), and Aleph::Gen_Binary_Lifting_LCA< GT, SA >::is_empty().

Referenced by Aleph::Gen_Binary_Lifting_LCA< GT, SA >::lca_id().

◆ id_of()

template<class GT , class SA = Dft_Show_Arc<GT>>
size_t Aleph::Gen_Binary_Lifting_LCA< GT, SA >::id_of ( const Node *  node) const
inline

Map a Node pointer to its internal ID [0, n-1].

Definition at line 550 of file LCA.H.

References Aleph::lca_detail::Rooted_Tree_Data< GT, SA >::id_of(), and Aleph::Gen_Binary_Lifting_LCA< GT, SA >::topology_.

Referenced by Aleph::Gen_Binary_Lifting_LCA< GT, SA >::depth_of(), Aleph::Gen_Binary_Lifting_LCA< GT, SA >::distance(), Aleph::Gen_Binary_Lifting_LCA< GT, SA >::is_ancestor(), Aleph::Gen_Binary_Lifting_LCA< GT, SA >::kth_ancestor(), Aleph::Gen_Binary_Lifting_LCA< GT, SA >::lca(), and Aleph::Gen_Binary_Lifting_LCA< GT, SA >::parent_of().

◆ is_ancestor()

template<class GT , class SA = Dft_Show_Arc<GT>>
bool Aleph::Gen_Binary_Lifting_LCA< GT, SA >::is_ancestor ( const Node *  u,
const Node *  v 
) const
inline

Returns true if node u is an ancestor of v (or u == v).

Definition at line 589 of file LCA.H.

References Aleph::Gen_Binary_Lifting_LCA< GT, SA >::id_of(), and Aleph::Gen_Binary_Lifting_LCA< GT, SA >::is_ancestor_id().

◆ is_ancestor_id()

template<class GT , class SA = Dft_Show_Arc<GT>>
bool Aleph::Gen_Binary_Lifting_LCA< GT, SA >::is_ancestor_id ( const size_t  u,
const size_t  v 
) const
inline

Returns true if node u is an ancestor of v (or u == v).

Definition at line 583 of file LCA.H.

References Aleph::lca_detail::Rooted_Tree_Data< GT, SA >::is_ancestor(), and Aleph::Gen_Binary_Lifting_LCA< GT, SA >::topology_.

Referenced by Aleph::Gen_Binary_Lifting_LCA< GT, SA >::is_ancestor().

◆ is_empty()

template<class GT , class SA = Dft_Show_Arc<GT>>
bool Aleph::Gen_Binary_Lifting_LCA< GT, SA >::is_empty ( ) const
inlinenoexcept

Returns true if the tree has no nodes.

Definition at line 532 of file LCA.H.

References Aleph::lca_detail::Rooted_Tree_Data< GT, SA >::is_empty(), and Aleph::Gen_Binary_Lifting_LCA< GT, SA >::topology_.

Referenced by Aleph::Gen_Binary_Lifting_LCA< GT, SA >::build_jump_table(), and Aleph::Gen_Binary_Lifting_LCA< GT, SA >::ensure_not_empty().

◆ kth_ancestor()

template<class GT , class SA = Dft_Show_Arc<GT>>
Node * Aleph::Gen_Binary_Lifting_LCA< GT, SA >::kth_ancestor ( const Node *  node,
const size_t  k 
) const
inline

k-th ancestor by node pointer in O(log n).

Returns
Ancestor node, or nullptr if it does not exist.

Definition at line 612 of file LCA.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Binary_Lifting_LCA< GT, SA >::id_of(), k, Aleph::Gen_Binary_Lifting_LCA< GT, SA >::kth_ancestor_id(), Aleph::Gen_Binary_Lifting_LCA< GT, SA >::node_of(), and Aleph::Gen_Binary_Lifting_LCA< GT, SA >::NONE.

◆ kth_ancestor_id()

template<class GT , class SA = Dft_Show_Arc<GT>>
size_t Aleph::Gen_Binary_Lifting_LCA< GT, SA >::kth_ancestor_id ( const size_t  id,
const size_t  k 
) const
inline

k-th ancestor by id in O(log n).

Parameters
[in]idNode id.
[in]kNumber of steps up.
Returns
Ancestor id, or NONE if k > depth(id).

Definition at line 600 of file LCA.H.

References Aleph::lca_detail::Rooted_Tree_Data< GT, SA >::depth(), k, Aleph::Gen_Binary_Lifting_LCA< GT, SA >::lift(), Aleph::Gen_Binary_Lifting_LCA< GT, SA >::NONE, Aleph::Gen_Binary_Lifting_LCA< GT, SA >::topology_, and Aleph::lca_detail::Rooted_Tree_Data< GT, SA >::validate_id().

Referenced by Aleph::Gen_Binary_Lifting_LCA< GT, SA >::kth_ancestor().

◆ lca()

template<class GT , class SA = Dft_Show_Arc<GT>>
Node * Aleph::Gen_Binary_Lifting_LCA< GT, SA >::lca ( const Node *  u,
const Node *  v 
) const
inline

LCA query by node pointers in O(log n).

Definition at line 650 of file LCA.H.

References Aleph::Gen_Binary_Lifting_LCA< GT, SA >::id_of(), Aleph::Gen_Binary_Lifting_LCA< GT, SA >::lca_id(), and Aleph::Gen_Binary_Lifting_LCA< GT, SA >::node_of().

◆ lca_id()

template<class GT , class SA = Dft_Show_Arc<GT>>
size_t Aleph::Gen_Binary_Lifting_LCA< GT, SA >::lca_id ( size_t  u,
size_t  v 
) const
inline

LCA query by node ids in O(log n).

Definition at line 619 of file LCA.H.

References ah_runtime_error_unless, Aleph::lca_detail::Rooted_Tree_Data< GT, SA >::depth(), Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Binary_Lifting_LCA< GT, SA >::ensure_not_empty(), k, Aleph::Gen_Binary_Lifting_LCA< GT, SA >::levels_, Aleph::Gen_Binary_Lifting_LCA< GT, SA >::lift(), Aleph::Gen_Binary_Lifting_LCA< GT, SA >::NONE, Aleph::lca_detail::Rooted_Tree_Data< GT, SA >::parent(), Aleph::Gen_Binary_Lifting_LCA< GT, SA >::topology_, Aleph::Gen_Binary_Lifting_LCA< GT, SA >::up_at(), and Aleph::lca_detail::Rooted_Tree_Data< GT, SA >::validate_id().

Referenced by Aleph::Gen_Binary_Lifting_LCA< GT, SA >::distance_id(), and Aleph::Gen_Binary_Lifting_LCA< GT, SA >::lca().

◆ lift()

template<class GT , class SA = Dft_Show_Arc<GT>>
size_t Aleph::Gen_Binary_Lifting_LCA< GT, SA >::lift ( size_t  v,
size_t  delta 
) const
inlineprivate

Definition at line 493 of file LCA.H.

References Aleph::and, Aleph::divide_and_conquer_partition_dp(), k, Aleph::Gen_Binary_Lifting_LCA< GT, SA >::NONE, and Aleph::Gen_Binary_Lifting_LCA< GT, SA >::up_at().

Referenced by Aleph::Gen_Binary_Lifting_LCA< GT, SA >::kth_ancestor_id(), and Aleph::Gen_Binary_Lifting_LCA< GT, SA >::lca_id().

◆ n()

template<class GT , class SA = Dft_Show_Arc<GT>>
size_t Aleph::Gen_Binary_Lifting_LCA< GT, SA >::n ( ) const
inlineprivatenoexcept

Definition at line 452 of file LCA.H.

References Aleph::lca_detail::Rooted_Tree_Data< GT, SA >::size(), and Aleph::Gen_Binary_Lifting_LCA< GT, SA >::topology_.

Referenced by Aleph::Gen_Binary_Lifting_LCA< GT, SA >::build_jump_table(), Aleph::Gen_Binary_Lifting_LCA< GT, SA >::up_at(), and Aleph::Gen_Binary_Lifting_LCA< GT, SA >::up_at().

◆ node_of()

template<class GT , class SA = Dft_Show_Arc<GT>>
Node * Aleph::Gen_Binary_Lifting_LCA< GT, SA >::node_of ( const size_t  id) const
inline

Map an internal ID [0, n-1] back to a Node pointer.

Definition at line 544 of file LCA.H.

References Aleph::lca_detail::Rooted_Tree_Data< GT, SA >::node_of(), and Aleph::Gen_Binary_Lifting_LCA< GT, SA >::topology_.

Referenced by Aleph::Gen_Binary_Lifting_LCA< GT, SA >::kth_ancestor(), Aleph::Gen_Binary_Lifting_LCA< GT, SA >::lca(), and Aleph::Gen_Binary_Lifting_LCA< GT, SA >::parent_of().

◆ num_levels()

template<class GT , class SA = Dft_Show_Arc<GT>>
size_t Aleph::Gen_Binary_Lifting_LCA< GT, SA >::num_levels ( ) const
inlinenoexcept

Returns the number of levels in the jump table ( \(\lceil \log_2 n \rceil \)).

Definition at line 541 of file LCA.H.

References Aleph::Gen_Binary_Lifting_LCA< GT, SA >::levels_.

◆ parent_id()

template<class GT , class SA = Dft_Show_Arc<GT>>
size_t Aleph::Gen_Binary_Lifting_LCA< GT, SA >::parent_id ( const size_t  id) const
inline

Parent ID of node id, or NONE if root.

Definition at line 569 of file LCA.H.

References Aleph::lca_detail::Rooted_Tree_Data< GT, SA >::parent(), Aleph::Gen_Binary_Lifting_LCA< GT, SA >::topology_, and Aleph::lca_detail::Rooted_Tree_Data< GT, SA >::validate_id().

Referenced by Aleph::Gen_Binary_Lifting_LCA< GT, SA >::parent_of().

◆ parent_of()

template<class GT , class SA = Dft_Show_Arc<GT>>
Node * Aleph::Gen_Binary_Lifting_LCA< GT, SA >::parent_of ( const Node *  node) const
inline

Parent of node, or nullptr if root.

Definition at line 576 of file LCA.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Binary_Lifting_LCA< GT, SA >::id_of(), Aleph::Gen_Binary_Lifting_LCA< GT, SA >::node_of(), Aleph::Gen_Binary_Lifting_LCA< GT, SA >::NONE, and Aleph::Gen_Binary_Lifting_LCA< GT, SA >::parent_id().

◆ root()

template<class GT , class SA = Dft_Show_Arc<GT>>
Node * Aleph::Gen_Binary_Lifting_LCA< GT, SA >::root ( ) const
inlinenoexcept

Returns the root node of the tree.

Definition at line 535 of file LCA.H.

References Aleph::lca_detail::Rooted_Tree_Data< GT, SA >::root(), and Aleph::Gen_Binary_Lifting_LCA< GT, SA >::topology_.

◆ root_id()

template<class GT , class SA = Dft_Show_Arc<GT>>
size_t Aleph::Gen_Binary_Lifting_LCA< GT, SA >::root_id ( ) const
inlinenoexcept

Returns the internal ID of the root node.

Definition at line 538 of file LCA.H.

References Aleph::lca_detail::Rooted_Tree_Data< GT, SA >::root_id(), and Aleph::Gen_Binary_Lifting_LCA< GT, SA >::topology_.

◆ size()

template<class GT , class SA = Dft_Show_Arc<GT>>
size_t Aleph::Gen_Binary_Lifting_LCA< GT, SA >::size ( ) const
inlinenoexcept

Total number of nodes in the tree.

Definition at line 529 of file LCA.H.

References Aleph::lca_detail::Rooted_Tree_Data< GT, SA >::size(), and Aleph::Gen_Binary_Lifting_LCA< GT, SA >::topology_.

◆ up_at() [1/2]

template<class GT , class SA = Dft_Show_Arc<GT>>
size_t Aleph::Gen_Binary_Lifting_LCA< GT, SA >::up_at ( const size_t  k,
const size_t  v 
) const
inlineprivatenoexcept

Definition at line 459 of file LCA.H.

References k, Aleph::Gen_Binary_Lifting_LCA< GT, SA >::n(), and Aleph::Gen_Binary_Lifting_LCA< GT, SA >::up_.

◆ up_at() [2/2]

template<class GT , class SA = Dft_Show_Arc<GT>>
size_t & Aleph::Gen_Binary_Lifting_LCA< GT, SA >::up_at ( const size_t  k,
const size_t  v 
)
inlineprivatenoexcept

Definition at line 454 of file LCA.H.

References k, Aleph::Gen_Binary_Lifting_LCA< GT, SA >::n(), and Aleph::Gen_Binary_Lifting_LCA< GT, SA >::up_.

Referenced by Aleph::Gen_Binary_Lifting_LCA< GT, SA >::build_jump_table(), Aleph::Gen_Binary_Lifting_LCA< GT, SA >::lca_id(), and Aleph::Gen_Binary_Lifting_LCA< GT, SA >::lift().

Member Data Documentation

◆ levels_

template<class GT , class SA = Dft_Show_Arc<GT>>
size_t Aleph::Gen_Binary_Lifting_LCA< GT, SA >::levels_ = 0
private

Definition at line 449 of file LCA.H.

Referenced by Aleph::Gen_Binary_Lifting_LCA< GT, SA >::build_jump_table(), Aleph::Gen_Binary_Lifting_LCA< GT, SA >::lca_id(), and Aleph::Gen_Binary_Lifting_LCA< GT, SA >::num_levels().

◆ NONE

template<class GT , class SA = Dft_Show_Arc<GT>>
constexpr size_t Aleph::Gen_Binary_Lifting_LCA< GT, SA >::NONE = Topology::NONE
staticconstexprprivate

Definition at line 446 of file LCA.H.

Referenced by Aleph::Gen_Binary_Lifting_LCA< GT, SA >::build_jump_table(), Aleph::Gen_Binary_Lifting_LCA< GT, SA >::kth_ancestor(), Aleph::Gen_Binary_Lifting_LCA< GT, SA >::kth_ancestor_id(), Aleph::Gen_Binary_Lifting_LCA< GT, SA >::lca_id(), Aleph::Gen_Binary_Lifting_LCA< GT, SA >::lift(), and Aleph::Gen_Binary_Lifting_LCA< GT, SA >::parent_of().

◆ topology_

template<class GT , class SA = Dft_Show_Arc<GT>>
Topology Aleph::Gen_Binary_Lifting_LCA< GT, SA >::topology_
private

Definition at line 448 of file LCA.H.

Referenced by Aleph::Gen_Binary_Lifting_LCA< GT, SA >::build_jump_table(), Aleph::Gen_Binary_Lifting_LCA< GT, SA >::depth_of_id(), Aleph::Gen_Binary_Lifting_LCA< GT, SA >::distance_id(), Aleph::Gen_Binary_Lifting_LCA< GT, SA >::id_of(), Aleph::Gen_Binary_Lifting_LCA< GT, SA >::is_ancestor_id(), Aleph::Gen_Binary_Lifting_LCA< GT, SA >::is_empty(), Aleph::Gen_Binary_Lifting_LCA< GT, SA >::kth_ancestor_id(), Aleph::Gen_Binary_Lifting_LCA< GT, SA >::lca_id(), Aleph::Gen_Binary_Lifting_LCA< GT, SA >::n(), Aleph::Gen_Binary_Lifting_LCA< GT, SA >::node_of(), Aleph::Gen_Binary_Lifting_LCA< GT, SA >::parent_id(), Aleph::Gen_Binary_Lifting_LCA< GT, SA >::root(), Aleph::Gen_Binary_Lifting_LCA< GT, SA >::root_id(), and Aleph::Gen_Binary_Lifting_LCA< GT, SA >::size().

◆ up_

template<class GT , class SA = Dft_Show_Arc<GT>>
Array<size_t> Aleph::Gen_Binary_Lifting_LCA< GT, SA >::up_
private

Definition at line 450 of file LCA.H.

Referenced by Aleph::Gen_Binary_Lifting_LCA< GT, SA >::build_jump_table(), Aleph::Gen_Binary_Lifting_LCA< GT, SA >::up_at(), and Aleph::Gen_Binary_Lifting_LCA< GT, SA >::up_at().

The documentation for this class was generated from the following file: