#include <gtest/gtest.h>
#include <tpl_maxflow.H>
#include <tpl_net.H>
#include <chrono>
#include <random>
#include <stdexcept>

Include dependency graph for tpl_maxflow_test.cc:

Functions
	TEST (DinicTest, LinearNetwork)

	TEST (DinicTest, DiamondNetwork)

	TEST (DinicTest, ComplexNetwork)

	TEST (DinicTest, ZeroCapacity)

	TEST (DinicTest, SingleArc)

	TEST (CapacityScalingTest, LinearNetwork)

	TEST (CapacityScalingTest, DiamondNetwork)

	TEST (CapacityScalingTest, ComplexNetwork)

	TEST (CapacityScalingTest, LargeCapacities)

	TEST (HLPPTest, LinearNetwork)

	TEST (HLPPTest, DiamondNetwork)

	TEST (HLPPTest, ComplexNetwork)

	TEST (FlowDecompositionTest, LinearFlow)

	TEST (FlowDecompositionTest, DiamondFlow)

	TEST (FlowDecompositionTest, ComplexFlow)

	TEST (FlowDecompositionTest, ZeroFlow)

	TEST (FlowDecompositionTest, CycleDetection)

	TEST (FlowStatisticsTest, BeforeFlow)

	TEST (FlowStatisticsTest, AfterFlow)

template<class Net >
double	compute_min_cut_capacity (Net &net)

template<class Net >
bool	verify_max_flow_min_cut (Net &net, double max_flow)

	TEST (MinCutTest, LinearNetwork)

	TEST (MinCutTest, DiamondNetwork)

	TEST (MinCutTest, ComplexNetwork)

	TEST (MinCutTest, GridNetwork)

	TEST (MinCutTest, SingleBottleneck)

	TEST (MinCutTest, ParallelArcs)

	TEST (MinCutTest, AllAlgorithmsGiveSameMinCut)

	TEST (MinCutTest, VerifyCutPartition)

	TEST (AlgorithmComparisonTest, AllAlgorithmsAgree)

	TEST (AlgorithmComparisonTest, GridNetwork)

	TEST (EdgeCasesTest, ParallelArcs)

	TEST (EdgeCasesTest, SourceBottleneck)

	TEST (EdgeCasesTest, SinkBottleneck)

	TEST (FunctorTest, DinicFunctor)

	TEST (FunctorTest, CapacityScalingFunctor)

	TEST (FunctorTest, HLPPFunctor)

	TEST (FunctorTest, DecomposeFunctor)

	TEST (PerformanceTest, Benchmark)

	TEST (RegressionTest, HLPPDisconnectedNodeRelabel)

Node *	build_antiparallel_network (TestNet &net)

	TEST (AntiParallelTest, AllAlgorithmsAgreeOnAntiParallel)

	TEST (AntiParallelTest, PureAntiParallel)

	TEST (CapacityScalingTest, FractionalCapacities)

	TEST (CapacityScalingTest, MixedIntegerFractional)

template<class Net >
void	verify_flow_conservation (const Net &net)

	TEST (HLPPStressTest, LadderNetwork)

	TEST (HLPPStressTest, HighExcessBottleneck)

	TEST (FlowDecompositionTest, ArcFlowConsistency)

	TEST (FlowDecompositionTest, Phase2CycleClosingNode)

	TEST (FlowDecompositionTest, Phase1CycleClosingNode)

	TEST (DisconnectedTest, ZeroCapacityBottleneck)

	TEST (DisconnectedTest, InvalidNetworkThrows)

	TEST (DinicStressTest, LongChain)

	TEST (DinicStressTest, WideParallel)

	TEST (RandomStressTest, SmallRandomGraphs)

	TEST (RandomStressTest, MediumRandomGraphs)

	TEST (IntegerFlowTest, AllAlgorithmsAgree)

	TEST (IntegerFlowTest, ComplexIntegerNetwork)

	TEST (IntegerFlowTest, RandomIntegerGraphs)

	TEST (IntegerFlowTest, MinCutVerification)

int	main (int argc, char **argv)

Function Documentation

◆ build_antiparallel_network()

Node * build_antiparallel_network ( TestNet & net )

