Dynamic forest with path queries via Link-Cut Trees. More...

#include <tpl_link_cut_tree.H>

Inheritance diagram for Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >:

Collaboration diagram for Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >:

Classes
struct	Node
	Internal node of the Link-Cut Tree (opaque handle). More...

Public Member Functions
	Gen_Link_Cut_Tree ()=default
	Default constructor for an empty Link-Cut Tree.

	~Gen_Link_Cut_Tree ()
	Destructor.

	Gen_Link_Cut_Tree (const Gen_Link_Cut_Tree &)=delete
	Deleted copy constructor.

Gen_Link_Cut_Tree &	operator= (const Gen_Link_Cut_Tree &)=delete
	Deleted copy assignment.

	Gen_Link_Cut_Tree (Gen_Link_Cut_Tree &&)=delete
	Deleted move constructor.

Gen_Link_Cut_Tree &	operator= (Gen_Link_Cut_Tree &&)=delete
	Deleted move assignment.

Node *	make_vertex (const T &val=T{})
	Create an isolated vertex with payload `val`.

Node *	make_vertex (T &&val)
	Create an isolated vertex (move semantics).

void	destroy_vertex (Node *x)
	Destroy an isolated vertex.

size_t	size () const noexcept
	Total number of vertices currently in the forest.

void	make_root (Node *x)
	Make `x` the root of its represented tree.

Node *	find_root (Node *x)
	Find the root of the represented tree containing `x`.

bool	connected (Node u, Node v)
	Test whether `u` and `v` are in the same represented tree.

void	link (Node u, Node v)
	Add an edge between `u` and `v`, merging their trees.

void	cut (Node u, Node v)
	Remove the represented edge between `u` and `v`.

Node *	lca (Node u, Node v)
	Lowest common ancestor of `u` and `v`.

T	path_query (Node u, Node v)
	Aggregate (under Monoid) over all vertex values on the path from `u` to `v`.

size_t	path_size (Node u, Node v)
	Number of vertices on the path from `u` to `v`.

const T &	get_val (Node *x)
	Read the payload value of vertex `x`.

void	set_val (Node *x, const T &val)
	Update the payload value of vertex `x` and recompute aggregates.

void	path_apply (Node u, Node v, const typename LazyTag::tag_type &tag)
	Apply a lazy tag to every vertex on the path from `u` to `v`.

size_t	num_components () const noexcept
	Number of connected components (trees) in the forest.

size_t	tree_size (Node *x)
	Number of vertices in the tree containing `x`.

size_t	depth (Node *x)
	Depth of `x` relative to the current root of its tree.

Node *	parent (Node *x)
	Parent of `x` in the represented tree under the current rooting.

template<typename Op >
void	for_each_node (Op &&op) const
	Call `op(Node *)` for every vertex in the forest.

template<typename Op >
void	for_each_on_path (Node u, Node v, Op &&op)
	Call `op(Node *)` for every vertex on the path from `u` to `v`, in order from `u` to `v`.

Array< Node * >	make_path (std::initializer_list< T > vals)
	Create a path of vertices from an initializer list of values.

Array< Node * >	make_vertices (std::initializer_list< T > vals)
	Create isolated vertices from an initializer list of values.

template<typename Container >
void	link_edges (const Container &edges)
	Link every pair in an edge container.

Tree_Node< T > *	export_to_tree_node (Node *root)
	Export the represented tree rooted at `root` as a `Tree_Node<T>`.

Static Private Member Functions
static bool	is_root (const Node *x) noexcept

static bool	is_left (const Node *x) noexcept

static void	push (Node *x) noexcept

static void	pull (Node *x) noexcept

static void	rotate (Node *x) noexcept

static void	splay (Node *x) noexcept

static Node *	access (Node *x) noexcept

template<typename Op >
static void	inorder_traverse (Node *root, Op &&op)

Private Attributes
Array< Node * >	nodes

size_t	n_components = 0

Detailed Description

template<typename T = int, class Monoid = DefaultMonoid<T>, class LazyTag = NoLazyTag<T>>
requires LCTMonoid<Monoid, T>
class Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >

Dynamic forest with path queries via Link-Cut Trees.

Template Parameters

