stoer_wagner.cc File Reference

#include <gtest/gtest.h>
#include <Stoer_Wagner.H>
#include <tpl_graph.H>
#include <tpl_sgraph.H>

Include dependency graph for stoer_wagner.cc:

Go to the source code of this file.

Classes
struct	WeightFilter< GT >

Typedefs
using	IntGraph = List_Graph< Graph_Node< int >, Graph_Arc< int > >
using	WeightedGraph = List_Graph< Graph_Node< string >, Graph_Arc< int > >
using	DoubleGraph = List_Graph< Graph_Node< int >, Graph_Arc< double > >
using	SGraph = List_SGraph< Graph_Snode< int >, Graph_Sarc< int > >

Functions
	TEST (StoerWagnerConstruction, DefaultConstruction)
	TEST (StoerWagnerConstruction, WithCustomDistance)
	TEST (StoerWagnerErrors, ThrowsOnSingleNode)
	TEST (StoerWagnerErrors, HandlesDisconnectedGraph)
	TEST (StoerWagnerErrors, HandlesTwoNodesNoEdges)
	TEST (StoerWagnerMinCut, TwoNodesOneEdge)
	TEST (StoerWagnerMinCut, Triangle)
	TEST (StoerWagnerMinCut, Square)
	TEST (StoerWagnerMinCut, Barbell)
	TEST (StoerWagnerMinCut, Path)
	TEST (StoerWagnerMinCut, Cycle)
	TEST (StoerWagnerMinCut, Star)
	TEST (StoerWagnerMinCut, CompleteK3)
	TEST (StoerWagnerMinCut, CompleteK4)
	TEST (StoerWagnerMinCut, CompleteK5)
	TEST (StoerWagnerMinCut, CompleteK6)
	TEST (StoerWagnerWeighted, WeakMiddleEdge)
	TEST (StoerWagnerWeighted, WeakFirstEdge)
	TEST (StoerWagnerWeighted, WeakLastEdge)
	TEST (StoerWagnerWeighted, TwoClustersWeakBridge)
	TEST (StoerWagnerWeighted, TwoClustersHeavyBridge)
	TEST (StoerWagnerWeighted, WeightedTriangle)
	TEST (StoerWagnerPartitions, PartitionsCoverAllNodes)
	TEST (StoerWagnerPartitions, PartitionsNonEmpty)
	TEST (StoerWagnerPartitions, NoOverlap)
	TEST (StoerWagnerPartitions, CutEdgesCrossPartition)
	TEST (StoerWagnerWeightOnly, BasicUsage)
	TEST (StoerWagnerWeightOnly, WeightedGraph)
	TEST (StoerWagnerWeightOnly, MatchesFullComputation)
	TEST (StoerWagnerWeightOnly, SmallGraph)
	TEST (StoerWagnerUnitWeight, IgnoresArcWeights)
	TEST (StoerWagnerUnitWeight, CountsEdges)
	TEST (StoerWagnerCustomDistance, DoubleWeight)
	TEST (StoerWagnerCustomDistance, ConstantWeight)
	TEST (StoerWagnerArcFilter, FiltersByWeight)
	TEST (StoerWagnerGraphTypes, ListSGraph)
	TEST (StoerWagnerGraphTypes, DoubleWeights)
	TEST (StoerWagnerEdgeCases, ZeroWeightEdge)
	TEST (StoerWagnerEdgeCases, AllSameWeight)
	TEST (StoerWagnerEdgeCases, LargeWeights)
	TEST (StoerWagnerPerformance, MediumGraph50Nodes)
	TEST (StoerWagnerPerformance, DenseGraph20Nodes)
	TEST (StoerWagnerDeterminism, SameResultOnMultipleCalls)

Typedef Documentation

DoubleGraph

using DoubleGraph = List_Graph<Graph_Node<int>, Graph_Arc<double> >

Definition at line 46 of file stoer_wagner.cc.

IntGraph

using IntGraph = List_Graph<Graph_Node<int>, Graph_Arc<int> >

Definition at line 44 of file stoer_wagner.cc.

SGraph

using SGraph = List_SGraph<Graph_Snode<int>, Graph_Sarc<int> >

Definition at line 47 of file stoer_wagner.cc.

WeightedGraph

using WeightedGraph = List_Graph<Graph_Node<string>, Graph_Arc<int> >

Definition at line 45 of file stoer_wagner.cc.

Function Documentation

TEST() [1/43]