Definition at line 923 of file tpl_maxflow_test.cc.

References Aleph::Net_Graph< NodeT, ArcT >::insert_arc(), and Aleph::Net_Graph< NodeT, ArcT >::insert_node().

Referenced by TEST().

◆ compute_min_cut_capacity()

template<class Net >

double compute_min_cut_capacity ( Net & net )

◆ main()

int main	(	int	argc,
		char **	argv
	)

Definition at line 1730 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

◆ TEST() [1/57]

TEST	(	AlgorithmComparisonTest	,
		AllAlgorithmsAgree
	)

Definition at line 688 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::capacity_scaling_maximum_flow(), Aleph::dinic_maximum_flow(), Aleph::edmonds_karp_maximum_flow(), and Aleph::ford_fulkerson_maximum_flow().

◆ TEST() [2/57]

TEST	(	AlgorithmComparisonTest	,
		GridNetwork
	)

Definition at line 707 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), build_grid_network(), Aleph::capacity_scaling_maximum_flow(), Aleph::dinic_maximum_flow(), Aleph::edmonds_karp_maximum_flow(), and Aleph::size().

◆ TEST() [3/57]

TEST	(	AntiParallelTest	,
		AllAlgorithmsAgreeOnAntiParallel
	)

Definition at line 939 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), build_antiparallel_network(), Aleph::capacity_scaling_maximum_flow(), Aleph::dinic_maximum_flow(), Aleph::edmonds_karp_maximum_flow(), Aleph::ford_fulkerson_maximum_flow(), Aleph::hlpp_maximum_flow(), and verify_max_flow_min_cut().

◆ TEST() [4/57]

TEST	(	AntiParallelTest	,
		PureAntiParallel
	)

Definition at line 975 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Net_Graph< NodeT, ArcT >::check_network(), Aleph::dinic_maximum_flow(), Aleph::Net_Graph< NodeT, ArcT >::insert_arc(), and Aleph::Net_Graph< NodeT, ArcT >::insert_node().

◆ TEST() [5/57]

TEST	(	CapacityScalingTest	,
		ComplexNetwork
	)

Definition at line 206 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::capacity_scaling_maximum_flow(), and Aleph::Net_Graph< NodeT, ArcT >::check_network().

◆ TEST() [6/57]

TEST	(	CapacityScalingTest	,
		DiamondNetwork
	)

Definition at line 195 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::capacity_scaling_maximum_flow(), and Aleph::Net_Graph< NodeT, ArcT >::check_network().

◆ TEST() [7/57]

TEST	(	CapacityScalingTest	,
		FractionalCapacities
	)

Definition at line 1002 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::capacity_scaling_maximum_flow(), Aleph::dinic_maximum_flow(), Aleph::Net_Graph< NodeT, ArcT >::insert_arc(), and Aleph::Net_Graph< NodeT, ArcT >::insert_node().

◆ TEST() [8/57]

TEST	(	CapacityScalingTest	,
		LargeCapacities
	)

Definition at line 217 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::capacity_scaling_maximum_flow(), Aleph::Net_Graph< NodeT, ArcT >::insert_arc(), and Aleph::Net_Graph< NodeT, ArcT >::insert_node().

◆ TEST() [9/57]

TEST	(	CapacityScalingTest	,
		LinearNetwork
	)

Definition at line 184 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::capacity_scaling_maximum_flow(), and Aleph::Net_Graph< NodeT, ArcT >::check_network().

◆ TEST() [10/57]

TEST	(	CapacityScalingTest	,
		MixedIntegerFractional
	)

Definition at line 1023 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::capacity_scaling_maximum_flow(), Aleph::dinic_maximum_flow(), Aleph::Net_Graph< NodeT, ArcT >::insert_arc(), and Aleph::Net_Graph< NodeT, ArcT >::insert_node().

◆ TEST() [11/57]

TEST	(	DinicStressTest	,
		LongChain
	)

Definition at line 1402 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Net_Graph< NodeT, ArcT >::check_network(), Aleph::dinic_maximum_flow(), Aleph::Net_Graph< NodeT, ArcT >::insert_arc(), and Aleph::Net_Graph< NodeT, ArcT >::insert_node().