T	Value type stored at each vertex.
Monoid	Associative combiner for path aggregation. Must satisfy `LCTMonoid`.
LazyTag	Lazy-tag policy for deferred path updates. Must satisfy `LCTLazyTag`.

The Gen_Link_Cut_Tree class allows you to manage a dynamic forest of nodes. It is particularly useful for problems where you need to answer connectivity queries or path aggregation queries (e.g., "what is the bottleneck edge on the path from A to B?") in a network that is constantly changing (edges being added and removed).

Lifecycle and Memory Management

Vertices are created via make_vertex(), returning an opaque Node* handle. The tree assumes ownership of all created nodes and will destroy them upon destruction. Handles remain stable as long as the tree is alive.

Typical Use Cases

Dynamic Connectivity: Use Link_Cut_Tree (which defaults to int and no-ops) simply to call link(), cut(), and connected().
Dynamic Minimum Spanning Forest: Maintain edges with weights using a MaxMonoid or MinMonoid. When adding an edge that forms a cycle, find the max/min weight edge on the cycle using path_query() and cut() it.
Path Updates / Range Queries on Trees: Use a SumMonoid and AddLazyTag to dynamically add values to paths and query path sums.

Complexity: Every public operation runs in amortized \(O(\log n)\) time, where \(n\) is the number of nodes currently in the forest.

Warning: The behavior is undefined if handles from different Gen_Link_Cut_Tree instances are mixed.

Definition at line 361 of file tpl_link_cut_tree.H.

Constructor & Destructor Documentation

◆ Gen_Link_Cut_Tree() [1/3]

template<typename T = int, class Monoid = DefaultMonoid<T>, class LazyTag = NoLazyTag<T>>

Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::Gen_Link_Cut_Tree ( )

default

Default constructor for an empty Link-Cut Tree.

◆ ~Gen_Link_Cut_Tree()

template<typename T = int, class Monoid = DefaultMonoid<T>, class LazyTag = NoLazyTag<T>>

Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::~Gen_Link_Cut_Tree ( )

inline

Destructor.

Frees all nodes managed by the LCT.

Definition at line 585 of file tpl_link_cut_tree.H.

References Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::nodes, and Aleph::Array< T >::size().

◆ Gen_Link_Cut_Tree() [2/3]

template<typename T = int, class Monoid = DefaultMonoid<T>, class LazyTag = NoLazyTag<T>>

Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::Gen_Link_Cut_Tree ( const Gen_Link_Cut_Tree< T, Monoid, LazyTag > & )

delete

Deleted copy constructor.

◆ Gen_Link_Cut_Tree() [3/3]

template<typename T = int, class Monoid = DefaultMonoid<T>, class LazyTag = NoLazyTag<T>>

Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::Gen_Link_Cut_Tree ( Gen_Link_Cut_Tree< T, Monoid, LazyTag > && )

delete

Deleted move constructor.

Member Function Documentation

◆ access()

template<typename T = int, class Monoid = DefaultMonoid<T>, class LazyTag = NoLazyTag<T>>

static Node * Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::access ( Node * x )

inlinestaticprivatenoexcept

Definition at line 545 of file tpl_link_cut_tree.H.

References Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::Node::parent, Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::pull(), and Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::splay().

◆ connected()

template<typename T = int, class Monoid = DefaultMonoid<T>, class LazyTag = NoLazyTag<T>>

bool Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::connected	(	Node *	u,
		Node *	v
	)

inline

Test whether u and v are in the same represented tree.

Internally, it checks if find_root(u) is the same as find_root(v).

Parameters

u	Handle to the first vertex.
v	Handle to the second vertex.

Returns: true if they are connected (in the same tree), false otherwise.

Exceptions

std::invalid_argument if u or v is null.

Definition at line 718 of file tpl_link_cut_tree.H.

References ah_invalid_argument_if, Aleph::divide_and_conquer_partition_dp(), and Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::find_root().