TEST	(	StoerWagnerArcFilter	,
		FiltersByWeight
	)

Definition at line 798 of file stoer_wagner.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::filter(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and Aleph::min_cut().

TEST() [2/43]

TEST	(	StoerWagnerConstruction	,
		DefaultConstruction
	)

Definition at line 233 of file stoer_wagner.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST() [3/43]

TEST	(	StoerWagnerConstruction	,
		WithCustomDistance
	)

Definition at line 238 of file stoer_wagner.cc.

References Aleph::blossom_maximum_cardinality_matching(), and GTArcCommon< ArcInfo >::get_info().

TEST() [4/43]

TEST	(	StoerWagnerCustomDistance	,
		ConstantWeight
	)

Definition at line 761 of file stoer_wagner.cc.

References Aleph::blossom_maximum_cardinality_matching(), create_triangle(), and Aleph::min_cut().

TEST() [5/43]

TEST	(	StoerWagnerCustomDistance	,
		DoubleWeight
	)

Definition at line 741 of file stoer_wagner.cc.

References Aleph::blossom_maximum_cardinality_matching(), GTArcCommon< ArcInfo >::get_info(), and Aleph::min_cut().

TEST() [6/43]

TEST	(	StoerWagnerDeterminism	,
		SameResultOnMultipleCalls
	)

Definition at line 986 of file stoer_wagner.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST() [7/43]

TEST	(	StoerWagnerEdgeCases	,
		AllSameWeight
	)

Definition at line 904 of file stoer_wagner.cc.

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

TEST() [8/43]

TEST	(	StoerWagnerEdgeCases	,
		LargeWeights
	)

Definition at line 918 of file stoer_wagner.cc.

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

TEST() [9/43]

TEST	(	StoerWagnerEdgeCases	,
		ZeroWeightEdge
	)

Definition at line 884 of file stoer_wagner.cc.

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

TEST() [10/43]

TEST	(	StoerWagnerErrors	,
		HandlesDisconnectedGraph
	)

Definition at line 265 of file stoer_wagner.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::HTList::is_empty(), and Aleph::min_cut().

TEST() [11/43]

TEST	(	StoerWagnerErrors	,
		HandlesTwoNodesNoEdges
	)

Definition at line 287 of file stoer_wagner.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and Aleph::min_cut().

TEST() [12/43]

TEST	(	StoerWagnerErrors	,
		ThrowsOnSingleNode
	)

Definition at line 253 of file stoer_wagner.cc.

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

TEST() [13/43]

TEST	(	StoerWagnerGraphTypes	,
		DoubleWeights
	)

Definition at line 851 of file stoer_wagner.cc.

References Aleph::blossom_maximum_cardinality_matching(), GTArcCommon< ArcInfo >::get_info(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::min_cut(), and DoubleDistance::operator()().

TEST() [14/43]

TEST	(	StoerWagnerGraphTypes	,
		ListSGraph
	)

Definition at line 831 of file stoer_wagner.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::insert_arc(), Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::insert_node(), and Aleph::min_cut().

TEST() [15/43]

TEST	(	StoerWagnerMinCut	,
		Barbell
	)

Definition at line 353 of file stoer_wagner.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::min_cut(), and Aleph::HTList::size().

TEST() [16/43]

TEST	(	StoerWagnerMinCut	,
		CompleteK3
	)

Definition at line 416 of file stoer_wagner.cc.

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

TEST() [17/43]

TEST	(	StoerWagnerMinCut	,
		CompleteK4
	)

Definition at line 430 of file stoer_wagner.cc.

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

TEST() [18/43]

TEST	(	StoerWagnerMinCut	,
		CompleteK5
	)

Definition at line 444 of file stoer_wagner.cc.

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

TEST() [19/43]

TEST	(	StoerWagnerMinCut	,
		CompleteK6
	)

Definition at line 458 of file stoer_wagner.cc.

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

TEST() [20/43]

TEST	(	StoerWagnerMinCut	,
		Cycle
	)

Definition at line 383 of file stoer_wagner.cc.

References Aleph::blossom_maximum_cardinality_matching(), create_cycle(), Aleph::min_cut(), and Aleph::HTList::size().

TEST() [21/43]

TEST	(	StoerWagnerMinCut	,
		Path
	)

Definition at line 368 of file stoer_wagner.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::min_cut(), and Aleph::HTList::size().

TEST() [22/43]

TEST	(	StoerWagnerMinCut	,
		Square
	)

Definition at line 339 of file stoer_wagner.cc.

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

TEST() [23/43]

TEST	(	StoerWagnerMinCut	,
		Star
	)

Definition at line 398 of file stoer_wagner.cc.

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

TEST() [24/43]

TEST	(	StoerWagnerMinCut	,
		Triangle
	)

Definition at line 324 of file stoer_wagner.cc.

References Aleph::blossom_maximum_cardinality_matching(), create_triangle(), Aleph::min_cut(), and Aleph::HTList::size().

TEST() [25/43]

TEST	(	StoerWagnerMinCut	,
		TwoNodesOneEdge
	)

Definition at line 305 of file stoer_wagner.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::min_cut(), and Aleph::HTList::size().

TEST() [26/43]

TEST	(	StoerWagnerPartitions	,
		CutEdgesCrossPartition
	)

Definition at line 619 of file stoer_wagner.cc.

References Aleph::blossom_maximum_cardinality_matching(), LocateFunctions< Container, Type >::get_it(), and Aleph::DynSetTree< Key, Tree, Compare >::insert().

TEST() [27/43]

TEST	(	StoerWagnerPartitions	,
		NoOverlap
	)

Definition at line 601 of file stoer_wagner.cc.

References Aleph::blossom_maximum_cardinality_matching(), create_cycle(), LocateFunctions< Container, Type >::get_it(), and Aleph::DynSetTree< Key, Tree, Compare >::insert().

TEST() [28/43]

TEST	(	StoerWagnerPartitions	,
		PartitionsCoverAllNodes
	)

Definition at line 574 of file stoer_wagner.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::HTList::size().

TEST() [29/43]

TEST	(	StoerWagnerPartitions	,
		PartitionsNonEmpty
	)

Definition at line 587 of file stoer_wagner.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::HTList::is_empty().

TEST() [30/43]

TEST	(	StoerWagnerPerformance	,
		DenseGraph20Nodes
	)

Definition at line 968 of file stoer_wagner.cc.

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

TEST() [31/43]

TEST	(	StoerWagnerPerformance	,
		MediumGraph50Nodes
	)

Definition at line 941 of file stoer_wagner.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), N, nodes, and Aleph::HTList::size().

TEST() [32/43]

TEST	(	StoerWagnerUnitWeight	,
		CountsEdges
	)

Definition at line 723 of file stoer_wagner.cc.

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

TEST() [33/43]

TEST	(	StoerWagnerUnitWeight	,
		IgnoresArcWeights
	)

Definition at line 702 of file stoer_wagner.cc.

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

TEST() [34/43]

TEST	(	StoerWagnerWeighted	,
		TwoClustersHeavyBridge
	)

Definition at line 531 of file stoer_wagner.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::min_cut(), and Aleph::HTList::size().

TEST() [35/43]

TEST	(	StoerWagnerWeighted	,
		TwoClustersWeakBridge
	)

Definition at line 516 of file stoer_wagner.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::min_cut(), and Aleph::HTList::size().

TEST() [36/43]

TEST	(	StoerWagnerWeighted	,
		WeakFirstEdge
	)

Definition at line 490 of file stoer_wagner.cc.

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

TEST() [37/43]

TEST	(	StoerWagnerWeighted	,
		WeakLastEdge
	)

Definition at line 503 of file stoer_wagner.cc.

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

TEST() [38/43]

TEST	(	StoerWagnerWeighted	,
		WeakMiddleEdge
	)

Definition at line 476 of file stoer_wagner.cc.

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

TEST() [39/43]

TEST	(	StoerWagnerWeighted	,
		WeightedTriangle
	)

Definition at line 546 of file stoer_wagner.cc.

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

TEST() [40/43]

TEST	(	StoerWagnerWeightOnly	,
		BasicUsage
	)

Definition at line 651 of file stoer_wagner.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >::min_cut_weight().

TEST() [41/43]

TEST	(	StoerWagnerWeightOnly	,
		MatchesFullComputation
	)

Definition at line 671 of file stoer_wagner.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >::min_cut_weight().

TEST() [42/43]

TEST	(	StoerWagnerWeightOnly	,
		SmallGraph
	)

Definition at line 685 of file stoer_wagner.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >::min_cut_weight().

TEST() [43/43]

TEST	(	StoerWagnerWeightOnly	,
		WeightedGraph
	)

Definition at line 661 of file stoer_wagner.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >::min_cut_weight().