link_cut_tree_test.cc File Reference

Comprehensive tests for Link-Cut Tree (tpl_link_cut_tree.H). More...

#include <algorithm>
#include <chrono>
#include <numeric>
#include <random>
#include <vector>
#include <gtest/gtest.h>
#include <tpl_link_cut_tree.H>
#include <tpl_link_cut_tree_with_edges.H>

Include dependency graph for link_cut_tree_test.cc:

Go to the source code of this file.

Classes
class	LinkCutTreeStructTest
class	LinkCutTreeSumTest
class	LinkCutTreeMinTest
class	LinkCutTreeMaxTest
class	LinkCutTreeXorTest
class	LinkCutTreeGcdTest
class	LinkCutTreeProductTest
class	LinkCutTreeLazyTest
class	LinkCutTreeAssignTest
class	LinkCutTreeEdgesTest

Functions
	TEST_F (LinkCutTreeStructTest, SingleNodeIsItsOwnRoot)
	TEST (LinkCutTreeOwnership, DestroyForeignHandleRejected)
	TEST_F (LinkCutTreeStructTest, LinkTwoNodesConnectsThem)
	TEST_F (LinkCutTreeStructTest, CutDisconnects)
	TEST_F (LinkCutTreeStructTest, BuildPath)
	TEST_F (LinkCutTreeStructTest, CutMiddleOfPath)
	TEST_F (LinkCutTreeStructTest, BuildStar)
	TEST_F (LinkCutTreeStructTest, RerootPath)
	TEST_F (LinkCutTreeStructTest, MultipleReroots)
	TEST_F (LinkCutTreeStructTest, FindRootAcrossAllNodesAfterRepeatedReroots)
	TEST_F (LinkCutTreeStructTest, LcaSameNode)
	TEST_F (LinkCutTreeStructTest, LcaOnPath)
	TEST_F (LinkCutTreeStructTest, LcaOnBinaryTree)
	TEST_F (LinkCutTreeStructTest, LinkAlreadyConnectedThrows)
	TEST_F (LinkCutTreeStructTest, SelfLinkThrows)
	TEST_F (LinkCutTreeStructTest, CutNonExistentEdgeThrows)
	TEST_F (LinkCutTreeStructTest, NullHandleThrows)
	TEST_F (LinkCutTreeStructTest, LcaDisconnectedThrows)
	TEST_F (LinkCutTreeStructTest, PathOperationsDisconnectedThrow)
	TEST_F (LinkCutTreeStructTest, NumComponents)
	TEST_F (LinkCutTreeStructTest, TreeSize)
	TEST_F (LinkCutTreeStructTest, DepthOnPath)
	TEST_F (LinkCutTreeStructTest, ParentOnPath)
	TEST_F (LinkCutTreeStructTest, ParentOnStar)
	TEST_F (LinkCutTreeStructTest, ForEachOnPath)
	TEST_F (LinkCutTreeStructTest, ForEachNode)
	TEST_F (LinkCutTreeStructTest, MakePath)
	TEST_F (LinkCutTreeStructTest, MakeVertices)
	TEST_F (LinkCutTreeStructTest, LinkEdges)
	TEST_F (LinkCutTreeSumTest, SingleNodeQuery)
	TEST_F (LinkCutTreeSumTest, PathSum)
	TEST_F (LinkCutTreeSumTest, SetValUpdatesAggregate)
	TEST_F (LinkCutTreeSumTest, SumAfterCutAndRelink)
	TEST_F (LinkCutTreeMinTest, PathMin)
	TEST_F (LinkCutTreeMaxTest, PathMax)
	TEST_F (LinkCutTreeXorTest, PathXor)
	TEST_F (LinkCutTreeGcdTest, PathGcd)
	TEST_F (LinkCutTreeProductTest, PathProduct)
	TEST_F (LinkCutTreeLazyTest, PathApplyAndQuery)
	TEST_F (LinkCutTreeLazyTest, PathApplyDisconnectedThrows)
	TEST_F (LinkCutTreeAssignTest, AssignAndQuery)
	TEST (LinkCutTreeStress, RandomLinkCutConnected)
	TEST (LinkCutTreeStress, RandomPathSum)
	TEST (LinkCutTreePerf, LargePathStaysReasonable)
	TEST_F (LinkCutTreeEdgesTest, SimpleLink)
	TEST_F (LinkCutTreeEdgesTest, VertexPayloadStoredSeparatelyFromEdgeWeights)
	TEST_F (LinkCutTreeEdgesTest, PathQueryEdges)
	TEST_F (LinkCutTreeEdgesTest, EdgeValueUpdate)
	TEST_F (LinkCutTreeEdgesTest, Cut)
	TEST_F (LinkCutTreeEdgesTest, DynamicMSTSimulation)
	TEST_F (LinkCutTreeEdgesTest, MultipleEdges)
	TEST_F (LinkCutTreeEdgesTest, SetEdgeVal)
	TEST_F (LinkCutTreeEdgesTest, CutAndRelink)
	TEST_F (LinkCutTreeEdgesTest, ErrorHandling)
	TEST (LinkCutTreeEdgeStress, RandomLinkCutPathMax)
	TEST_F (LinkCutTreeStructTest, ExportToTreeNodePath)
	TEST_F (LinkCutTreeStructTest, ExportToTreeNodeStar)
	TEST_F (LinkCutTreeEdgesTest, ExportToTreeNodeEdges)
	TEST_F (LinkCutTreeEdgesTest, ExportToTreeNodeStar)
	TEST_F (LinkCutTreeEdgesTest, NumEdgesAndNumComponentsAfterLink)
	TEST_F (LinkCutTreeEdgesTest, NumEdgesAndNumComponentsAfterCut)
	TEST_F (LinkCutTreeEdgesTest, PathSizeOnSimplePath)
	TEST_F (LinkCutTreeEdgesTest, MakeRootAndFindRoot)
	TEST (LinkCutTreeEdgesOwnership, ForeignHandleRejected)
