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_Euler_RMQ_LCA< GT, SA > Class Template Reference
Graphs

LCA via Euler tour + RMQ on depth in a rooted tree. More...

#include <LCA.H>

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

Public Types

using Node = typename GT::Node
 

Public Member Functions

 Gen_Euler_RMQ_LCA (const GT &g, Node *root, SA sa=SA())
 Construct from graph + explicit root.
 
 Gen_Euler_RMQ_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.
 
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 lca_id (const size_t u, const size_t v) const
 LCA query by node ids in O(1).
 
Node * lca (const Node *u, const Node *v) const
 LCA query by node pointers in O(1).
 
size_t distance_id (const size_t u, const size_t v) const
 Number of edges on the path between two ids in O(1).
 
size_t distance (const Node *u, const Node *v) const
 Number of edges on the path between two nodes in O(1).
 
const Array< size_t > & euler_tour () const noexcept
 Euler tour sequence of node ids ( \(2n - 1\) entries).
 
size_t euler_tour_size () const noexcept
 Euler tour size ( \(0\) for empty tree, else \(2n - 1\)).
 

Private Types

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

Private Member Functions

void ensure_not_empty (const char *where) const
 
void build_rmq ()
 

Private Attributes

Topology topology_
 
Array< Depth_Node > euler_depth_
 
Gen_Sparse_Table< Depth_Node, Depth_Node_Min_Op > rmq_
 

Static Private Attributes

static constexpr size_t NONE = Topology::NONE
 

Detailed Description

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

LCA via Euler tour + RMQ on depth in a rooted tree.

This engine reduces the LCA problem to a Range Minimum Query (RMQ) problem.

The Reduction:

  1. Perform an Euler tour of the tree, recording each node as it is visited and as we return from its children. The tour has size \(2n - 1\).
  2. For each node in the tour, store its depth.
  3. Store the first occurrence index first[v] of each node v in the tour.
  4. The LCA of \(u\) and \(v\) is the node with the minimum depth in the Euler tour range [first[u], first[v]].

By using a Sparse Table for RMQ, we achieve constant time \(O(1)\) queries after \(O(n \log n)\) preprocessing.

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

Definition at line 691 of file LCA.H.

Member Typedef Documentation

◆ Depth_Node

template<class GT , class SA = Dft_Show_Arc<GT>>
using Aleph::Gen_Euler_RMQ_LCA< GT, SA >::Depth_Node = lca_detail::Depth_Node
private

Definition at line 699 of file LCA.H.

◆ Depth_Node_Min_Op

template<class GT , class SA = Dft_Show_Arc<GT>>
using Aleph::Gen_Euler_RMQ_LCA< GT, SA >::Depth_Node_Min_Op = lca_detail::Depth_Node_Min_Op
private

Definition at line 700 of file LCA.H.

◆ Node

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

Definition at line 694 of file LCA.H.

◆ Topology

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

Definition at line 697 of file LCA.H.

Constructor & Destructor Documentation

◆ Gen_Euler_RMQ_LCA() [1/2]

template<class GT , class SA = Dft_Show_Arc<GT>>
Aleph::Gen_Euler_RMQ_LCA< GT, SA >::Gen_Euler_RMQ_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.

Exceptions
ah_domain_errorif the filtered graph is not a tree.

Definition at line 735 of file LCA.H.

References Aleph::Gen_Euler_RMQ_LCA< GT, SA >::build_rmq().

◆ Gen_Euler_RMQ_LCA() [2/2]

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

Construct using the first graph node as root.

Definition at line 743 of file LCA.H.

References Aleph::Gen_Euler_RMQ_LCA< GT, SA >::build_rmq().

Member Function Documentation

◆ build_rmq()

template<class GT , class SA = Dft_Show_Arc<GT>>
void Aleph::Gen_Euler_RMQ_LCA< GT, SA >::build_rmq ( )
inlineprivate

Definition at line 712 of file LCA.H.

References Aleph::Array< T >::create(), Aleph::lca_detail::Rooted_Tree_Data< GT, SA >::depth(), Aleph::divide_and_conquer_partition_dp(), Aleph::lca_detail::Rooted_Tree_Data< GT, SA >::euler(), Aleph::Gen_Euler_RMQ_LCA< GT, SA >::euler_depth_, Aleph::lca_detail::Rooted_Tree_Data< GT, SA >::euler_size(), Aleph::Gen_Euler_RMQ_LCA< GT, SA >::is_empty(), Aleph::Gen_Euler_RMQ_LCA< GT, SA >::rmq_, and Aleph::Gen_Euler_RMQ_LCA< GT, SA >::topology_.

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

◆ depth_of()

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

Distance from root to node.

Definition at line 782 of file LCA.H.

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

◆ depth_of_id()

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

Distance from root to node by ID.

Definition at line 775 of file LCA.H.

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

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

◆ distance()

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

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

Definition at line 842 of file LCA.H.

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

◆ distance_id()

template<class GT , class SA = Dft_Show_Arc<GT>>
size_t Aleph::Gen_Euler_RMQ_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(1).

Definition at line 835 of file LCA.H.

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

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

◆ ensure_not_empty()

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

Definition at line 706 of file LCA.H.

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

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

◆ euler_tour()

