#include <boost/test/unit_test.hpp>
#include <core/union_find.h>
#include <algorithm>
#include <atomic>
#include <map>
#include <random>
#include <thread>
#include <vector>

Functions
	BOOST_AUTO_TEST_CASE (MatchesReferenceImplementation)
	The partition, the merge count and the component count must all track a reference implementation exactly, across a spread of graph densities.

	BOOST_AUTO_TEST_CASE (RootIsMinimumOfComponent)
	Rem's algorithm roots every tree at the smallest index it holds.

	BOOST_AUTO_TEST_CASE (CompressionPreservesPartition)
	FindCompress() rewrites the tree as it walks.

	BOOST_AUTO_TEST_CASE (ConcurrentUniteMatchesSerial)
	Unite() is the one entry point SearchClusters() calls from several threads at once.

	BOOST_AUTO_TEST_CASE (ReverseChainUnderContention)
	A chain united back to front is the worst case for Rem's interleaved climb: every union walks the length of the tree built so far.

	BOOST_AUTO_TEST_CASE (DegenerateSizes)

	BOOST_AUTO_TEST_CASE (ResetClearsState)

Function Documentation

◆ BOOST_AUTO_TEST_CASE() [1/7]

BOOST_AUTO_TEST_CASE ( CompressionPreservesPartition )

FindCompress() rewrites the tree as it walks.

It must return what Find() would have, and must not disturb the partition.

Definition at line 180 of file test_union_find.cpp.

References KI_UNION_FIND::Find(), KI_UNION_FIND::FindCompress(), rng, and KI_UNION_FIND::Unite().

◆ BOOST_AUTO_TEST_CASE() [2/7]

BOOST_AUTO_TEST_CASE ( ConcurrentUniteMatchesSerial )

Unite() is the one entry point SearchClusters() calls from several threads at once.

The final partition must not depend on how the edges were divided up, and exactly one caller may see true per merge or Kruskal would emit a cycle.

Definition at line 211 of file test_union_find.cpp.

References BOOST_CHECK_EQUAL(), KI_UNION_FIND::ComponentCount(), KI_UNION_FIND::Connected(), rng, and KI_UNION_FIND::Unite().

◆ BOOST_AUTO_TEST_CASE() [3/7]

BOOST_AUTO_TEST_CASE ( DegenerateSizes )

Definition at line 298 of file test_union_find.cpp.

References BOOST_CHECK_EQUAL(), KI_UNION_FIND::ComponentCount(), KI_UNION_FIND::Connected(), empty(), KI_UNION_FIND::Find(), and KI_UNION_FIND::Unite().

◆ BOOST_AUTO_TEST_CASE() [4/7]

BOOST_AUTO_TEST_CASE ( MatchesReferenceImplementation )

The partition, the merge count and the component count must all track a reference implementation exactly, across a spread of graph densities.

Definition at line 104 of file test_union_find.cpp.

References BOOST_AUTO_TEST_CASE(), KI_UNION_FIND::ComponentCount(), KI_UNION_FIND::Connected(), rng, and KI_UNION_FIND::Unite().

◆ BOOST_AUTO_TEST_CASE() [5/7]

BOOST_AUTO_TEST_CASE ( ResetClearsState )

Definition at line 317 of file test_union_find.cpp.

References BOOST_CHECK_EQUAL(), KI_UNION_FIND::ComponentCount(), KI_UNION_FIND::Find(), KI_UNION_FIND::Reset(), KI_UNION_FIND::Size(), and KI_UNION_FIND::Unite().

◆ BOOST_AUTO_TEST_CASE() [6/7]

BOOST_AUTO_TEST_CASE ( ReverseChainUnderContention )

A chain united back to front is the worst case for Rem's interleaved climb: every union walks the length of the tree built so far.

It must still terminate and collapse to one component.

Definition at line 264 of file test_union_find.cpp.

References BOOST_CHECK_EQUAL(), KI_UNION_FIND::ComponentCount(), KI_UNION_FIND::Find(), and KI_UNION_FIND::Unite().

◆ BOOST_AUTO_TEST_CASE() [7/7]

BOOST_AUTO_TEST_CASE ( RootIsMinimumOfComponent )

Rem's algorithm roots every tree at the smallest index it holds.

SearchClusters() relies on this only through Find() agreeing with itself, but a broken link direction would show up here first and would silently corrupt the clustering rather than crash.

Definition at line 147 of file test_union_find.cpp.

References KI_UNION_FIND::Find(), rng, and KI_UNION_FIND::Unite().

Functions