int	main (int argc, char *argv[])

Detailed Description

Comprehensive tests for Link-Cut Tree (tpl_link_cut_tree.H).

Tests structural operations (link, cut, connected, make_root, find_root, lca), path aggregates (sum, min, max, xor), lazy path updates, error-handling contracts, and randomised stress against a naive oracle.

Definition in file link_cut_tree_test.cc.

Function Documentation

main()

int main	(	int	argc,
		char *	argv[]
	)

Definition at line 1691 of file link_cut_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [1/6]

TEST	(	LinkCutTreeEdgesOwnership	,
		ForeignHandleRejected
	)

Definition at line 1668 of file link_cut_tree_test.cc.

References Aleph::destroy_tree(), Aleph::divide_and_conquer_partition_dp(), and Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::make_vertex().

TEST() [2/6]

TEST	(	LinkCutTreeEdgeStress	,
		RandomLinkCutPathMax
	)

Definition at line 1367 of file link_cut_tree_test.cc.

References Aleph::and, Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::connected(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::cut(), Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::link(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::make_vertex(), N, Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::path_query(), rng, and w.

TEST() [3/6]

TEST	(	LinkCutTreeOwnership	,
		DestroyForeignHandleRejected
	)

Definition at line 73 of file link_cut_tree_test.cc.

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

TEST() [4/6]

TEST	(	LinkCutTreePerf	,
		LargePathStaysReasonable
	)

Definition at line 1069 of file link_cut_tree_test.cc.

References Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::connected(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::cut(), Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::find_root(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::link(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::make_root(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::make_vertex(), N, and Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::path_size().

TEST() [5/6]

TEST	(	LinkCutTreeStress	,
		RandomLinkCutConnected
	)

Definition at line 860 of file link_cut_tree_test.cc.

References Aleph::and, Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::connected(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::cut(), Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::link(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::make_vertex(), N, and rng.

TEST() [6/6]

TEST	(	LinkCutTreeStress	,
		RandomPathSum
	)

Definition at line 979 of file link_cut_tree_test.cc.

References Aleph::and, Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::cut(), Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::link(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::make_vertex(), N, Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::path_query(), rng, Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::set_val(), and Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::Node::val.

TEST_F() [1/58]

TEST_F	(	LinkCutTreeAssignTest	,
		AssignAndQuery
	)

Definition at line 773 of file link_cut_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and N.

TEST_F() [2/58]

TEST_F	(	LinkCutTreeEdgesTest	,
		Cut
	)

Definition at line 1172 of file link_cut_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [3/58]

TEST_F	(	LinkCutTreeEdgesTest	,
		CutAndRelink
	)

Definition at line 1250 of file link_cut_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [4/58]

TEST_F	(	LinkCutTreeEdgesTest	,
		DynamicMSTSimulation
	)

Definition at line 1184 of file link_cut_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [5/58]

TEST_F	(	LinkCutTreeEdgesTest	,
		EdgeValueUpdate
	)

Definition at line 1158 of file link_cut_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [6/58]

TEST_F	(	LinkCutTreeEdgesTest	,
		ErrorHandling
	)

Definition at line 1268 of file link_cut_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and w.

TEST_F() [7/58]

TEST_F	(	LinkCutTreeEdgesTest	,
		ExportToTreeNodeEdges
	)

Definition at line 1514 of file link_cut_tree_test.cc.

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

TEST_F() [8/58]

TEST_F	(	LinkCutTreeEdgesTest	,
		ExportToTreeNodeStar
	)

Definition at line 1557 of file link_cut_tree_test.cc.

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

TEST_F() [9/58]

TEST_F	(	LinkCutTreeEdgesTest	,
		MakeRootAndFindRoot
	)

Definition at line 1648 of file link_cut_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [10/58]

TEST_F	(	LinkCutTreeEdgesTest	,
		MultipleEdges
	)

Definition at line 1205 of file link_cut_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [11/58]

TEST_F	(	LinkCutTreeEdgesTest	,
		NumEdgesAndNumComponentsAfterCut
	)

Definition at line 1611 of file link_cut_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [12/58]

TEST_F	(	LinkCutTreeEdgesTest	,
		NumEdgesAndNumComponentsAfterLink
	)

Definition at line 1593 of file link_cut_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [13/58]

TEST_F	(	LinkCutTreeEdgesTest	,
		PathQueryEdges
	)

Definition at line 1142 of file link_cut_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and w.

TEST_F() [14/58]

TEST_F	(	LinkCutTreeEdgesTest	,
		PathSizeOnSimplePath
	)

Definition at line 1631 of file link_cut_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [15/58]

TEST_F	(	LinkCutTreeEdgesTest	,
		SetEdgeVal
	)

Definition at line 1232 of file link_cut_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and w.

TEST_F() [16/58]

TEST_F	(	LinkCutTreeEdgesTest	,
		SimpleLink
	)

Definition at line 1115 of file link_cut_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [17/58]

TEST_F	(	LinkCutTreeEdgesTest	,
		VertexPayloadStoredSeparatelyFromEdgeWeights
	)

Definition at line 1125 of file link_cut_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [18/58]

TEST_F	(	LinkCutTreeGcdTest	,
		PathGcd
	)

Definition at line 678 of file link_cut_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [19/58]

TEST_F	(	LinkCutTreeLazyTest	,
		PathApplyAndQuery
	)

Definition at line 729 of file link_cut_tree_test.cc.

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

TEST_F() [20/58]

TEST_F	(	LinkCutTreeLazyTest	,
		PathApplyDisconnectedThrows
	)

Definition at line 755 of file link_cut_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [21/58]

TEST_F	(	LinkCutTreeMaxTest	,
		PathMax
	)

Definition at line 630 of file link_cut_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and N.

TEST_F() [22/58]

TEST_F	(	LinkCutTreeMinTest	,
		PathMin
	)

Definition at line 604 of file link_cut_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and N.

TEST_F() [23/58]

TEST_F	(	LinkCutTreeProductTest	,
		PathProduct
	)

Definition at line 705 of file link_cut_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [24/58]

TEST_F	(	LinkCutTreeStructTest	,
		BuildPath
	)

Definition at line 111 of file link_cut_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and N.

TEST_F() [25/58]

TEST_F	(	LinkCutTreeStructTest	,
		BuildStar
	)

Definition at line 152 of file link_cut_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and N.

TEST_F() [26/58]

TEST_F	(	LinkCutTreeStructTest	,
		CutDisconnects
	)

Definition at line 99 of file link_cut_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [27/58]

TEST_F	(	LinkCutTreeStructTest	,
		CutMiddleOfPath
	)

Definition at line 130 of file link_cut_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and N.

TEST_F() [28/58]

TEST_F	(	LinkCutTreeStructTest	,
		CutNonExistentEdgeThrows
	)

Definition at line 303 of file link_cut_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and w.

TEST_F() [29/58]

TEST_F	(	LinkCutTreeStructTest	,
		DepthOnPath
	)

Definition at line 393 of file link_cut_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and N.

TEST_F() [30/58]

TEST_F	(	LinkCutTreeStructTest	,
		ExportToTreeNodePath
	)

Definition at line 1435 of file link_cut_tree_test.cc.

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

TEST_F() [31/58]

TEST_F	(	LinkCutTreeStructTest	,
		ExportToTreeNodeStar
	)

Definition at line 1472 of file link_cut_tree_test.cc.

References Aleph::destroy_tree(), Aleph::divide_and_conquer_partition_dp(), l1, l2, and l3.

TEST_F() [32/58]

TEST_F	(	LinkCutTreeStructTest	,
		FindRootAcrossAllNodesAfterRepeatedReroots
	)

Definition at line 216 of file link_cut_tree_test.cc.

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

TEST_F() [33/58]

TEST_F	(	LinkCutTreeStructTest	,
		ForEachNode
	)

Definition at line 481 of file link_cut_tree_test.cc.

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

TEST_F() [34/58]

TEST_F	(	LinkCutTreeStructTest	,
		ForEachOnPath
	)

Definition at line 461 of file link_cut_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and N.

TEST_F() [35/58]

TEST_F	(	LinkCutTreeStructTest	,
		LcaDisconnectedThrows
	)

Definition at line 329 of file link_cut_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [36/58]

TEST_F	(	LinkCutTreeStructTest	,
		LcaOnBinaryTree
	)

Definition at line 260 of file link_cut_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [37/58]

TEST_F	(	LinkCutTreeStructTest	,
		LcaOnPath
	)

Definition at line 243 of file link_cut_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and N.

TEST_F() [38/58]

TEST_F	(	LinkCutTreeStructTest	,
		LcaSameNode
	)

Definition at line 237 of file link_cut_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [39/58]

TEST_F	(	LinkCutTreeStructTest	,
		LinkAlreadyConnectedThrows
	)

Definition at line 289 of file link_cut_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [40/58]

TEST_F	(	LinkCutTreeStructTest	,
		LinkEdges
	)

Definition at line 515 of file link_cut_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [41/58]

TEST_F	(	LinkCutTreeStructTest	,
		LinkTwoNodesConnectsThem
	)

Definition at line 86 of file link_cut_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [42/58]

TEST_F	(	LinkCutTreeStructTest	,
		MakePath
	)

Definition at line 496 of file link_cut_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [43/58]

TEST_F	(	LinkCutTreeStructTest	,
		MakeVertices
	)

Definition at line 507 of file link_cut_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [44/58]

TEST_F	(	LinkCutTreeStructTest	,
		MultipleReroots
	)

Definition at line 198 of file link_cut_tree_test.cc.

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

TEST_F() [45/58]

TEST_F	(	LinkCutTreeStructTest	,
		NullHandleThrows
	)

Definition at line 318 of file link_cut_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [46/58]

TEST_F	(	LinkCutTreeStructTest	,
		NumComponents
	)

Definition at line 354 of file link_cut_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [47/58]

TEST_F	(	LinkCutTreeStructTest	,
		ParentOnPath
	)

Definition at line 413 of file link_cut_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and N.

TEST_F() [48/58]

TEST_F	(	LinkCutTreeStructTest	,
		ParentOnStar
	)

Definition at line 436 of file link_cut_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), l1, l2, and l3.

TEST_F() [49/58]

TEST_F	(	LinkCutTreeStructTest	,
		PathOperationsDisconnectedThrow
	)

Definition at line 336 of file link_cut_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [50/58]

TEST_F	(	LinkCutTreeStructTest	,
		RerootPath
	)

Definition at line 182 of file link_cut_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and N.

TEST_F() [51/58]

TEST_F	(	LinkCutTreeStructTest	,
		SelfLinkThrows
	)

Definition at line 297 of file link_cut_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [52/58]

TEST_F	(	LinkCutTreeStructTest	,
		SingleNodeIsItsOwnRoot
	)

Definition at line 65 of file link_cut_tree_test.cc.

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

TEST_F() [53/58]

TEST_F	(	LinkCutTreeStructTest	,
		TreeSize
	)

Definition at line 373 of file link_cut_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [54/58]

TEST_F	(	LinkCutTreeSumTest	,
		PathSum
	)

Definition at line 546 of file link_cut_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and N.

TEST_F() [55/58]

TEST_F	(	LinkCutTreeSumTest	,
		SetValUpdatesAggregate
	)

Definition at line 565 of file link_cut_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [56/58]

TEST_F	(	LinkCutTreeSumTest	,
		SingleNodeQuery
	)

Definition at line 540 of file link_cut_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [57/58]

TEST_F	(	LinkCutTreeSumTest	,
		SumAfterCutAndRelink
	)

Definition at line 577 of file link_cut_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST_F() [58/58]

TEST_F	(	LinkCutTreeXorTest	,
		PathXor
	)

Definition at line 655 of file link_cut_tree_test.cc.

References Aleph::divide_and_conquer_partition_dp().