◆ TEST() [12/57]

TEST	(	DinicStressTest	,
		WideParallel
	)

Definition at line 1425 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Net_Graph< NodeT, ArcT >::check_network(), Aleph::dinic_maximum_flow(), Aleph::hlpp_maximum_flow(), Aleph::Net_Graph< NodeT, ArcT >::insert_arc(), and Aleph::Net_Graph< NodeT, ArcT >::insert_node().

◆ TEST() [13/57]

TEST	(	DinicTest	,
		ComplexNetwork
	)

Definition at line 143 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Net_Graph< NodeT, ArcT >::check_network(), and Aleph::dinic_maximum_flow().

◆ TEST() [14/57]

TEST	(	DinicTest	,
		DiamondNetwork
	)

Definition at line 131 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Net_Graph< NodeT, ArcT >::check_network(), and Aleph::dinic_maximum_flow().

◆ TEST() [15/57]

TEST	(	DinicTest	,
		LinearNetwork
	)

Definition at line 120 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Net_Graph< NodeT, ArcT >::check_network(), and Aleph::dinic_maximum_flow().

◆ TEST() [16/57]

TEST	(	DinicTest	,
		SingleArc
	)

Definition at line 168 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::dinic_maximum_flow(), Aleph::Net_Graph< NodeT, ArcT >::insert_arc(), and Aleph::Net_Graph< NodeT, ArcT >::insert_node().

◆ TEST() [17/57]

TEST	(	DinicTest	,
		ZeroCapacity
	)

Definition at line 155 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::dinic_maximum_flow(), Aleph::Net_Graph< NodeT, ArcT >::insert_arc(), and Aleph::Net_Graph< NodeT, ArcT >::insert_node().

◆ TEST() [18/57]

TEST	(	DisconnectedTest	,
		InvalidNetworkThrows
	)

Definition at line 1378 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::capacity_scaling_maximum_flow(), Aleph::dinic_maximum_flow(), Aleph::hlpp_maximum_flow(), Aleph::Net_Graph< NodeT, ArcT >::insert_arc(), and Aleph::Net_Graph< NodeT, ArcT >::insert_node().

◆ TEST() [19/57]

TEST	(	DisconnectedTest	,
		ZeroCapacityBottleneck
	)

Definition at line 1362 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::dinic_maximum_flow(), Aleph::Net_Graph< NodeT, ArcT >::insert_arc(), and Aleph::Net_Graph< NodeT, ArcT >::insert_node().

◆ TEST() [20/57]

TEST	(	EdgeCasesTest	,
		ParallelArcs
	)

Definition at line 729 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::dinic_maximum_flow(), Aleph::Net_Graph< NodeT, ArcT >::insert_arc(), and Aleph::Net_Graph< NodeT, ArcT >::insert_node().

◆ TEST() [21/57]

TEST	(	EdgeCasesTest	,
		SinkBottleneck
	)

Definition at line 758 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::dinic_maximum_flow(), Aleph::Net_Graph< NodeT, ArcT >::insert_arc(), and Aleph::Net_Graph< NodeT, ArcT >::insert_node().

◆ TEST() [22/57]

TEST	(	EdgeCasesTest	,
		SourceBottleneck
	)

Definition at line 744 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::dinic_maximum_flow(), Aleph::Net_Graph< NodeT, ArcT >::insert_arc(), and Aleph::Net_Graph< NodeT, ArcT >::insert_node().

◆ TEST() [23/57]

TEST	(	FlowDecompositionTest	,
		ArcFlowConsistency
	)

Definition at line 1204 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::decompose_flow(), Aleph::dinic_maximum_flow(), and Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne().

◆ TEST() [24/57]

TEST	(	FlowDecompositionTest	,
		ComplexFlow
	)

Definition at line 299 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::decompose_flow(), and Aleph::dinic_maximum_flow().

◆ TEST() [25/57]

TEST	(	FlowDecompositionTest	,
		CycleDetection
	)

Definition at line 331 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::decompose_flow(), Aleph::Net_Graph< NodeT, ArcT >::insert_arc(), and Aleph::Net_Graph< NodeT, ArcT >::insert_node().