Referenced by Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::connected(), example_connectivity(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::export_to_tree_node(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::export_to_tree_node(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::link(), TEST(), TEST(), and Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::tree_size().

◆ cut()

template<typename T = int, class Monoid = DefaultMonoid<T>, class LazyTag = NoLazyTag<T>>

void Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::cut	(	Node *	u,
		Node *	v
	)

inline

Remove the represented edge between u and v.

Splits the tree containing u and v into two trees by deleting the edge between them. It achieves this by making u the root of the tree, and then accessing v. If v is adjacent to u in the represented tree, u will be the left child of v in the auxiliary tree. Breaking this child connection separates them.

Parameters

u	Handle to the first vertex of the edge.
v	Handle to the second vertex of the edge.

Exceptions

std::domain_error	if the edge (u, v) does not exist.
std::invalid_argument	if either handle is null.

Definition at line 769 of file tpl_link_cut_tree.H.

References Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::access(), ah_domain_error_if, ah_invalid_argument_if, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::Node::left, Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::make_root(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::n_components, Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::Node::parent, Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::pull(), and Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::Node::right.

Referenced by Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::cut(), example_connectivity(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::link(), TEST(), TEST(), and TEST().

◆ depth()

template<typename T = int, class Monoid = DefaultMonoid<T>, class LazyTag = NoLazyTag<T>>

size_t Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::depth ( Node * x )

inline

Depth of x relative to the current root of its tree.

The depth is the number of edges on the path from the root to x. O(log n) amortised.

Definition at line 932 of file tpl_link_cut_tree.H.

References Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::access(), ah_invalid_argument_if, Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::Node::left, and Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::Node::sz.

◆ destroy_vertex()

template<typename T = int, class Monoid = DefaultMonoid<T>, class LazyTag = NoLazyTag<T>>

void Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::destroy_vertex ( Node * x )

inline

Destroy an isolated vertex.

Parameters

x	Handle to the isolated vertex to destroy.

Exceptions

std::invalid_argument	if `x` is null.
std::domain_error	if `x` is not isolated or does not belong to this tree.

Definition at line 639 of file tpl_link_cut_tree.H.

References Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::access(), ah_domain_error_if, ah_invalid_argument_if, Aleph::and, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::Node::left, Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::n_components, Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::nodes, Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::Node::parent, Aleph::Array< T >::remove_last(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::Node::right, and Aleph::Array< T >::size().

Referenced by Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::cut(), and Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::link().

◆ export_to_tree_node()

template<typename T = int, class Monoid = DefaultMonoid<T>, class LazyTag = NoLazyTag<T>>

Tree_Node< T > * Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::export_to_tree_node ( Node * root )

inline

Export the represented tree rooted at root as a Tree_Node<T>.

Materializes the current represented tree containing root into an explicit n-ary tree of Tree_Node<T> nodes. A make_root(root) is performed internally to establish the rooting.

The caller owns the returned tree and must free it with destroy_tree(result).

Parameters

root	Vertex to use as root of the exported tree.

Returns: Newly allocated Tree_Node<T> * mirroring the represented tree.

Exceptions

std::invalid_argument if root is null.

Complexity: O(n^2) where n is the number of vertices in the component (dominated by the parent-lookup sweep).

Definition at line 1061 of file tpl_link_cut_tree.H.

References ah_invalid_argument_if, Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::connected(), destroy_tree(), Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::for_each_node(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::make_root(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::parent(), and root().

◆ find_root()

template<typename T = int, class Monoid = DefaultMonoid<T>, class LazyTag = NoLazyTag<T>>

Node * Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::find_root ( Node * x )

inline

Find the root of the represented tree containing x.

This exposes the path to x and then traverses down the left children of the auxiliary tree to find the node with the minimum depth in the represented tree, which corresponds to the root. The structure is splayed at the end to maintain amortized time bounds.

Parameters

x	Handle to a vertex in the tree.

Returns: Handle to the root vertex of the tree containing x.

Exceptions

std::invalid_argument if x is null.

Definition at line 693 of file tpl_link_cut_tree.H.

References Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::access(), ah_invalid_argument_if, Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::Node::left, Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::push(), and Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::splay().

Referenced by Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::connected(), example_rerooting(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::find_root(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::for_each_on_path(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::lca(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::link(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::path_apply(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::path_query(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::path_size(), and TEST().

◆ for_each_node()

template<typename T = int, class Monoid = DefaultMonoid<T>, class LazyTag = NoLazyTag<T>>

template<typename Op >

void Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::for_each_node ( Op && op ) const

inline

Call op(Node *) for every vertex in the forest.

Definition at line 965 of file tpl_link_cut_tree.H.

References Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::nodes, and Aleph::Array< T >::size().

Referenced by Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::export_to_tree_node().

◆ for_each_on_path()

template<typename T = int, class Monoid = DefaultMonoid<T>, class LazyTag = NoLazyTag<T>>

template<typename Op >

void Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::for_each_on_path	(	Node *	u,
		Node *	v,
		Op &&	op
	)

inline

Call op(Node *) for every vertex on the path from u to v, in order from u to v.

O(path_length log n) amortised.

Definition at line 977 of file tpl_link_cut_tree.H.

References ah_domain_error_if, ah_invalid_argument_if, Aleph::Array< T >::append(), Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::find_root(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::make_root(), and Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::parent().

◆ get_val()

template<typename T = int, class Monoid = DefaultMonoid<T>, class LazyTag = NoLazyTag<T>>

const T & Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::get_val ( Node * x )

inline

Read the payload value of vertex x.

Parameters

x	Handle to the vertex.

Returns: Constant reference to the stored value.

Exceptions

std::invalid_argument if x is null.

Definition at line 856 of file tpl_link_cut_tree.H.

References Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::access(), ah_invalid_argument_if, and Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::Node::val.

Referenced by example_lca(), example_rerooting(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::export_to_tree_node(), and Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::get_edge_val().

◆ inorder_traverse()

template<typename T = int, class Monoid = DefaultMonoid<T>, class LazyTag = NoLazyTag<T>>

template<typename Op >

static void Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::inorder_traverse	(	Node *	root,
		Op &&	op
	)

inlinestaticprivate

Definition at line 562 of file tpl_link_cut_tree.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::push(), and root().

◆ is_left()

template<typename T = int, class Monoid = DefaultMonoid<T>, class LazyTag = NoLazyTag<T>>

static bool Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::is_left ( const Node * x )

inlinestaticprivatenoexcept

Definition at line 409 of file tpl_link_cut_tree.H.

References Aleph::and.

◆ is_root()

template<typename T = int, class Monoid = DefaultMonoid<T>, class LazyTag = NoLazyTag<T>>

static bool Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::is_root ( const Node * x )

inlinestaticprivatenoexcept

Definition at line 403 of file tpl_link_cut_tree.H.

References Aleph::and, and Aleph::divide_and_conquer_partition_dp().

Referenced by Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::rotate(), and Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::splay().

◆ lca()

template<typename T = int, class Monoid = DefaultMonoid<T>, class LazyTag = NoLazyTag<T>>

Node * Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::lca	(	Node *	u,
		Node *	v
	)

inline

Lowest common ancestor of u and v.

The LCA is relative to the current rooting of the tree. If the structure has been rerooted via make_root(), the LCA will reflect that new hierarchy. Internally, it exposes the path from the root to u, and then begins exposing the path from the root to v. The point where the v path intersects the u path is the LCA.

Parameters

u	Handle to the first vertex.
v	Handle to the second vertex.

Returns: Handle to the LCA of u and v.

Exceptions

std::domain_error	if `u` and `v` are not connected.
std::invalid_argument	if either handle is null.

Definition at line 796 of file tpl_link_cut_tree.H.

References Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::access(), ah_domain_error_if, ah_invalid_argument_if, Aleph::divide_and_conquer_partition_dp(), and Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::find_root().

Referenced by example_lca().

◆ link()

template<typename T = int, class Monoid = DefaultMonoid<T>, class LazyTag = NoLazyTag<T>>

void Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::link	(	Node *	u,
		Node *	v
	)

inline

Add an edge between u and v, merging their trees.

This operation links the tree containing u to the tree containing v. It does this by first making u the root of its tree (make_root(u)). Then, it simply sets v as the parent of u in the represented forest.

The operation requires that u and v are currently in different trees. If they are already connected, a cycle would be formed, which is not allowed in a valid forest representation.

Parameters

u	Handle to the vertex that will become a child.
v	Handle to the vertex that will become the parent.

Exceptions

std::domain_error	if `u` and `v` are already in the same tree.
std::invalid_argument	if `u == v` or either handle is null.

Definition at line 746 of file tpl_link_cut_tree.H.

References ah_domain_error_if, ah_invalid_argument_if, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::find_root(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::make_root(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::n_components, and Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::Node::parent.

Referenced by example_connectivity(), example_lca(), example_path_aggregates(), example_rerooting(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::link(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::link_edges(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::make_path(), TEST(), TEST(), and TEST().

◆ link_edges()

template<typename T = int, class Monoid = DefaultMonoid<T>, class LazyTag = NoLazyTag<T>>

template<typename Container >

void Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::link_edges ( const Container & edges )

inline

Link every pair in an edge container.

Template Parameters

Container Iterable of std::pair<Node *, Node *>.

Definition at line 1036 of file tpl_link_cut_tree.H.

References Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::link().

◆ make_path()

template<typename T = int, class Monoid = DefaultMonoid<T>, class LazyTag = NoLazyTag<T>>

Array< Node * > Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::make_path ( std::initializer_list< T > vals )

inline

Create a path of vertices from an initializer list of values.

Returns an Array of handles in order. Each consecutive pair is linked.

Example: auto path = lct.make_path({10, 20, 30});

// path(0) — path(1) — path(2) with values 10, 20, 30

Definition at line 1004 of file tpl_link_cut_tree.H.

References Aleph::Array< T >::append(), Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::link(), and Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::make_vertex().

◆ make_root()

template<typename T = int, class Monoid = DefaultMonoid<T>, class LazyTag = NoLazyTag<T>>

void Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::make_root ( Node * x )

inline

Make x the root of its represented tree.

This operation changes the represented tree so that x becomes the new root. It exposes the path to x (bringing x to the root of its auxiliary tree) and flips its rev lazy flag. This reverses the depth order of the path, making x the highest node (the new root). Does not create or destroy any edge. After this call find_root(x) == x.

Parameters

x	Handle to the vertex to become the new root.

Exceptions

std::invalid_argument if x is null.

Definition at line 674 of file tpl_link_cut_tree.H.

References Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::access(), ah_invalid_argument_if, Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::push(), and Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::Node::rev.

Referenced by Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::cut(), example_lca(), example_rerooting(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::export_to_tree_node(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::for_each_on_path(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::link(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::make_root(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::path_apply(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::path_query(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::path_size(), and TEST().

◆ make_vertex() [1/2]

template<typename T = int, class Monoid = DefaultMonoid<T>, class LazyTag = NoLazyTag<T>>

Node * Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::make_vertex ( const T & val = T{} )

inline

Create an isolated vertex with payload val.

The vertex is created as a tree of a single node. The Link-Cut Tree retains ownership of the allocated memory. The returned handle must be used for all subsequent operations involving this vertex.

Parameters

val	Initial vertex value (default-constructed if omitted).

Returns: Stable handle to the new vertex.

Definition at line 612 of file tpl_link_cut_tree.H.

Referenced by example_connectivity(), example_lca(), example_path_aggregates(), example_rerooting(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::link(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::make_path(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::make_vertices(), TEST(), TEST(), TEST(), TEST(), and TEST_F().

◆ make_vertex() [2/2]

template<typename T = int, class Monoid = DefaultMonoid<T>, class LazyTag = NoLazyTag<T>>

Node * Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::make_vertex ( T && val )

inline

Create an isolated vertex (move semantics).

Parameters

val	Initial vertex value.

Returns: Stable handle to the new vertex.

Definition at line 625 of file tpl_link_cut_tree.H.

References Aleph::Array< T >::append(), Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::n_components, and Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::nodes.

◆ make_vertices()

template<typename T = int, class Monoid = DefaultMonoid<T>, class LazyTag = NoLazyTag<T>>

Array< Node * > Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::make_vertices ( std::initializer_list< T > vals )

inline

Create isolated vertices from an initializer list of values.

Returns: Array of handles (no edges created).

Definition at line 1023 of file tpl_link_cut_tree.H.

References Aleph::Array< T >::append(), Aleph::divide_and_conquer_partition_dp(), and Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::make_vertex().

◆ num_components()

template<typename T = int, class Monoid = DefaultMonoid<T>, class LazyTag = NoLazyTag<T>>

size_t Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::num_components ( ) const

inlinenoexcept

Number of connected components (trees) in the forest.

Note: O(1).

Definition at line 908 of file tpl_link_cut_tree.H.

References Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::n_components.

◆ operator=() [1/2]

template<typename T = int, class Monoid = DefaultMonoid<T>, class LazyTag = NoLazyTag<T>>

Gen_Link_Cut_Tree & Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::operator= ( const Gen_Link_Cut_Tree< T, Monoid, LazyTag > & )

delete

Deleted copy assignment.

◆ operator=() [2/2]

template<typename T = int, class Monoid = DefaultMonoid<T>, class LazyTag = NoLazyTag<T>>

Gen_Link_Cut_Tree & Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::operator= ( Gen_Link_Cut_Tree< T, Monoid, LazyTag > && )

delete

Deleted move assignment.

◆ parent()

template<typename T = int, class Monoid = DefaultMonoid<T>, class LazyTag = NoLazyTag<T>>

Node * Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::parent ( Node * x )

inline

Parent of x in the represented tree under the current rooting.

Returns nullptr if x is the root of its tree. O(log n) amortised.

Definition at line 944 of file tpl_link_cut_tree.H.

References Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::access(), ah_invalid_argument_if, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::Node::left, Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::push(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::Node::right, and Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::splay().

Referenced by Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::export_to_tree_node(), and Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::for_each_on_path().

◆ path_apply()

template<typename T = int, class Monoid = DefaultMonoid<T>, class LazyTag = NoLazyTag<T>>

void Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::path_apply	(	Node *	u,
		Node *	v,
		const typename LazyTag::tag_type &	tag
	)

inline

Apply a lazy tag to every vertex on the path from u to v.

Exposes the path between u and v, then applies the given tag to the root of the auxiliary tree representing this path. The change will be pushed down efficiently (lazily) during subsequent operations.

Available only when LazyTag is not NoLazyTag.

Parameters

u	Start vertex of the path.
v	End vertex of the path.
tag	The lazy tag to apply.

Exceptions

std::domain_error	if `u` and `v` are not connected.
std::invalid_argument	if either handle is null.

Definition at line 891 of file tpl_link_cut_tree.H.

References Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::access(), ah_domain_error_if, ah_invalid_argument_if, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::find_root(), and Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::make_root().

◆ path_query()

template<typename T = int, class Monoid = DefaultMonoid<T>, class LazyTag = NoLazyTag<T>>

T Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::path_query	(	Node *	u,
		Node *	v
	)

inline

Aggregate (under Monoid) over all vertex values on the path from u to v.

This method first makes u the root of the tree, and then exposes the path up to v by calling access(v). The path from u to v is perfectly captured in the auxiliary tree rooted at v, so the aggregate value is trivially available in v->agg.

Parameters

u	Start vertex of the path.
v	End vertex of the path.

Returns: The monoidal aggregation of values along the path.

Exceptions

std::domain_error	if `u` and `v` are not connected.
std::invalid_argument	if either handle is null.

Definition at line 824 of file tpl_link_cut_tree.H.

References Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::access(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::Node::agg, ah_domain_error_if, ah_invalid_argument_if, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::find_root(), and Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::make_root().

Referenced by example_path_aggregates(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::path_query(), and TEST().

◆ path_size()

template<typename T = int, class Monoid = DefaultMonoid<T>, class LazyTag = NoLazyTag<T>>

size_t Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::path_size	(	Node *	u,
		Node *	v
	)

inline

Number of vertices on the path from u to v.

Parameters

u	Start vertex of the path.
v	End vertex of the path.

Returns: The number of vertices on the path between u and v (inclusive).

Exceptions

std::domain_error	if `u` and `v` are not connected.
std::invalid_argument	if either handle is null.

Definition at line 841 of file tpl_link_cut_tree.H.

References Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::access(), ah_domain_error_if, ah_invalid_argument_if, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::find_root(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::make_root(), and Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::Node::sz.

Referenced by example_rerooting(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::path_size(), and TEST().

◆ pull()

template<typename T = int, class Monoid = DefaultMonoid<T>, class LazyTag = NoLazyTag<T>>

static void Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::pull ( Node * x )

inlinestaticprivatenoexcept

Definition at line 450 of file tpl_link_cut_tree.H.

References Aleph::divide_and_conquer_partition_dp().

Referenced by Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::access(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::cut(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::rotate(), and Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::set_val().

◆ push()

template<typename T = int, class Monoid = DefaultMonoid<T>, class LazyTag = NoLazyTag<T>>

static void Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::push ( Node * x )

inlinestaticprivatenoexcept

Definition at line 416 of file tpl_link_cut_tree.H.

References Aleph::divide_and_conquer_partition_dp().

Referenced by Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::find_root(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::inorder_traverse(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::make_root(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::parent(), and Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::splay().

◆ rotate()

template<typename T = int, class Monoid = DefaultMonoid<T>, class LazyTag = NoLazyTag<T>>

static void Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::rotate ( Node * x )

inlinestaticprivatenoexcept

Definition at line 472 of file tpl_link_cut_tree.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::is_root(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::Node::left, Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::Node::parent, Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::pull(), and Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::Node::right.

Referenced by Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::splay().

◆ set_val()

template<typename T = int, class Monoid = DefaultMonoid<T>, class LazyTag = NoLazyTag<T>>

void Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::set_val	(	Node *	x,
		const T &	val
	)

inline

Update the payload value of vertex x and recompute aggregates.

Parameters

x	Handle to the vertex to update.
val	The new value to set.

Exceptions

std::invalid_argument if x is null.

Definition at line 869 of file tpl_link_cut_tree.H.

References Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::access(), ah_invalid_argument_if, Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::pull(), and Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::Node::val.

Referenced by example_path_aggregates(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::set_edge_val(), and TEST().

◆ size()

template<typename T = int, class Monoid = DefaultMonoid<T>, class LazyTag = NoLazyTag<T>>

size_t Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::size ( ) const

inlinenoexcept

Total number of vertices currently in the forest.

Definition at line 661 of file tpl_link_cut_tree.H.

References Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::nodes, and Aleph::Array< T >::size().

◆ splay()

template<typename T = int, class Monoid = DefaultMonoid<T>, class LazyTag = NoLazyTag<T>>

static void Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::splay ( Node * x )

inlinestaticprivatenoexcept

Definition at line 509 of file tpl_link_cut_tree.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::is_root(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::Node::left, Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::Node::parent, Aleph::ArrayStack< T >::push(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::push(), and Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::rotate().

Referenced by Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::access(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::find_root(), and Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::parent().

◆ tree_size()

template<typename T = int, class Monoid = DefaultMonoid<T>, class LazyTag = NoLazyTag<T>>

size_t Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::tree_size ( Node * x )

inline

Number of vertices in the tree containing x.

Note: O(n log n) — scans all vertices. Use sparingly.

Definition at line 917 of file tpl_link_cut_tree.H.

References ah_invalid_argument_if, Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::connected(), Aleph::count(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::nodes, and Aleph::Array< T >::size().

Member Data Documentation

◆ n_components

template<typename T = int, class Monoid = DefaultMonoid<T>, class LazyTag = NoLazyTag<T>>

size_t Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::n_components = 0

private

Definition at line 399 of file tpl_link_cut_tree.H.

Referenced by Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::cut(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::destroy_vertex(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::link(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::make_vertex(), and Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::num_components().

◆ nodes

template<typename T = int, class Monoid = DefaultMonoid<T>, class LazyTag = NoLazyTag<T>>

Array<Node *> Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::nodes

private

Definition at line 398 of file tpl_link_cut_tree.H.

Referenced by Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::~Gen_Link_Cut_Tree(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::destroy_vertex(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::for_each_node(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::make_vertex(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::size(), and Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::tree_size().

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

tpl_link_cut_tree.H

Classes

Public Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Lifecycle and Memory Management

Typical Use Cases

Constructor & Destructor Documentation

◆ Gen_Link_Cut_Tree() [1/3]

◆ ~Gen_Link_Cut_Tree()

◆ Gen_Link_Cut_Tree() [2/3]

◆ Gen_Link_Cut_Tree() [3/3]

Member Function Documentation

◆ access()

◆ connected()

◆ cut()

◆ depth()

◆ destroy_vertex()

◆ export_to_tree_node()

◆ find_root()

◆ for_each_node()

◆ for_each_on_path()

◆ get_val()

◆ inorder_traverse()

◆ is_left()

◆ is_root()

◆ lca()

◆ link()

◆ link_edges()

◆ make_path()

◆ make_root()

◆ make_vertex() [1/2]

◆ make_vertex() [2/2]

◆ make_vertices()

◆ num_components()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ parent()

◆ path_apply()

◆ path_query()

◆ path_size()

◆ pull()

◆ push()

◆ rotate()

◆ set_val()

◆ size()

◆ splay()

◆ tree_size()

Member Data Documentation

◆ n_components

◆ nodes