min_cost_matching_test.cc File Reference

Rigorous tests for Min_Cost_Matching.H. More...

#include <gtest/gtest.h>
#include <algorithm>
#include <bit>
#include <chrono>
#include <cstdint>
#include <functional>
#include <initializer_list>
#include <limits>
#include <ostream>
#include <random>
#include <stdexcept>
#include <tuple>
#include <utility>
#include <Blossom_Weighted.H>
#include <Min_Cost_Matching.H>
#include <tpl_agraph.H>
#include <tpl_array.H>
#include <tpl_dynMapTree.H>
#include <tpl_dynSetTree.H>
#include <tpl_graph.H>
#include <tpl_sgraph.H>

Include dependency graph for min_cost_matching_test.cc:

Go to the source code of this file.

Functions
	TEST (MinCostMatchingStandaloneTest, EmptyGraph)
	TEST (MinCostMatchingStandaloneTest, PositiveSingleEdgeIllustratesObjectiveModes)
	TEST (MinCostMatchingStandaloneTest, ParallelArcsUseCheapestArc)
	TEST (MinCostMatchingStandaloneTest, DigraphThrowsDomainError)
	TEST (MinCostMatchingStandaloneTest, LLONGMinCostThrowsOverflow)
	TEST (MinCostMatchingStandaloneTest, UnsignedCostAboveLongLongRangeThrowsOverflow)
	TEST (MinCostMatchingStandaloneTest, FreeAliasAndFunctorAgree)
	TEST (MinCostMatchingStandaloneTest, MatchesNegatedWeightedBlossomObjective)
	TEST (MinCostMatchingPerfectStandaloneTest, EmptyGraphIsPerfectlyMatchable)
	TEST (MinCostMatchingPerfectStandaloneTest, OddNodeCountIsInfeasible)
	TEST (MinCostMatchingPerfectStandaloneTest, EvenNodeCountCanStillBeInfeasible)
	TEST (MinCostMatchingPerfectStandaloneTest, DigraphThrowsDomainError)
	TEST (MinCostMatchingPerfectStandaloneTest, FeasiblePerfectMatchingMatchesExactOracle)
	TEST (MinCostMatchingPerfectStandaloneTest, AliasAndFunctorAgree)
	TEST (MinCostMatchingBackendsTest, DeterministicScenarioMatchesExactAcrossBackends)
	TEST (MinCostMatchingPerfectBackendsTest, RandomSmallGraphsMatchExactPerfectOracle)
	TEST (MinCostMatchingBackendsTest, RandomSmallGraphsMatchExactOptimum)
	TEST (MinCostMatchingBackendsTest, DISABLED_PerfRegressionLargeFixedSeed)

Detailed Description

Rigorous tests for Min_Cost_Matching.H.

Coverage:

• Deterministic non-bipartite costed instances
• Objective-mode behavior (pure minimum-cost vs max-cardinality + min-cost)
• Parallel arcs, loops, and domain/overflow validations
• Cross-backend consistency (List_Graph, List_SGraph, Array_Graph)
• Random small-graph validation against exact exponential DP oracle

Definition in file min_cost_matching_test.cc.

Function Documentation

TEST() [1/18]

TEST	(	MinCostMatchingBackendsTest	,
		DeterministicScenarioMatchesExactAcrossBackends
	)

Definition at line 720 of file min_cost_matching_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [2/18]

TEST	(	MinCostMatchingBackendsTest	,
		DISABLED_PerfRegressionLargeFixedSeed
	)

Definition at line 852 of file min_cost_matching_test.cc.

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

TEST() [3/18]

TEST	(	MinCostMatchingBackendsTest	,
		RandomSmallGraphsMatchExactOptimum
	)

Definition at line 801 of file min_cost_matching_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and rng.

TEST() [4/18]

TEST	(	MinCostMatchingPerfectBackendsTest	,
		RandomSmallGraphsMatchExactPerfectOracle
	)

Definition at line 751 of file min_cost_matching_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and rng.

TEST() [5/18]

TEST	(	MinCostMatchingPerfectStandaloneTest	,
		AliasAndFunctorAgree
	)

Definition at line 686 of file min_cost_matching_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [6/18]

TEST	(	MinCostMatchingPerfectStandaloneTest	,
		DigraphThrowsDomainError
	)

Definition at line 640 of file min_cost_matching_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [7/18]

TEST	(	MinCostMatchingPerfectStandaloneTest	,
		EmptyGraphIsPerfectlyMatchable
	)

Definition at line 585 of file min_cost_matching_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [8/18]

TEST	(	MinCostMatchingPerfectStandaloneTest	,
		EvenNodeCountCanStillBeInfeasible
	)

Definition at line 620 of file min_cost_matching_test.cc.

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

TEST() [9/18]

TEST	(	MinCostMatchingPerfectStandaloneTest	,
		FeasiblePerfectMatchingMatchesExactOracle
	)

Definition at line 655 of file min_cost_matching_test.cc.

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

TEST() [10/18]

TEST	(	MinCostMatchingPerfectStandaloneTest	,
		OddNodeCountIsInfeasible
	)

Definition at line 600 of file min_cost_matching_test.cc.

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

TEST() [11/18]

TEST	(	MinCostMatchingStandaloneTest	,
		DigraphThrowsDomainError
	)

Definition at line 462 of file min_cost_matching_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [12/18]

TEST	(	MinCostMatchingStandaloneTest	,
		EmptyGraph
	)

Definition at line 388 of file min_cost_matching_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [13/18]

TEST	(	MinCostMatchingStandaloneTest	,
		FreeAliasAndFunctorAgree
	)

Definition at line 509 of file min_cost_matching_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [14/18]

TEST	(	MinCostMatchingStandaloneTest	,
		LLONGMinCostThrowsOverflow
	)

Definition at line 477 of file min_cost_matching_test.cc.

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

TEST() [15/18]

TEST	(	MinCostMatchingStandaloneTest	,
		MatchesNegatedWeightedBlossomObjective
	)

Definition at line 545 of file min_cost_matching_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [16/18]

TEST	(	MinCostMatchingStandaloneTest	,
		ParallelArcsUseCheapestArc
	)

Definition at line 431 of file min_cost_matching_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() [17/18]

TEST	(	MinCostMatchingStandaloneTest	,
		PositiveSingleEdgeIllustratesObjectiveModes
	)

Definition at line 402 of file min_cost_matching_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() [18/18]

TEST	(	MinCostMatchingStandaloneTest	,
		UnsignedCostAboveLongLongRangeThrowsOverflow
	)

Definition at line 492 of file min_cost_matching_test.cc.

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