blossom_test.cc File Reference

Rigorous tests for Blossom.H maximum matching in general graphs. More...

#include <gtest/gtest.h>
#include <algorithm>
#include <bit>
#include <chrono>
#include <cstdint>
#include <cstdlib>
#include <functional>
#include <random>
#include <string>
#include <stdexcept>
#include <utility>
#include <vector>
#include <Blossom.H>
#include <tpl_array.H>
#include <tpl_bipartite.H>
#include <tpl_dynArray.H>
#include <tpl_dynSetTree.H>
#include <tpl_graph.H>
#include <tpl_olhash.H>
#include <tpl_sgraph.H>
#include <tpl_agraph.H>

Include dependency graph for blossom_test.cc:

Go to the source code of this file.

Functions
	TYPED_TEST (BlossomMatchingTypedTest, EmptyGraph)
	TYPED_TEST (BlossomMatchingTypedTest, SingleEdge)
	TYPED_TEST (BlossomMatchingTypedTest, OddCycleC5)
	TYPED_TEST (BlossomMatchingTypedTest, CompleteGraphK6)
	TYPED_TEST (BlossomMatchingTypedTest, BlossomContractionScenario)
	TYPED_TEST (BlossomMatchingTypedTest, HandlesLoopsAndParallelArcs)
	TYPED_TEST (BlossomMatchingTypedTest, FunctorWrapperMatchesFreeFunction)
	TYPED_TEST (BlossomMatchingTypedTest, RandomGraphsAgreeWithExactDP)
	TYPED_TEST (BlossomMatchingTypedTest, AgreesWithHopcroftKarpOnBipartiteGraphs)
	TYPED_TEST (BlossomMatchingTypedTest, NestedOddCyclesWithStems)
	TYPED_TEST (BlossomMatchingTypedTest, FlowerWithSharedCenterAndBridge)
	TYPED_TEST (BlossomMatchingTypedTest, DenseRandomStressCrossBackendAgreement)
	TYPED_TEST (BlossomMatchingTypedTest, BlossomMatchingPerfRegression)
	TEST (BlossomMatchingStandaloneTest, ArcFilterIsRespected)
	TEST (BlossomMatchingStandaloneTest, DigraphThrowsDomainError)

Detailed Description

Rigorous tests for Blossom.H maximum matching in general graphs.

Coverage:

• Deterministic graphs with known optimum
• Graphs that require blossom contraction
• Self-loops and parallel arcs
• Cross-backend validation (List_Graph, List_SGraph, Array_Graph)
• Random small graphs validated against exact DP optimum
• Bipartite subset cross-check with Hopcroft-Karp
• Arc-filter behavior

Definition in file blossom_test.cc.

Function Documentation

TEST() [1/2]

TEST	(	BlossomMatchingStandaloneTest	,
		ArcFilterIsRespected
	)

Definition at line 634 of file blossom_test.cc.

References 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 verify_matching().

TEST() [2/2]

TEST	(	BlossomMatchingStandaloneTest	,
		DigraphThrowsDomainError
	)

Definition at line 661 of file blossom_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TYPED_TEST() [1/13]

TYPED_TEST	(	BlossomMatchingTypedTest	,
		AgreesWithHopcroftKarpOnBipartiteGraphs
	)

Definition at line 445 of file blossom_test.cc.

References Aleph::divide_and_conquer_partition_dp(), l, r, Aleph::DynArray< T >::reserve(), rng, and verify_matching().

TYPED_TEST() [2/13]

TYPED_TEST	(	BlossomMatchingTypedTest	,
		BlossomContractionScenario
	)

Definition at line 350 of file blossom_test.cc.

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

TYPED_TEST() [3/13]

TYPED_TEST	(	BlossomMatchingTypedTest	,
		BlossomMatchingPerfRegression
	)

Definition at line 570 of file blossom_test.cc.

References Aleph::DynArray< T >::append(), Aleph::divide_and_conquer_partition_dp(), Aleph::DynArray< T >::is_empty(), Aleph::DynArray< T >::reserve(), rng, seed, Aleph::DynArray< T >::size(), and verify_matching().

TYPED_TEST() [4/13]

TYPED_TEST	(	BlossomMatchingTypedTest	,
		CompleteGraphK6
	)

Definition at line 330 of file blossom_test.cc.

References Aleph::DynArray< T >::append(), Aleph::divide_and_conquer_partition_dp(), Aleph::DynArray< T >::reserve(), and verify_matching().

TYPED_TEST() [5/13]

TYPED_TEST	(	BlossomMatchingTypedTest	,
		DenseRandomStressCrossBackendAgreement
	)

Definition at line 537 of file blossom_test.cc.

References Aleph::DynArray< T >::append(), Aleph::divide_and_conquer_partition_dp(), Aleph::DynArray< T >::reserve(), rng, and verify_matching().

TYPED_TEST() [6/13]

TYPED_TEST	(	BlossomMatchingTypedTest	,
		EmptyGraph
	)

Definition at line 288 of file blossom_test.cc.

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

TYPED_TEST() [7/13]

TYPED_TEST	(	BlossomMatchingTypedTest	,
		FlowerWithSharedCenterAndBridge
	)

Definition at line 508 of file blossom_test.cc.

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

TYPED_TEST() [8/13]

TYPED_TEST	(	BlossomMatchingTypedTest	,
		FunctorWrapperMatchesFreeFunction
	)

Definition at line 391 of file blossom_test.cc.

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

TYPED_TEST() [9/13]

TYPED_TEST	(	BlossomMatchingTypedTest	,
		HandlesLoopsAndParallelArcs
	)

Definition at line 369 of file blossom_test.cc.

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

TYPED_TEST() [10/13]

TYPED_TEST	(	BlossomMatchingTypedTest	,
		NestedOddCyclesWithStems
	)

Definition at line 481 of file blossom_test.cc.

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

TYPED_TEST() [11/13]

TYPED_TEST	(	BlossomMatchingTypedTest	,
		OddCycleC5
	)

Definition at line 316 of file blossom_test.cc.

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

TYPED_TEST() [12/13]

TYPED_TEST	(	BlossomMatchingTypedTest	,
		RandomGraphsAgreeWithExactDP
	)

Definition at line 411 of file blossom_test.cc.

References Aleph::DynArray< T >::append(), Aleph::divide_and_conquer_partition_dp(), Aleph::DynArray< T >::reserve(), rng, and verify_matching().

TYPED_TEST() [13/13]

TYPED_TEST	(	BlossomMatchingTypedTest	,
		SingleEdge
	)

Definition at line 302 of file blossom_test.cc.

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