weighted_blossom_test.cc File Reference

Rigorous tests for Blossom_Weighted.H. More...

#include <gtest/gtest.h>
#include <algorithm>
#include <cstdint>
#include <functional>
#include <limits>
#include <random>
#include <stdexcept>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <Blossom_Weighted.H>
#include <tpl_agraph.H>
#include <tpl_graph.H>
#include <tpl_sgraph.H>

Include dependency graph for weighted_blossom_test.cc:

Go to the source code of this file.

Functions
	TYPED_TEST (WeightedBlossomTypedTest, EmptyGraph)
	TYPED_TEST (WeightedBlossomTypedTest, SinglePositiveEdge)
	TYPED_TEST (WeightedBlossomTypedTest, ParallelEdgesAndLoops)
	TYPED_TEST (WeightedBlossomTypedTest, NegativeWeightsDefaultAndMaxCardinality)
	TYPED_TEST (WeightedBlossomTypedTest, WeightedBlossomRegressionCases)
	TYPED_TEST (WeightedBlossomTypedTest, RandomSmallGraphsAgainstExactDP)
	TEST (WeightedBlossomStandaloneTest, CrossBackendUniqueOptimumConsistency)
	TEST (WeightedBlossomStandaloneTest, CrossBackendRandomObjectiveConsistency)
	TEST (WeightedBlossomStandaloneTest, ArcFilterIsRespected)
	TEST (WeightedBlossomStandaloneTest, DigraphThrowsDomainError)
	TEST (WeightedBlossomStandaloneTest, MaxCardinalityCanBeatPureWeightCardinality)
	TEST (WeightedBlossomMwMatchingStandaloneTest, FloatingWeightsAndFiniteValidation)
	TEST (WeightedBlossomMwMatchingStandaloneTest, RejectsSelfLoopsAndDuplicateEdges)
	TEST (WeightedBlossomMwMatchingStandaloneTest, RejectsUnsafeIntegerRanges)
	TEST (WeightedBlossomStandaloneTest, ToLlCheckedRejectsOverflow)
	TEST (WeightedBlossomStandaloneTest, StressLargeRandomGraphsCrossBackendConsistency)

Detailed Description

Rigorous tests for Blossom_Weighted.H.

Coverage:

• Deterministic blossom-heavy weighted instances
• Negative-weight behavior and max-cardinality mode
• Parallel arcs and loops handling
• Arc-filter behavior
• Cross-backend consistency (List_Graph, List_SGraph, Array_Graph)
• Random small graphs validated against exact exponential DP optimum

Definition in file weighted_blossom_test.cc.

Function Documentation

TEST() [1/10]

TEST	(	WeightedBlossomMwMatchingStandaloneTest	,
		FloatingWeightsAndFiniteValidation
	)

Definition at line 710 of file weighted_blossom_test.cc.

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

TEST() [2/10]

TEST	(	WeightedBlossomMwMatchingStandaloneTest	,
		RejectsSelfLoopsAndDuplicateEdges
	)

Definition at line 741 of file weighted_blossom_test.cc.

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

TEST() [3/10]

TEST	(	WeightedBlossomMwMatchingStandaloneTest	,
		RejectsUnsafeIntegerRanges
	)

Definition at line 758 of file weighted_blossom_test.cc.

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

TEST() [4/10]

TEST	(	WeightedBlossomStandaloneTest	,
		ArcFilterIsRespected
	)

Definition at line 627 of file weighted_blossom_test.cc.

References Aleph::blossom_maximum_weight_matching(), 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() [5/10]

TEST	(	WeightedBlossomStandaloneTest	,
		CrossBackendRandomObjectiveConsistency
	)

Definition at line 564 of file weighted_blossom_test.cc.

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

TEST() [6/10]

TEST	(	WeightedBlossomStandaloneTest	,
		CrossBackendUniqueOptimumConsistency
	)

Definition at line 527 of file weighted_blossom_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [7/10]

TEST	(	WeightedBlossomStandaloneTest	,
		DigraphThrowsDomainError
	)

Definition at line 658 of file weighted_blossom_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [8/10]

TEST	(	WeightedBlossomStandaloneTest	,
		MaxCardinalityCanBeatPureWeightCardinality
	)

Definition at line 674 of file weighted_blossom_test.cc.

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

TEST() [9/10]

TEST	(	WeightedBlossomStandaloneTest	,
		StressLargeRandomGraphsCrossBackendConsistency
	)

Definition at line 809 of file weighted_blossom_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and rng.

TEST() [10/10]

TEST	(	WeightedBlossomStandaloneTest	,
		ToLlCheckedRejectsOverflow
	)

Definition at line 784 of file weighted_blossom_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and LL.

TYPED_TEST() [1/6]

TYPED_TEST	(	WeightedBlossomTypedTest	,
		EmptyGraph
	)

Definition at line 399 of file weighted_blossom_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TYPED_TEST() [2/6]

TYPED_TEST	(	WeightedBlossomTypedTest	,
		NegativeWeightsDefaultAndMaxCardinality
	)

Definition at line 439 of file weighted_blossom_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TYPED_TEST() [3/6]

TYPED_TEST	(	WeightedBlossomTypedTest	,
		ParallelEdgesAndLoops
	)

Definition at line 422 of file weighted_blossom_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TYPED_TEST() [4/6]

TYPED_TEST	(	WeightedBlossomTypedTest	,
		RandomSmallGraphsAgainstExactDP
	)

Definition at line 488 of file weighted_blossom_test.cc.

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

TYPED_TEST() [5/6]

TYPED_TEST	(	WeightedBlossomTypedTest	,
		SinglePositiveEdge
	)

Definition at line 414 of file weighted_blossom_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TYPED_TEST() [6/6]

TYPED_TEST	(	WeightedBlossomTypedTest	,
		WeightedBlossomRegressionCases
	)

Definition at line 455 of file weighted_blossom_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and w.