◆ TEST() [26/57]

TEST	(	FlowDecompositionTest	,
		DiamondFlow
	)

Definition at line 286 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::decompose_flow(), and Aleph::dinic_maximum_flow().

◆ TEST() [27/57]

TEST	(	FlowDecompositionTest	,
		LinearFlow
	)

Definition at line 274 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::decompose_flow(), and Aleph::dinic_maximum_flow().

◆ TEST() [28/57]

TEST	(	FlowDecompositionTest	,
		Phase1CycleClosingNode
	)

Definition at line 1312 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::decompose_flow(), Aleph::Net_Graph< NodeT, ArcT >::insert_arc(), Aleph::Net_Graph< NodeT, ArcT >::insert_node(), and last_node.

◆ TEST() [29/57]

TEST	(	FlowDecompositionTest	,
		Phase2CycleClosingNode
	)

Definition at line 1251 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::decompose_flow(), Aleph::Net_Graph< NodeT, ArcT >::insert_arc(), Aleph::Net_Graph< NodeT, ArcT >::insert_node(), and last_node.

◆ TEST() [30/57]

TEST	(	FlowDecompositionTest	,
		ZeroFlow
	)

Definition at line 313 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::decompose_flow(), Aleph::Net_Graph< NodeT, ArcT >::insert_arc(), and Aleph::Net_Graph< NodeT, ArcT >::insert_node().

◆ TEST() [31/57]

TEST	(	FlowStatisticsTest	,
		AfterFlow
	)

Definition at line 395 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::compute_flow_statistics(), and Aleph::dinic_maximum_flow().

◆ TEST() [32/57]

TEST	(	FlowStatisticsTest	,
		BeforeFlow
	)

Definition at line 382 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::compute_flow_statistics().

◆ TEST() [33/57]

TEST	(	FunctorTest	,
		CapacityScalingFunctor
	)

Definition at line 787 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

◆ TEST() [34/57]

TEST	(	FunctorTest	,
		DecomposeFunctor
	)

Definition at line 807 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::dinic_maximum_flow().

◆ TEST() [35/57]

TEST	(	FunctorTest	,
		DinicFunctor
	)

Definition at line 777 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

◆ TEST() [36/57]

TEST	(	FunctorTest	,
		HLPPFunctor
	)

Definition at line 797 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

◆ TEST() [37/57]

TEST	(	HLPPStressTest	,
		HighExcessBottleneck
	)

Definition at line 1172 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Net_Graph< NodeT, ArcT >::check_network(), Aleph::hlpp_maximum_flow(), Aleph::Net_Graph< NodeT, ArcT >::insert_arc(), and Aleph::Net_Graph< NodeT, ArcT >::insert_node().

◆ TEST() [38/57]

TEST	(	HLPPStressTest	,
		LadderNetwork
	)

Definition at line 1082 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Net_Graph< NodeT, ArcT >::check_network(), Aleph::Array< T >::create(), Aleph::dinic_maximum_flow(), Aleph::edmonds_karp_maximum_flow(), Aleph::hlpp_maximum_flow(), Aleph::Net_Graph< NodeT, ArcT >::insert_arc(), Aleph::Net_Graph< NodeT, ArcT >::insert_node(), and N.

◆ TEST() [39/57]

TEST	(	HLPPTest	,
		ComplexNetwork
	)

Definition at line 258 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Net_Graph< NodeT, ArcT >::check_network(), and Aleph::hlpp_maximum_flow().

◆ TEST() [40/57]

TEST	(	HLPPTest	,
		DiamondNetwork
	)

Definition at line 247 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Net_Graph< NodeT, ArcT >::check_network(), and Aleph::hlpp_maximum_flow().

◆ TEST() [41/57]

TEST	(	HLPPTest	,
		LinearNetwork
	)

Definition at line 236 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Net_Graph< NodeT, ArcT >::check_network(), and Aleph::hlpp_maximum_flow().

◆ TEST() [42/57]

TEST	(	IntegerFlowTest	,
		AllAlgorithmsAgree
	)

Definition at line 1579 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::capacity_scaling_maximum_flow(), Aleph::dinic_maximum_flow(), Aleph::edmonds_karp_maximum_flow(), Aleph::hlpp_maximum_flow(), and Aleph::Net_Cap_Graph< NodeT, ArcT >::insert_node().

