hungarian_test.cc File Reference

Comprehensive tests for Hungarian.H. More...

#include <gtest/gtest.h>
#include <random>
#include <set>
#include <Hungarian.H>
#include <tpl_dynMat.H>
#include <tpl_mincost.H>

Include dependency graph for hungarian_test.cc:

Go to the source code of this file.

Functions
template<typename T >
DynMatrix< T >	make_matrix (initializer_list< initializer_list< T > > rows)
template<typename T >
T	compute_assignment_cost (const DynMatrix< T > &cost, const DynList< pair< size_t, size_t > > &pairs)
void	verify_permutation (const Array< long > &row_to_col, const Array< long > &col_to_row, size_t rows, size_t cols)
	TEST (HungarianBasic, Matrix1x1)
	TEST (HungarianBasic, Matrix2x2)
	TEST (HungarianBasic, Matrix3x3)
	TEST (HungarianBasic, Matrix4x4)
	TEST (HungarianBasic, RankOneMatrix4x4)
	TEST (HungarianRectangular, MoreColsThanRows_2x3)
	TEST (HungarianRectangular, MoreRowsThanCols_3x2)
	TEST (HungarianRectangular, Wide_2x5)
	TEST (HungarianRectangular, Tall_5x2)
	TEST (HungarianDegenerate, AllZeros)
	TEST (HungarianDegenerate, AllSameCost)
	TEST (HungarianDegenerate, DiagonalZeros)
	TEST (HungarianDegenerate, Identity)
	TEST (HungarianDegenerate, SingleRow)
	TEST (HungarianDegenerate, SingleColumn)
	TEST (HungarianNumerics, IntegerCosts)
	TEST (HungarianNumerics, DoubleCosts)
	TEST (HungarianNumerics, NegativeCosts)
	TEST (HungarianNumerics, MixedSigns)
	TEST (HungarianNumerics, LargeCosts)
	TEST (HungarianMaximization, Basic3x3)
	TEST (HungarianMaximization, Rectangular)
	TEST (HungarianAPI, InitializerListConstructor)
	TEST (HungarianAPI, FreeFunctionMinimization)
	TEST (HungarianAPI, GetPairsFiltersDummies)
	TEST (HungarianAPI, ConsistencyCheck)
	TEST (HungarianValidation, PermutationProperty)
	TEST (HungarianValidation, CostMatchesSum)
	TEST (HungarianValidation, BruteForce3x3)
	TEST (HungarianValidation, BruteForce4x4)
	TEST (HungarianStress, Random10x10)
	TEST (HungarianStress, Random50x50)
	TEST (HungarianStress, Random100x100)
	TEST (HungarianStress, RandomRectangular_30x50)
	TEST (HungarianStress, CrossValidateWithMinCostFlow)
	TEST (HungarianStress, CrossValidateRandom20x20)

Detailed Description

Comprehensive tests for Hungarian.H.

Tests cover:

• Basic assignment problems (1x1, 2x2, 3x3, 4x4)
• Rectangular matrices
• Degenerate cases (all zeros, identical costs, diagonal)
• Numeric types (int, double, negative costs)
• Maximization
• API (initializer_list, free functions, consistency)
• Validation (permutation property, cost correctness)
• Stress tests (random large matrices)

Definition in file hungarian_test.cc.

Function Documentation

compute_assignment_cost()

template<typename T >

T compute_assignment_cost	(	const DynMatrix< T > &	cost,
		const DynList< pair< size_t, size_t > > &	pairs
	)

Definition at line 81 of file hungarian_test.cc.

References Aleph::divide_and_conquer_partition_dp(), r, and Aleph::DynMatrix< T >::read().

Referenced by TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

make_matrix()

template<typename T >

DynMatrix< T > make_matrix

(

initializer_list< initializer_list< T > >

rows

)

Definition at line 62 of file hungarian_test.cc.

References Aleph::DynMatrix< T >::allocate(), m, and OhashCommon< HashTbl, Key >::size().

TEST() [1/36]

TEST	(	HungarianAPI	,
		ConsistencyCheck
	)

Definition at line 475 of file hungarian_test.cc.

References compute_assignment_cost(), Aleph::divide_and_conquer_partition_dp(), and verify_permutation().

TEST() [2/36]

TEST	(	HungarianAPI	,
		FreeFunctionMinimization
	)

Definition at line 444 of file hungarian_test.cc.

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

TEST() [3/36]

TEST	(	HungarianAPI	,
		GetPairsFiltersDummies
	)

Definition at line 457 of file hungarian_test.cc.

References Aleph::divide_and_conquer_partition_dp(), and r.

TEST() [4/36]

TEST	(	HungarianAPI	,
		InitializerListConstructor
	)

Definition at line 430 of file hungarian_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [5/36]

TEST	(	HungarianBasic	,
		Matrix1x1
	)

Definition at line 131 of file hungarian_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [6/36]

TEST	(	HungarianBasic	,
		Matrix2x2
	)

Definition at line 142 of file hungarian_test.cc.

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

TEST() [7/36]

TEST	(	HungarianBasic	,
		Matrix3x3
	)

Definition at line 157 of file hungarian_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [8/36]

TEST	(	HungarianBasic	,
		Matrix4x4
	)

