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

#include <LCA.H>

Collaboration diagram for Aleph::Gen_Binary_Lifting_LCA< GT, SA >:

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

Lift the deeper node until it is at the same depth as the other.
If they are now the same node, that is the LCA.
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

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

Definition at line 466 of file LCA.H.

Member Typedef Documentation

◆ Node

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

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

Definition at line 469 of file LCA.H.

◆ Topology

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

Constructor & Destructor Documentation

◆ Gen_Binary_Lifting_LCA() [1/2]

template<AlephGraph GT, ArcFilter< GT > 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]	g	Rooted tree topology (filtered by `sa`).
[in]	root	Root node pointer (must belong to `g`).
[in]	sa	Arc filter.

Exceptions

ah_domain_error if the filtered graph is not a tree.

Definition at line 541 of file LCA.H.

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

◆ Gen_Binary_Lifting_LCA() [2/2]

template<AlephGraph GT, ArcFilter< GT > 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]	g	Rooted tree topology (filtered by `sa`).
[in]	sa	Arc filter.

Definition at line 551 of file LCA.H.

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

Member Function Documentation

◆ build_jump_table()

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

void Aleph::Gen_Binary_Lifting_LCA< GT, SA >::build_jump_table ( )

inlineprivate

Definition at line 500 of file LCA.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Array< T >::create(), 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<AlephGraph GT, ArcFilter< GT > 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 606 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<AlephGraph GT, ArcFilter< GT > 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 599 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<AlephGraph GT, ArcFilter< GT > 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 706 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<AlephGraph GT, ArcFilter< GT > 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 699 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<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

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

inlineprivate

Definition at line 494 of file LCA.H.

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

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

◆ id_of()

template<AlephGraph GT, ArcFilter< GT > 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 593 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<AlephGraph GT, ArcFilter< GT > 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 632 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<AlephGraph GT, ArcFilter< GT > 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 626 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<AlephGraph GT, ArcFilter< GT > 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 563 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<AlephGraph GT, ArcFilter< GT > 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 655 of file LCA.H.

References 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<AlephGraph GT, ArcFilter< GT > 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]	id	Node id.
[in]	k	Number of steps up.

Returns: Ancestor id, or NONE if k > depth(id).

Definition at line 643 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<AlephGraph GT, ArcFilter< GT > 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 693 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<AlephGraph GT, ArcFilter< GT > 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 662 of file LCA.H.

References ah_runtime_error_unless, Aleph::blossom_maximum_cardinality_matching(), Aleph::lca_detail::Rooted_Tree_Data< GT, SA >::depth(), 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<AlephGraph GT, ArcFilter< GT > 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 523 of file LCA.H.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), 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<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

size_t Aleph::Gen_Binary_Lifting_LCA< GT, SA >::n ( ) const

inlineprivatenoexcept

Definition at line 479 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<AlephGraph GT, ArcFilter< GT > 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 587 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<AlephGraph GT, ArcFilter< GT > 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 581 of file LCA.H.

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

◆ parent_id()

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

References 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<AlephGraph GT, ArcFilter< GT > 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 569 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<AlephGraph GT, ArcFilter< GT > 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 575 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<AlephGraph GT, ArcFilter< GT > 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 557 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<AlephGraph GT, ArcFilter< GT > 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 489 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<AlephGraph GT, ArcFilter< GT > 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 484 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<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

size_t Aleph::Gen_Binary_Lifting_LCA< GT, SA >::levels_ = 0

private

Definition at line 476 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<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

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

staticconstexprprivate

Definition at line 473 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<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

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

private

Definition at line 475 of file LCA.H.

◆ up_

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

Array<size_t> Aleph::Gen_Binary_Lifting_LCA< GT, SA >::up_

private

Definition at line 477 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:

LCA.H

Public Types

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Member Typedef Documentation

◆ Node

◆ Topology

Constructor & Destructor Documentation

◆ Gen_Binary_Lifting_LCA() [1/2]

◆ Gen_Binary_Lifting_LCA() [2/2]

Member Function Documentation

◆ build_jump_table()

◆ depth_of()

◆ depth_of_id()

◆ distance()

◆ distance_id()

◆ ensure_not_empty()

◆ id_of()

◆ is_ancestor()

◆ is_ancestor_id()

◆ is_empty()

◆ kth_ancestor()

◆ kth_ancestor_id()

◆ lca()

◆ lca_id()

◆ lift()

◆ n()

◆ node_of()

◆ num_levels()

◆ parent_id()

◆ parent_of()

◆ root()

◆ root_id()

◆ size()

◆ up_at() [1/2]

◆ up_at() [2/2]

Member Data Documentation

◆ levels_

◆ NONE

◆ topology_

◆ up_