◆ TEST() [43/57]

TEST	(	IntegerFlowTest	,
		ComplexIntegerNetwork
	)

Definition at line 1615 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::capacity_scaling_maximum_flow(), Aleph::dinic_maximum_flow(), Aleph::hlpp_maximum_flow(), and Aleph::Net_Cap_Graph< NodeT, ArcT >::insert_node().

◆ TEST() [44/57]

TEST	(	IntegerFlowTest	,
		MinCutVerification
	)

Definition at line 1683 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::dinic_maximum_flow(), Aleph::hlpp_maximum_flow(), Aleph::Net_Cap_Graph< NodeT, ArcT >::insert_node(), and Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne().

◆ TEST() [45/57]

TEST	(	IntegerFlowTest	,
		RandomIntegerGraphs
	)

Definition at line 1653 of file tpl_maxflow_test.cc.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), Aleph::capacity_scaling_maximum_flow(), Aleph::dinic_maximum_flow(), Aleph::edmonds_karp_maximum_flow(), Aleph::hlpp_maximum_flow(), and seed.

◆ TEST() [46/57]

TEST	(	MinCutTest	,
		AllAlgorithmsGiveSameMinCut
	)

Definition at line 576 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::capacity_scaling_maximum_flow(), compute_min_cut_capacity(), Aleph::dinic_maximum_flow(), Aleph::edmonds_karp_maximum_flow(), Aleph::ford_fulkerson_maximum_flow(), and verify_max_flow_min_cut().

◆ TEST() [47/57]

TEST	(	MinCutTest	,
		ComplexNetwork
	)

Definition at line 509 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), compute_min_cut_capacity(), Aleph::dinic_maximum_flow(), Aleph::min_cut(), and verify_max_flow_min_cut().

◆ TEST() [48/57]

TEST	(	MinCutTest	,
		DiamondNetwork
	)

Definition at line 496 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), compute_min_cut_capacity(), Aleph::dinic_maximum_flow(), Aleph::min_cut(), and verify_max_flow_min_cut().

◆ TEST() [49/57]

TEST	(	MinCutTest	,
		GridNetwork
	)

Definition at line 522 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), build_grid_network(), Aleph::edmonds_karp_maximum_flow(), and verify_max_flow_min_cut().

◆ TEST() [50/57]

TEST	(	MinCutTest	,
		LinearNetwork
	)

Definition at line 481 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), compute_min_cut_capacity(), Aleph::dinic_maximum_flow(), Aleph::min_cut(), and verify_max_flow_min_cut().

◆ TEST() [51/57]

TEST	(	MinCutTest	,
		ParallelArcs
	)

Definition at line 556 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), compute_min_cut_capacity(), Aleph::dinic_maximum_flow(), Aleph::Net_Graph< NodeT, ArcT >::insert_arc(), Aleph::Net_Graph< NodeT, ArcT >::insert_node(), Aleph::min_cut(), and verify_max_flow_min_cut().

◆ TEST() [52/57]

TEST	(	MinCutTest	,
		SingleBottleneck
	)

Definition at line 532 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), compute_min_cut_capacity(), Aleph::dinic_maximum_flow(), Aleph::Net_Graph< NodeT, ArcT >::insert_arc(), Aleph::Net_Graph< NodeT, ArcT >::insert_node(), Aleph::min_cut(), and verify_max_flow_min_cut().

◆ TEST() [53/57]

TEST	(	MinCutTest	,
		VerifyCutPartition
	)

Definition at line 607 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::dinic_maximum_flow(), Aleph::DynListQueue< T >::front(), Aleph::DynListQueue< T >::get(), GraphCommon< GT, Node, Arc >::get_connected_node(), Aleph::Net_Graph< NodeT, ArcT >::get_sink(), Aleph::Net_Graph< NodeT, ArcT >::get_source(), GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::Array_Iterator< T >::has_curr(), Aleph::Digraph_Iterator< GT, Filter >::has_curr(), Aleph::DynListQueue< T >::insert(), Aleph::DynListQueue< T >::is_empty(), and Aleph::DynListQueue< T >::put().

