lca_test.cc File Reference

Tests for LCA.H (binary lifting and Euler tour + RMQ). More...

#include <gtest/gtest.h>
#include <algorithm>
#include <chrono>
#include <cstddef>
#include <cstdlib>
#include <functional>
#include <limits>
#include <random>
#include <stdexcept>
#include <utility>
#include <LCA.H>
#include <tpl_agraph.H>
#include <tpl_array.H>
#include <tpl_graph.H>
#include <tpl_sgraph.H>
#include <htlist.H>
#include "test_graph_helpers.h"

Include dependency graph for lca_test.cc:

Go to the source code of this file.

Functions
	TYPED_TEST (LcaTypedTest, EmptyTree)
	TYPED_TEST (LcaTypedTest, SingleNode)
	TYPED_TEST (LcaTypedTest, ManualTreeQueries)
	TYPED_TEST (LcaTypedTest, DefaultRootIsFirstNode)
	TYPED_TEST (LcaTypedTest, RejectsCycle)
	TYPED_TEST (LcaTypedTest, RejectsDisconnectedGraph)
	TYPED_TEST (LcaTypedTest, RejectsLoopAndParallelEdges)
	TYPED_TEST (LcaTypedTest, ArcFilterSelectsTree)
	TYPED_TEST (LcaTypedTest, RejectsNodeFromAnotherGraphAndBadIds)
	TYPED_TEST (LcaTypedTest, RandomTreesAgainstNaiveOracle)
	TYPED_TEST (LcaTypedTest, PerfRegression)

Detailed Description

Tests for LCA.H (binary lifting and Euler tour + RMQ).

Coverage:

• Empty and single-node trees
• Deterministic rooted trees with known LCAs/distances
• Input validation (cycle, disconnected, loop, parallel edge)
• Arc-filter behavior
• Node ownership and range checks
• Random stress against an independent naive oracle
• Cross-backend consistency (List_Graph, List_SGraph, Array_Graph)

Definition in file lca_test.cc.

Function Documentation

TYPED_TEST() [1/11]

TYPED_TEST	(	LcaTypedTest	,
		ArcFilterSelectsTree
	)

Definition at line 446 of file lca_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(), and nodes.

TYPED_TEST() [2/11]

TYPED_TEST	(	LcaTypedTest	,
		DefaultRootIsFirstNode
	)

Definition at line 342 of file lca_test.cc.

References Aleph::Array< T >::append(), Aleph::divide_and_conquer_partition_dp(), Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), nodes, and Aleph::Array< T >::reserve().

TYPED_TEST() [3/11]

TYPED_TEST	(	LcaTypedTest	,
		EmptyTree
	)

Definition at line 233 of file lca_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TYPED_TEST() [4/11]

TYPED_TEST	(	LcaTypedTest	,
		ManualTreeQueries
	)

Definition at line 280 of file lca_test.cc.

References Aleph::Array< T >::append(), check(), Aleph::divide_and_conquer_partition_dp(), nodes, and Aleph::Array< T >::reserve().

TYPED_TEST() [5/11]

TYPED_TEST	(	LcaTypedTest	,
		PerfRegression
	)

Definition at line 577 of file lca_test.cc.

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

TYPED_TEST() [6/11]

TYPED_TEST	(	LcaTypedTest	,
		RandomTreesAgainstNaiveOracle
	)

Definition at line 509 of file lca_test.cc.

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

TYPED_TEST() [7/11]

TYPED_TEST	(	LcaTypedTest	,
		RejectsCycle
	)

Definition at line 385 of file lca_test.cc.

References Aleph::Array< T >::append(), Aleph::divide_and_conquer_partition_dp(), nodes, and Aleph::Array< T >::reserve().

TYPED_TEST() [8/11]

TYPED_TEST	(	LcaTypedTest	,
		RejectsDisconnectedGraph
	)

Definition at line 402 of file lca_test.cc.

References Aleph::Array< T >::append(), Aleph::divide_and_conquer_partition_dp(), nodes, and Aleph::Array< T >::reserve().

TYPED_TEST() [9/11]

TYPED_TEST	(	LcaTypedTest	,
		RejectsLoopAndParallelEdges
	)

Definition at line 418 of file lca_test.cc.

References Aleph::Array< T >::append(), Aleph::divide_and_conquer_partition_dp(), nodes, and Aleph::Array< T >::reserve().

TYPED_TEST() [10/11]

TYPED_TEST	(	LcaTypedTest	,
		RejectsNodeFromAnotherGraphAndBadIds
	)

Definition at line 478 of file lca_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::Array< T >::reserve().

TYPED_TEST() [11/11]

TYPED_TEST	(	LcaTypedTest	,
		SingleNode
	)

Definition at line 251 of file lca_test.cc.

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