hld_test.cc File Reference

Tests for HLD.H (Heavy-Light Decomposition). More...

#include <gtest/gtest.h>
#include <algorithm>
#include <cstddef>
#include <functional>
#include <limits>
#include <numeric>
#include <random>
#include <stdexcept>
#include <utility>
#include <vector>
#include <HLD.H>
#include <LCA.H>
#include <tpl_agraph.H>
#include <tpl_graph.H>
#include <tpl_sgraph.H>
#include "test_graph_helpers.h"

Include dependency graph for hld_test.cc:

Go to the source code of this file.

Functions
	TYPED_TEST (HldTypedTest, EmptyTree)
	TYPED_TEST (HldTypedTest, SingleNode)
	TYPED_TEST (HldTypedTest, ManualTreePathSum)
	TYPED_TEST (HldTypedTest, ManualTreePathMax)
	TYPED_TEST (HldTypedTest, ManualTreeSubtreeQuery)
	TYPED_TEST (HldTypedTest, PointUpdate)
	TYPED_TEST (HldTypedTest, PathQueryEdges)
	TYPED_TEST (HldTypedTest, LcaFromHLD)
	TYPED_TEST (HldTypedTest, DecompositionProperties)
	TYPED_TEST (HldTypedTest, ValidationErrors)
	TYPED_TEST (HldTypedTest, ArcFilter)
	TYPED_TEST (HldTypedTest, StressRandomAgainstNaive)

Detailed Description

Tests for HLD.H (Heavy-Light Decomposition).

Coverage:

• Empty and single-node trees
• Deterministic rooted trees with known path sums, max, and subtree queries
• Point updates
• Edge-weighted path queries
• LCA via HLD (cross-validated against Binary_Lifting_LCA)
• Decomposition property invariants
• Input validation (cycle, disconnected, loop, parallel edge)
• Arc-filter behavior
• Random stress against an independent naive oracle
• Cross-backend consistency (List_Graph, List_SGraph, Array_Graph)

Definition in file hld_test.cc.

Function Documentation

TYPED_TEST() [1/12]

TYPED_TEST	(	HldTypedTest	,
		ArcFilter
	)

Definition at line 566 of file hld_test.cc.

References Aleph::Array< T >::create(), Aleph::divide_and_conquer_partition_dp(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), l, and nodes.

TYPED_TEST() [2/12]

TYPED_TEST	(	HldTypedTest	,
		DecompositionProperties
	)

Definition at line 482 of file hld_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and nodes.

TYPED_TEST() [3/12]

TYPED_TEST	(	HldTypedTest	,
		EmptyTree
	)

Definition at line 233 of file hld_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TYPED_TEST() [4/12]

TYPED_TEST	(	HldTypedTest	,
		LcaFromHLD
	)

Definition at line 450 of file hld_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and nodes.

TYPED_TEST() [5/12]

TYPED_TEST	(	HldTypedTest	,
		ManualTreePathMax
	)

Definition at line 320 of file hld_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and nodes.

TYPED_TEST() [6/12]

TYPED_TEST	(	HldTypedTest	,
		ManualTreePathSum
	)

Definition at line 272 of file hld_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and nodes.

TYPED_TEST() [7/12]

TYPED_TEST	(	HldTypedTest	,
		ManualTreeSubtreeQuery
	)

Definition at line 349 of file hld_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and nodes.

TYPED_TEST() [8/12]

TYPED_TEST	(	HldTypedTest	,
		PathQueryEdges
	)

Definition at line 414 of file hld_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and nodes.

TYPED_TEST() [9/12]

TYPED_TEST	(	HldTypedTest	,
		PointUpdate
	)

Definition at line 382 of file hld_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and nodes.

TYPED_TEST() [10/12]

TYPED_TEST	(	HldTypedTest	,
		SingleNode
	)

Definition at line 249 of file hld_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node().

TYPED_TEST() [11/12]

TYPED_TEST	(	HldTypedTest	,
		StressRandomAgainstNaive
	)

Definition at line 604 of file hld_test.cc.

References Aleph::divide_and_conquer_partition_dp(), nodes, rng, and root().

TYPED_TEST() [12/12]

TYPED_TEST	(	HldTypedTest	,
		ValidationErrors
	)

Definition at line 530 of file hld_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and nodes.