◆ TEST() [54/57]

TEST	(	PerformanceTest	,
		Benchmark
	)

Definition at line 824 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), build_grid_network(), Aleph::capacity_scaling_maximum_flow(), Aleph::dinic_maximum_flow(), and Aleph::edmonds_karp_maximum_flow().

◆ TEST() [55/57]

TEST	(	RandomStressTest	,
		MediumRandomGraphs
	)

Definition at line 1548 of file tpl_maxflow_test.cc.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), Aleph::dinic_maximum_flow(), Aleph::edmonds_karp_maximum_flow(), Aleph::hlpp_maximum_flow(), and seed.

◆ TEST() [56/57]

TEST	(	RandomStressTest	,
		SmallRandomGraphs
	)

Definition at line 1518 of file tpl_maxflow_test.cc.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), Aleph::capacity_scaling_maximum_flow(), Aleph::dinic_maximum_flow(), Aleph::edmonds_karp_maximum_flow(), Aleph::hlpp_maximum_flow(), and seed.

◆ TEST() [57/57]

TEST	(	RegressionTest	,
		HLPPDisconnectedNodeRelabel
	)

Definition at line 865 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::Array_Iterator< T >::has_curr(), Aleph::hlpp_maximum_flow(), Aleph::Net_Graph< NodeT, ArcT >::insert_arc(), and Aleph::Net_Graph< NodeT, ArcT >::insert_node().

◆ verify_flow_conservation()

template<class Net >

void verify_flow_conservation ( const Net & net )

Definition at line 1058 of file tpl_maxflow_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::Array_Iterator< T >::has_curr(), Aleph::Net_Graph< NodeT, ArcT >::is_sink(), Aleph::Net_Graph< NodeT, ArcT >::is_source(), and Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne().

◆ verify_max_flow_min_cut()

template<class Net >

bool verify_max_flow_min_cut	(	Net &	net,
		double	max_flow
	)

Definition at line 475 of file tpl_maxflow_test.cc.

References compute_min_cut_capacity(), and Aleph::min_cut().

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

Functions

Function Documentation

◆ build_antiparallel_network()

◆ compute_min_cut_capacity()

◆ main()

◆ TEST() [1/57]

◆ TEST() [2/57]

◆ TEST() [3/57]

◆ TEST() [4/57]

◆ TEST() [5/57]

◆ TEST() [6/57]

◆ TEST() [7/57]

◆ TEST() [8/57]

◆ TEST() [9/57]

◆ TEST() [10/57]

◆ TEST() [11/57]

◆ TEST() [12/57]

◆ TEST() [13/57]

◆ TEST() [14/57]

◆ TEST() [15/57]

◆ TEST() [16/57]

◆ TEST() [17/57]

◆ TEST() [18/57]

◆ TEST() [19/57]

◆ TEST() [20/57]

◆ TEST() [21/57]

◆ TEST() [22/57]

◆ TEST() [23/57]

◆ TEST() [24/57]

◆ TEST() [25/57]

◆ TEST() [26/57]

◆ TEST() [27/57]

◆ TEST() [28/57]

◆ TEST() [29/57]

◆ TEST() [30/57]

◆ TEST() [31/57]

◆ TEST() [32/57]

◆ TEST() [33/57]

◆ TEST() [34/57]

◆ TEST() [35/57]

◆ TEST() [36/57]

◆ TEST() [37/57]

◆ TEST() [38/57]

◆ TEST() [39/57]

◆ TEST() [40/57]

◆ TEST() [41/57]

◆ TEST() [42/57]

◆ TEST() [43/57]

◆ TEST() [44/57]

◆ TEST() [45/57]

◆ TEST() [46/57]

◆ TEST() [47/57]

◆ TEST() [48/57]

◆ TEST() [49/57]

◆ TEST() [50/57]

◆ TEST() [51/57]

◆ TEST() [52/57]

◆ TEST() [53/57]

◆ TEST() [54/57]

◆ TEST() [55/57]

◆ TEST() [56/57]

◆ TEST() [57/57]

◆ verify_flow_conservation()

◆ verify_max_flow_min_cut()