template<class GT , class SA = Dft_Show_Arc<GT>>
const Array< size_t > & Aleph::Gen_Euler_RMQ_LCA< GT, SA >::euler_tour ( ) const
inlinenoexcept

Euler tour sequence of node ids ( \(2n - 1\) entries).

Definition at line 848 of file LCA.H.

References Aleph::lca_detail::Rooted_Tree_Data< GT, SA >::euler(), and Aleph::Gen_Euler_RMQ_LCA< GT, SA >::topology_.

◆ euler_tour_size()

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

Euler tour size ( \(0\) for empty tree, else \(2n - 1\)).

Definition at line 854 of file LCA.H.

References Aleph::lca_detail::Rooted_Tree_Data< GT, SA >::euler_size(), and Aleph::Gen_Euler_RMQ_LCA< GT, SA >::topology_.

◆ id_of()

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

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

Definition at line 769 of file LCA.H.

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

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

◆ is_ancestor()

template<class GT , class SA = Dft_Show_Arc<GT>>
bool Aleph::Gen_Euler_RMQ_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 808 of file LCA.H.

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

◆ is_ancestor_id()

template<class GT , class SA = Dft_Show_Arc<GT>>
bool Aleph::Gen_Euler_RMQ_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 802 of file LCA.H.

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

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

◆ is_empty()

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

Returns true if the tree has no nodes.

Definition at line 754 of file LCA.H.

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

Referenced by Aleph::Gen_Euler_RMQ_LCA< GT, SA >::build_rmq(), and Aleph::Gen_Euler_RMQ_LCA< GT, SA >::ensure_not_empty().

◆ lca()

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

LCA query by node pointers in O(1).

Definition at line 829 of file LCA.H.

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

◆ lca_id()

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

LCA query by node ids in O(1).

Definition at line 814 of file LCA.H.

References Aleph::Gen_Euler_RMQ_LCA< GT, SA >::ensure_not_empty(), Aleph::lca_detail::Rooted_Tree_Data< GT, SA >::first(), l, r, Aleph::Gen_Euler_RMQ_LCA< GT, SA >::rmq_, Aleph::Gen_Euler_RMQ_LCA< GT, SA >::topology_, and Aleph::lca_detail::Rooted_Tree_Data< GT, SA >::validate_id().

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

◆ node_of()

template<class GT , class SA = Dft_Show_Arc<GT>>
Node * Aleph::Gen_Euler_RMQ_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 763 of file LCA.H.

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

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

◆ parent_id()

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

Parent ID of node id, or NONE if root.

Definition at line 788 of file LCA.H.

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

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

◆ parent_of()

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

Parent of node, or nullptr if root.

Definition at line 795 of file LCA.H.

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

◆ root()

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

Returns the root node of the tree.

Definition at line 757 of file LCA.H.

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

◆ root_id()

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

Returns the internal ID of the root node.

Definition at line 760 of file LCA.H.

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

◆ size()

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

Total number of nodes in the tree.

Definition at line 751 of file LCA.H.

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

Member Data Documentation

◆ euler_depth_

template<class GT , class SA = Dft_Show_Arc<GT>>
Array<Depth_Node> Aleph::Gen_Euler_RMQ_LCA< GT, SA >::euler_depth_
private

Definition at line 703 of file LCA.H.

Referenced by Aleph::Gen_Euler_RMQ_LCA< GT, SA >::build_rmq().

◆ NONE

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

Definition at line 698 of file LCA.H.

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

◆ rmq_

template<class GT , class SA = Dft_Show_Arc<GT>>
Gen_Sparse_Table<Depth_Node, Depth_Node_Min_Op> Aleph::Gen_Euler_RMQ_LCA< GT, SA >::rmq_
private

Definition at line 704 of file LCA.H.

Referenced by Aleph::Gen_Euler_RMQ_LCA< GT, SA >::build_rmq(), and Aleph::Gen_Euler_RMQ_LCA< GT, SA >::lca_id().

◆ topology_

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

Definition at line 702 of file LCA.H.

Referenced by Aleph::Gen_Euler_RMQ_LCA< GT, SA >::build_rmq(), Aleph::Gen_Euler_RMQ_LCA< GT, SA >::depth_of_id(), Aleph::Gen_Euler_RMQ_LCA< GT, SA >::distance_id(), Aleph::Gen_Euler_RMQ_LCA< GT, SA >::euler_tour(), Aleph::Gen_Euler_RMQ_LCA< GT, SA >::euler_tour_size(), Aleph::Gen_Euler_RMQ_LCA< GT, SA >::id_of(), Aleph::Gen_Euler_RMQ_LCA< GT, SA >::is_ancestor_id(), Aleph::Gen_Euler_RMQ_LCA< GT, SA >::is_empty(), Aleph::Gen_Euler_RMQ_LCA< GT, SA >::lca_id(), Aleph::Gen_Euler_RMQ_LCA< GT, SA >::node_of(), Aleph::Gen_Euler_RMQ_LCA< GT, SA >::parent_id(), Aleph::Gen_Euler_RMQ_LCA< GT, SA >::root(), Aleph::Gen_Euler_RMQ_LCA< GT, SA >::root_id(), and Aleph::Gen_Euler_RMQ_LCA< GT, SA >::size().

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