Offline subtree and path queries on trees via Mo's algorithm. More...

#include <tpl_mo_on_trees.H>

Collaboration diagram for Aleph::Gen_Mo_On_Trees< GT, Policy >:

Public Types
using	Node = typename GT::Node

using	Arc = typename GT::Arc

using	T = typename Node::Node_Type

using	answer_type = typename Policy::answer_type

Public Member Functions
	Gen_Mo_On_Trees (const GT &g, Node *root, Policy p=Policy())
	Construct a Mo's algorithm query engine for tree queries.

size_t	size () const noexcept
	Number of nodes in the tree.

bool	is_empty () const noexcept
	True if the tree is empty.

Array< answer_type >	subtree_solve (const Array< Node * > &query_roots) const
	Answer subtree queries using Mo's algorithm.

Array< answer_type >	subtree_solve (std::initializer_list< Node * > il) const
	Answer subtree queries from an initializer list.

Array< answer_type >	path_solve (const Array< std::pair< Node , Node > > &query_pairs) const
	Answer path queries between node pairs.

Array< answer_type >	path_solve (std::initializer_list< std::pair< Node , Node > > il) const
	Solve path queries (initializer-list overload).

Private Member Functions
void	build ()

size_t	lca (size_t u, size_t v) const

Array< answer_type >	mo_sweep (const Array< T > &data, Array< Mo_Query > queries, size_t n) const

Private Attributes
const GT &	g_

Node *	root_

Policy	pol_

size_t	n_ = 0

Array< Node * >	id_to_node_

MapOLhash< Node *, size_t >	node_to_id_

Array< T >	node_values_

Array< size_t >	tin_

Array< size_t >	tout_

Array< T >	flat_sub_

Array< size_t >	first_

Array< size_t >	last_

Array< size_t >	flat_node_

size_t	log_n_ = 0

Array< size_t >	depth_

Array< size_t >	parent_

Array< size_t >	up_

Static Private Attributes
static constexpr size_t	NONE = ~static_cast<size_t>(0)

Detailed Description

template<class GT, class Policy>
requires MoTreeGraph<GT>
class Aleph::Gen_Mo_On_Trees< GT, Policy >

Offline subtree and path queries on trees via Mo's algorithm.

Given a tree (represented as any Aleph-w graph type), a root node, and a Policy satisfying MoPolicy, this class preprocesses the tree in O(N log N) and then answers batches of subtree or path queries in O((N+Q)√N) time.

Template Parameters

GT	Graph type (`List_Graph`, `List_SGraph`, or `Array_Graph`).
Policy	A type satisfying `MoPolicy<Policy, GT::Node::Node_Type>`.

Example (subtree distinct count): // Build a tree

List_Graph<Graph_Node<int>, Graph_Arc<Empty_Class>> g;

auto * n0 = g.insert_node(10);

auto * n1 = g.insert_node(20);

auto * n2 = g.insert_node(10);

g.insert_arc(n0, n1);

g.insert_arc(n0, n2);

// Distinct count on subtree rooted at n0 → 2 (values 10, 20)

using G = decltype(g);

Gen_Mo_On_Trees<G, Distinct_Count_Policy<int>> mot(g, n0);

auto ans = mot.subtree_solve({n0});

// ans(0) == 2

Aleph::Gen_Mo_On_Trees
Offline subtree and path queries on trees via Mo's algorithm.
Definition tpl_mo_on_trees.H:168

Aleph::List_Graph
Graph implemented with double-linked adjacency lists.
Definition tpl_graph.H:428

Aleph::List_Graph::insert_node
virtual Node * insert_node(Node *node) noexcept
Insertion of a node already allocated.
Definition tpl_graph.H:524

Aleph::List_Graph::insert_arc
Arc * insert_arc(Node *src_node, Node *tgt_node, void *a)
Definition tpl_graph.H:604

Aleph::divide_and_conquer_partition_dp
Divide_Conquer_DP_Result< Cost > divide_and_conquer_partition_dp(const size_t groups, const size_t n, Transition_Cost_Fn transition_cost, const Cost inf=dp_optimization_detail::default_inf< Cost >())
Optimize partition DP using divide-and-conquer optimization.
Definition DP_Optimizations.H:133

Aleph::Graph_Arc
Arc of graph implemented with double-linked adjacency lists.
Definition tpl_graph.H:222

Definition at line 167 of file tpl_mo_on_trees.H.

Member Typedef Documentation

◆ answer_type

template<class GT , class Policy >

using Aleph::Gen_Mo_On_Trees< GT, Policy >::answer_type = typename Policy::answer_type

Definition at line 173 of file tpl_mo_on_trees.H.