Definition at line 170 of file hungarian_test.cc.

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

TEST() [9/36]

TEST	(	HungarianBasic	,
		RankOneMatrix4x4
	)

Definition at line 192 of file hungarian_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [10/36]

TEST	(	HungarianDegenerate	,
		AllSameCost
	)

Definition at line 283 of file hungarian_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [11/36]

TEST	(	HungarianDegenerate	,
		AllZeros
	)

Definition at line 275 of file hungarian_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [12/36]

TEST	(	HungarianDegenerate	,
		DiagonalZeros
	)

Definition at line 291 of file hungarian_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [13/36]

TEST	(	HungarianDegenerate	,
		Identity
	)

Definition at line 304 of file hungarian_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [14/36]

TEST	(	HungarianDegenerate	,
		SingleColumn
	)

Definition at line 324 of file hungarian_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [15/36]

TEST	(	HungarianDegenerate	,
		SingleRow
	)

Definition at line 313 of file hungarian_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [16/36]

TEST	(	HungarianMaximization	,
		Basic3x3
	)

Definition at line 399 of file hungarian_test.cc.

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

TEST() [17/36]

TEST	(	HungarianMaximization	,
		Rectangular
	)

Definition at line 417 of file hungarian_test.cc.

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

TEST() [18/36]

TEST	(	HungarianNumerics	,
		DoubleCosts
	)

Definition at line 346 of file hungarian_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [19/36]

TEST	(	HungarianNumerics	,
		IntegerCosts
	)

Definition at line 339 of file hungarian_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [20/36]

TEST	(	HungarianNumerics	,
		LargeCosts
	)

Definition at line 386 of file hungarian_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [21/36]

TEST	(	HungarianNumerics	,
		MixedSigns
	)

Definition at line 377 of file hungarian_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [22/36]

TEST	(	HungarianNumerics	,
		NegativeCosts
	)

Definition at line 353 of file hungarian_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [23/36]

TEST	(	HungarianRectangular	,
		MoreColsThanRows_2x3
	)

Definition at line 215 of file hungarian_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [24/36]

TEST	(	HungarianRectangular	,
		MoreRowsThanCols_3x2
	)

Definition at line 230 of file hungarian_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [25/36]

TEST	(	HungarianRectangular	,
		Tall_5x2
	)

Definition at line 257 of file hungarian_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [26/36]

TEST	(	HungarianRectangular	,
		Wide_2x5
	)

Definition at line 246 of file hungarian_test.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [27/36]

TEST	(	HungarianStress	,
		CrossValidateRandom20x20
	)

Definition at line 695 of file hungarian_test.cc.

References Aleph::DynMatrix< T >::allocate(), Aleph::divide_and_conquer_partition_dp(), N, rng, and Aleph::solve_assignment().

TEST() [28/36]

TEST	(	HungarianStress	,
		CrossValidateWithMinCostFlow
	)

Definition at line 668 of file hungarian_test.cc.

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

TEST() [29/36]

TEST	(	HungarianStress	,
		Random100x100
	)

Definition at line 628 of file hungarian_test.cc.

References Aleph::DynMatrix< T >::allocate(), compute_assignment_cost(), Aleph::divide_and_conquer_partition_dp(), rng, and verify_permutation().

TEST() [30/36]

TEST	(	HungarianStress	,
		Random10x10
	)

Definition at line 588 of file hungarian_test.cc.

References Aleph::DynMatrix< T >::allocate(), compute_assignment_cost(), Aleph::divide_and_conquer_partition_dp(), rng, and verify_permutation().

TEST() [31/36]

TEST	(	HungarianStress	,
		Random50x50
	)

Definition at line 608 of file hungarian_test.cc.

References Aleph::DynMatrix< T >::allocate(), compute_assignment_cost(), Aleph::divide_and_conquer_partition_dp(), rng, and verify_permutation().

TEST() [32/36]

TEST	(	HungarianStress	,
		RandomRectangular_30x50
	)

Definition at line 648 of file hungarian_test.cc.

References Aleph::DynMatrix< T >::allocate(), compute_assignment_cost(), Aleph::divide_and_conquer_partition_dp(), rng, and verify_permutation().

TEST() [33/36]

TEST	(	HungarianValidation	,
		BruteForce3x3
	)

Definition at line 532 of file hungarian_test.cc.

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

TEST() [34/36]

TEST	(	HungarianValidation	,
		BruteForce4x4
	)

Definition at line 559 of file hungarian_test.cc.

References Aleph::divide_and_conquer_partition_dp(), min(), and Aleph::next_permutation().

TEST() [35/36]

TEST	(	HungarianValidation	,
		CostMatchesSum
	)

Definition at line 518 of file hungarian_test.cc.

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

TEST() [36/36]

TEST	(	HungarianValidation	,
		PermutationProperty
	)

Definition at line 497 of file hungarian_test.cc.

References Aleph::divide_and_conquer_partition_dp().

verify_permutation()

void verify_permutation	(	const Array< long > &	row_to_col,
		const Array< long > &	col_to_row,
		size_t	rows,
		size_t	cols
	)

Definition at line 94 of file hungarian_test.cc.

References Aleph::divide_and_conquer_partition_dp().

Referenced by TEST(), TEST(), TEST(), TEST(), and TEST().