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 >:

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<AlephGraph GT, ArcFilter< GT > 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:

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\).
For each node in the tour, store its depth.
Store the first occurrence index first[v] of each node v in the tour.
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

GT	Graph type (`List_Graph`, `List_SGraph`, `Array_Graph`).
SA	Arc filter type (default: `Dft_Show_Arc<GT>`).

Definition at line 733 of file LCA.H.

Member Typedef Documentation

◆ Depth_Node

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

using Aleph::Gen_Euler_RMQ_LCA< GT, SA >::Depth_Node = lca_detail::Depth_Node

private

Definition at line 741 of file LCA.H.

◆ Depth_Node_Min_Op

template<AlephGraph GT, ArcFilter< GT > 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 742 of file LCA.H.

◆ Node

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

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

Definition at line 736 of file LCA.H.

◆ Topology

template<AlephGraph GT, ArcFilter< GT > 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 739 of file LCA.H.

Constructor & Destructor Documentation

◆ Gen_Euler_RMQ_LCA() [1/2]

template<AlephGraph GT, ArcFilter< GT > 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_error if the filtered graph is not a tree.

Definition at line 776 of file LCA.H.

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

◆ Gen_Euler_RMQ_LCA() [2/2]

template<AlephGraph GT, ArcFilter< GT > 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 783 of file LCA.H.

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

Member Function Documentation

◆ build_rmq()

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

void Aleph::Gen_Euler_RMQ_LCA< GT, SA >::build_rmq ( )

inlineprivate

Definition at line 754 of file LCA.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Array< T >::create(), Aleph::lca_detail::Rooted_Tree_Data< GT, SA >::depth(), 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<AlephGraph GT, ArcFilter< GT > 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 833 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<AlephGraph GT, ArcFilter< GT > 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 826 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<AlephGraph GT, ArcFilter< GT > 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 893 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<AlephGraph GT, ArcFilter< GT > 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 886 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<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

void Aleph::Gen_Euler_RMQ_LCA< GT, SA >::ensure_not_empty ( const char * where ) const

inlineprivate

Definition at line 748 of file LCA.H.

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

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

◆ euler_tour()

template<AlephGraph GT, ArcFilter< GT > 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 899 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<AlephGraph GT, ArcFilter< GT > 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 905 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<AlephGraph GT, ArcFilter< GT > 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 820 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<AlephGraph GT, ArcFilter< GT > 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 859 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<AlephGraph GT, ArcFilter< GT > 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 853 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<AlephGraph GT, ArcFilter< GT > 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 796 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<AlephGraph GT, ArcFilter< GT > 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 880 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<AlephGraph GT, ArcFilter< GT > 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 865 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<AlephGraph GT, ArcFilter< GT > 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 814 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<AlephGraph GT, ArcFilter< GT > 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 839 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<AlephGraph GT, ArcFilter< GT > 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 846 of file LCA.H.

References 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<AlephGraph GT, ArcFilter< GT > 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 802 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<AlephGraph GT, ArcFilter< GT > 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 808 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<AlephGraph GT, ArcFilter< GT > 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 790 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<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

Array<Depth_Node> Aleph::Gen_Euler_RMQ_LCA< GT, SA >::euler_depth_

private

Definition at line 745 of file LCA.H.

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

◆ NONE

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

constexpr size_t Aleph::Gen_Euler_RMQ_LCA< GT, SA >::NONE = Topology::NONE

staticconstexprprivate

Definition at line 740 of file LCA.H.

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

◆ rmq_

template<AlephGraph GT, ArcFilter< GT > 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 746 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<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

Topology Aleph::Gen_Euler_RMQ_LCA< GT, SA >::topology_

private

Definition at line 744 of file LCA.H.

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

LCA.H

Public Types

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Member Typedef Documentation

◆ Depth_Node

◆ Depth_Node_Min_Op

◆ Node

◆ Topology

Constructor & Destructor Documentation

◆ Gen_Euler_RMQ_LCA() [1/2]

◆ Gen_Euler_RMQ_LCA() [2/2]

Member Function Documentation

◆ build_rmq()

◆ depth_of()

◆ depth_of_id()

◆ distance()

◆ distance_id()

◆ ensure_not_empty()

◆ euler_tour()

◆ euler_tour_size()

◆ id_of()

◆ is_ancestor()

◆ is_ancestor_id()

◆ is_empty()

◆ lca()

◆ lca_id()

◆ node_of()

◆ parent_id()

◆ parent_of()

◆ root()

◆ root_id()

◆ size()

Member Data Documentation

◆ euler_depth_

◆ NONE

◆ rmq_

◆ topology_