◆ Arc

template<class GT , class Policy >

using Aleph::Gen_Mo_On_Trees< GT, Policy >::Arc = typename GT::Arc

Definition at line 171 of file tpl_mo_on_trees.H.

◆ Node

template<class GT , class Policy >

using Aleph::Gen_Mo_On_Trees< GT, Policy >::Node = typename GT::Node

Definition at line 170 of file tpl_mo_on_trees.H.

◆ T

template<class GT , class Policy >

using Aleph::Gen_Mo_On_Trees< GT, Policy >::T = typename Node::Node_Type

Definition at line 172 of file tpl_mo_on_trees.H.

Constructor & Destructor Documentation

◆ Gen_Mo_On_Trees()

template<class GT , class Policy >

Aleph::Gen_Mo_On_Trees< GT, Policy >::Gen_Mo_On_Trees	(	const GT &	g,
		Node *	root,
		Policy	p = `Policy()`
	)

inline

Construct a Mo's algorithm query engine for tree queries.

Performs an O(N log N) preprocessing step (Euler tour + binary lifting for LCA). The graph is not modified in any way.

Parameters

g	The tree graph (must be connected with N nodes and N-1 edges).
root	Root node used to orient parent/child relations.
p	Policy object copied/moved into the query engine.

Exceptions

std::domain_error	If `root` is not found in `g`.
std::domain_error	If `g` is disconnected (not a valid tree under the chosen root).
std::bad_alloc	If auxiliary arrays/tables cannot be allocated.

Note: Complexity: O(N log N) time and O(N log N) space.

Definition at line 447 of file tpl_mo_on_trees.H.

References Aleph::Gen_Mo_On_Trees< GT, Policy >::build().

Member Function Documentation

◆ build()

template<class GT , class Policy >

void Aleph::Gen_Mo_On_Trees< GT, Policy >::build ( )

inlineprivate

Definition at line 206 of file tpl_mo_on_trees.H.

Referenced by Aleph::Gen_Mo_On_Trees< GT, Policy >::Gen_Mo_On_Trees().

◆ is_empty()

template<class GT , class Policy >

bool Aleph::Gen_Mo_On_Trees< GT, Policy >::is_empty ( ) const

inlinenoexcept

True if the tree is empty.

Definition at line 457 of file tpl_mo_on_trees.H.

References Aleph::Gen_Mo_On_Trees< GT, Policy >::n_.

◆ lca()

template<class GT , class Policy >

size_t Aleph::Gen_Mo_On_Trees< GT, Policy >::lca	(	size_t	u,
		size_t	v
	)		const

inlineprivate

Definition at line 351 of file tpl_mo_on_trees.H.

References Aleph::Gen_Mo_On_Trees< GT, Policy >::depth_, Aleph::diff(), k, Aleph::Gen_Mo_On_Trees< GT, Policy >::log_n_, Aleph::Gen_Mo_On_Trees< GT, Policy >::n_, and Aleph::Gen_Mo_On_Trees< GT, Policy >::up_.

Referenced by Aleph::Gen_Mo_On_Trees< GT, Policy >::path_solve().

◆ mo_sweep()

template<class GT , class Policy >

Array< answer_type > Aleph::Gen_Mo_On_Trees< GT, Policy >::mo_sweep	(	const Array< T > &	data,
		Array< Mo_Query >	queries,
		size_t	n
	)		const

inlineprivate

Definition at line 375 of file tpl_mo_on_trees.H.

References Aleph::Array< T >::create(), Aleph::divide_and_conquer_partition_dp(), Aleph::Mo_Query::l, Aleph::Gen_Mo_On_Trees< GT, Policy >::pol_, r, and Aleph::Mo_Query::r.

Referenced by Aleph::Gen_Mo_On_Trees< GT, Policy >::subtree_solve().

◆ path_solve() [1/2]

template<class GT , class Policy >

Array< answer_type > Aleph::Gen_Mo_On_Trees< GT, Policy >::path_solve ( const Array< std::pair< Node *, Node * > > & query_pairs ) const

inline

Answer path queries between node pairs.

For each pair (u, v), answers the policy query over all nodes on the unique path from u to v (both endpoints included).

Uses the double-occurrence Euler tour with a toggle trick: each node appears twice (entry + exit). A node is "active" when it has been toggled an odd number of times within the current window. The LCA of each query is handled separately.

Parameters

query_pairs Array of (u, v) node-pointer pairs.

Returns: Array<answer_type> with answers in the same order as query_pairs.

Exceptions

std::domain_error	If any query endpoint is not in the tree.
Any	exception thrown by `Policy::init`, `Policy::add`, `Policy::remove`, or `Policy::answer`.