bipartite_test.cc File Reference

Tests for Bipartite. More...

#include <gtest/gtest.h>
#include <tpl_bipartite.H>
#include <tpl_graph.H>

Include dependency graph for bipartite_test.cc:

Go to the source code of this file.

Typedefs
using	Graph = List_Graph< Graph_Node< int >, Graph_Arc< Empty_Class > >

Functions
Graph	create_complete_bipartite (size_t m, size_t n)
	Creates a complete bipartite graph K_{m,n} Left partition: nodes 0..m-1 Right partition: nodes m..m+n-1.
Graph	create_path_graph (size_t n)
	Creates a path graph with n nodes: 0–1–2–...–n-1 Path graphs are always bipartite.
Graph	create_cycle_graph (size_t n)
	Creates a cycle graph with n nodes: 0–1–2–...–n-1–0 Even cycles are bipartite, odd cycles are not.
Graph	create_star_graph (size_t n)
	Creates a star graph with center and n leaves Star graphs are always bipartite.
Graph	create_triangle ()
	Creates a triangle (K_3) - the simplest non-bipartite graph.
Graph	create_disconnected_bipartite ()
	Creates two disconnected components.
bool	verify_bipartition (const Graph &g, const DynDlist< Graph::Node * > &l, const DynDlist< Graph::Node * > &r)
	Verifies that a bipartition is valid:
bool	verify_matching (const Graph &g, const DynDlist< Graph::Arc * > &matching)
	Verifies that a matching is valid:
	TEST (Bipartite, EmptyGraphReturnsEmpty)
	TEST (Bipartite, SingleNode)
	TEST (Bipartite, TwoConnectedNodes)
	TEST (Bipartite, PathGraphEven)
	TEST (Bipartite, PathGraphOdd)
	TEST (Bipartite, StarGraph)
	TEST (Bipartite, CompleteBipartiteK22)
	TEST (Bipartite, CompleteBipartiteK33)
	TEST (Bipartite, CompleteBipartiteK25)
	TEST (Bipartite, EvenCycle)
	TEST (Bipartite, TriangleThrows)
	TEST (Bipartite, OddCycleThrows)
	TEST (Bipartite, LargeOddCycleThrows)
	TEST (Bipartite, CompleteGraphK3Throws)
	TEST (Bipartite, GraphWithOddCycleAttached)
	TEST (Bipartite, TwoDisconnectedNodes)
	TEST (Bipartite, DisconnectedBipartiteComponents)
	TEST (ComputeBipartiteClass, BasicUsage)
	TEST (ComputeBipartiteClass, ThrowsOnNonBipartite)
	TEST (MaximumMatching, EmptyGraphReturnsEmpty)
	TEST (MaximumMatching, SingleEdge)
	TEST (MaximumMatching, PathGraph4)
	TEST (MaximumMatching, PathGraph5)
	TEST (MaximumMatching, CompleteBipartiteK22)
	TEST (MaximumMatching, CompleteBipartiteK33)
	TEST (MaximumMatching, CompleteBipartiteK55)
	TEST (MaximumMatching, UnbalancedK25)
	TEST (MaximumMatching, UnbalancedK52)
	TEST (MaximumMatching, StarGraph)
	TEST (MaximumMatching, EvenCycle)
	TEST (MaximumMatching, ThrowsOnNonBipartite)
	TEST (MaximumMatchingClass, BasicUsage)
	TEST (MaximumMatchingClass, ThrowsOnNonBipartite)
	TEST (BipartiteStress, LargeBipartiteGraph)
	TEST (BipartiteStress, LargePathGraph)
	TEST (MaximumMatchingStress, LargeMatching)
	TEST (BipartiteStress, LargeEvenCycle)
	TEST (Bipartite, MultipleEdgesBetweenSameNodes)
	TEST (Bipartite, IsolatedNodeWithBipartiteComponent)
	TEST (BipartiteColor, EnumValues)
	TEST (HopcroftKarp, EmptyGraph)
	TEST (HopcroftKarp, SingleIsolatedNode)
	TEST (HopcroftKarp, SingleEdge)
	TEST (HopcroftKarp, PathGraph4)
	TEST (HopcroftKarp, PathGraph5)
	TEST (HopcroftKarp, CompleteBipartiteK22)
	TEST (HopcroftKarp, CompleteBipartiteK33)
	TEST (HopcroftKarp, CompleteBipartiteK55)
	TEST (HopcroftKarp, UnbalancedK25)
	TEST (HopcroftKarp, StarGraph)
	TEST (HopcroftKarp, EvenCycle6)
	TEST (HopcroftKarp, TriangleThrows)
	TEST (HopcroftKarp, OddCycleThrows)
	TEST (HopcroftKarp, TwoDisconnectedEdges)
	TEST (HopcroftKarp, DisconnectedWithIsolatedNodes)
	TEST (HopcroftKarp, TwoDisconnectedCompleteBipartite)
	TEST (HopcroftKarp, CrossValidateK44)
	TEST (HopcroftKarp, CrossValidatePath6)
	TEST (HopcroftKarp, CrossValidateEvenCycle8)
	TEST (HopcroftKarp, FunctorWrapper)
	TEST (HopcroftKarp, FunctorMatchesFreeFunction)
	TEST (HopcroftKarp, StressK50_50)
	TEST (HopcroftKarp, StressK100_100)
	TEST (HopcroftKarp, StressPath200)
int	main (int argc, char **argv)

Detailed Description

Tests for Bipartite.

Comprehensive tests for tpl_bipartite.H.

Tests cover:

• Bipartite graph detection and partition computation
• Maximum cardinality matching
• Edge cases (empty graphs, single nodes, disconnected components)
• Non-bipartite graph detection

Definition in file bipartite_test.cc.

Typedef Documentation

Graph

using Graph = List_Graph<Graph_Node<int>, Graph_Arc<Empty_Class> >

Definition at line 57 of file bipartite_test.cc.

Function Documentation

create_complete_bipartite()

Graph create_complete_bipartite	(	size_t	m,
		size_t	n
	)

Creates a complete bipartite graph K_{m,n} Left partition: nodes 0..m-1 Right partition: nodes m..m+n-1.

Definition at line 68 of file bipartite_test.cc.

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

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

create_cycle_graph()

Graph create_cycle_graph

(

size_t

n

)

Creates a cycle graph with n nodes: 0–1–2–...–n-1–0 Even cycles are bipartite, odd cycles are not.

Definition at line 115 of file bipartite_test.cc.

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

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

create_disconnected_bipartite()

Graph create_disconnected_bipartite

(

)

Creates two disconnected components.

Definition at line 172 of file bipartite_test.cc.

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

Referenced by TEST(), and TEST().

create_path_graph()

Graph create_path_graph

(

size_t

n

)

Creates a path graph with n nodes: 0–1–2–...–n-1 Path graphs are always bipartite.

Definition at line 94 of file bipartite_test.cc.

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

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

create_star_graph()

Graph create_star_graph

(

size_t

n

)

Creates a star graph with center and n leaves Star graphs are always bipartite.

Definition at line 136 of file bipartite_test.cc.

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

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

create_triangle()

Graph create_triangle

(

)

Creates a triangle (K_3) - the simplest non-bipartite graph.

Definition at line 154 of file bipartite_test.cc.

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

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

main()

int main	(	int	argc,
		char **	argv
	)

Definition at line 1149 of file bipartite_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST() [1/64]

TEST	(	Bipartite	,
		CompleteBipartiteK22
	)

Definition at line 349 of file bipartite_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), create_complete_bipartite(), l, r, Aleph::HTList::size(), and verify_bipartition().

TEST() [2/64]

TEST	(	Bipartite	,
		CompleteBipartiteK25
	)

Definition at line 375 of file bipartite_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), create_complete_bipartite(), l, r, Aleph::HTList::size(), and verify_bipartition().

TEST() [3/64]

TEST	(	Bipartite	,
		CompleteBipartiteK33
	)

Definition at line 362 of file bipartite_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), create_complete_bipartite(), l, r, Aleph::HTList::size(), and verify_bipartition().

TEST() [4/64]

TEST	(	Bipartite	,
		CompleteGraphK3Throws
	)

Definition at line 431 of file bipartite_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), create_triangle(), l, and r.

TEST() [5/64]

TEST	(	Bipartite	,
		DisconnectedBipartiteComponents
	)

Definition at line 486 of file bipartite_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), create_disconnected_bipartite(), l, r, Aleph::HTList::size(), and verify_bipartition().

TEST() [6/64]

TEST	(	Bipartite	,
		EmptyGraphReturnsEmpty
	)

Definition at line 269 of file bipartite_test.cc.

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

TEST() [7/64]

TEST	(	Bipartite	,
		EvenCycle
	)

Definition at line 387 of file bipartite_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), create_cycle_graph(), l, r, Aleph::HTList::size(), and verify_bipartition().

TEST() [8/64]

TEST	(	Bipartite	,
		GraphWithOddCycleAttached
	)

Definition at line 441 of file bipartite_test.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(), l, and r.

TEST() [9/64]

TEST	(	Bipartite	,
		IsolatedNodeWithBipartiteComponent
	)

Definition at line 788 of file bipartite_test.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(), l, r, and Aleph::HTList::size().

TEST() [10/64]

TEST	(	Bipartite	,
		LargeOddCycleThrows
	)

Definition at line 422 of file bipartite_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), create_cycle_graph(), l, and r.

TEST() [11/64]

TEST	(	Bipartite	,
		MultipleEdgesBetweenSameNodes
	)

Definition at line 769 of file bipartite_test.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(), l, r, and Aleph::HTList::size().

TEST() [12/64]

TEST	(	Bipartite	,
		OddCycleThrows
	)

Definition at line 413 of file bipartite_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), create_cycle_graph(), l, and r.

TEST() [13/64]

TEST	(	Bipartite	,
		PathGraphEven
	)

Definition at line 308 of file bipartite_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), create_path_graph(), l, r, Aleph::HTList::size(), and verify_bipartition().

TEST() [14/64]

TEST	(	Bipartite	,
		PathGraphOdd
	)

Definition at line 322 of file bipartite_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), create_path_graph(), l, r, Aleph::HTList::size(), and verify_bipartition().

TEST() [15/64]

TEST	(	Bipartite	,
		SingleNode
	)

Definition at line 279 of file bipartite_test.cc.

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

TEST() [16/64]

TEST	(	Bipartite	,
		StarGraph
	)

Definition at line 334 of file bipartite_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), create_star_graph(), l, r, Aleph::HTList::size(), and verify_bipartition().

TEST() [17/64]

TEST	(	Bipartite	,
		TriangleThrows
	)

Definition at line 404 of file bipartite_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), create_triangle(), l, and r.

TEST() [18/64]

TEST	(	Bipartite	,
		TwoConnectedNodes
	)

Definition at line 292 of file bipartite_test.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(), l, r, Aleph::HTList::size(), and verify_bipartition().

TEST() [19/64]

TEST	(	Bipartite	,
		TwoDisconnectedNodes
	)

Definition at line 469 of file bipartite_test.cc.

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

TEST() [20/64]

TEST	(	BipartiteColor	,
		EnumValues
	)

Definition at line 812 of file bipartite_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Bp_Blue, Aleph::Bp_Red, and Aleph::Bp_White.

TEST() [21/64]

TEST	(	BipartiteStress	,
		LargeBipartiteGraph
	)

Definition at line 715 of file bipartite_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), create_complete_bipartite(), l, r, Aleph::HTList::size(), and verify_bipartition().

TEST() [22/64]

TEST	(	BipartiteStress	,
		LargeEvenCycle
	)

Definition at line 752 of file bipartite_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), create_cycle_graph(), l, r, Aleph::HTList::size(), and verify_bipartition().

TEST() [23/64]

TEST	(	BipartiteStress	,
		LargePathGraph
	)

Definition at line 727 of file bipartite_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), create_path_graph(), l, r, Aleph::HTList::size(), and verify_bipartition().

TEST() [24/64]

TEST	(	ComputeBipartiteClass	,
		BasicUsage
	)

Definition at line 505 of file bipartite_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), create_complete_bipartite(), l, r, Aleph::HTList::size(), and verify_bipartition().

TEST() [25/64]

TEST	(	ComputeBipartiteClass	,
		ThrowsOnNonBipartite
	)

Definition at line 517 of file bipartite_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), create_triangle(), l, and r.

TEST() [26/64]

TEST	(	HopcroftKarp	,
		CompleteBipartiteK22
	)

Definition at line 884 of file bipartite_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), create_complete_bipartite(), and verify_matching().

TEST() [27/64]

TEST	(	HopcroftKarp	,
		CompleteBipartiteK33
	)

Definition at line 895 of file bipartite_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), create_complete_bipartite(), and verify_matching().

TEST() [28/64]

TEST	(	HopcroftKarp	,
		CompleteBipartiteK55
	)

Definition at line 906 of file bipartite_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), create_complete_bipartite(), and verify_matching().

TEST() [29/64]

TEST	(	HopcroftKarp	,
		CrossValidateEvenCycle8
	)

Definition at line 1076 of file bipartite_test.cc.

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

TEST() [30/64]

TEST	(	HopcroftKarp	,
		CrossValidateK44
	)

Definition at line 1048 of file bipartite_test.cc.

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

TEST() [31/64]

TEST	(	HopcroftKarp	,
		CrossValidatePath6
	)

Definition at line 1062 of file bipartite_test.cc.

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

TEST() [32/64]

TEST	(	HopcroftKarp	,
		DisconnectedWithIsolatedNodes
	)

Definition at line 983 of file bipartite_test.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 verify_matching().

TEST() [33/64]

TEST	(	HopcroftKarp	,
		EmptyGraph
	)

Definition at line 826 of file bipartite_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST() [34/64]

TEST	(	HopcroftKarp	,
		EvenCycle6
	)

Definition at line 939 of file bipartite_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), create_cycle_graph(), and verify_matching().

TEST() [35/64]

TEST	(	HopcroftKarp	,
		FunctorMatchesFreeFunction
	)

Definition at line 1103 of file bipartite_test.cc.

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

TEST() [36/64]

TEST	(	HopcroftKarp	,
		FunctorWrapper
	)

Definition at line 1092 of file bipartite_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), create_complete_bipartite(), and verify_matching().

TEST() [37/64]

TEST	(	HopcroftKarp	,
		OddCycleThrows
	)

Definition at line 961 of file bipartite_test.cc.

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

TEST() [38/64]

TEST	(	HopcroftKarp	,
		PathGraph4
	)

Definition at line 862 of file bipartite_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), create_path_graph(), and verify_matching().

TEST() [39/64]

TEST	(	HopcroftKarp	,
		PathGraph5
	)

Definition at line 873 of file bipartite_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), create_path_graph(), and verify_matching().

TEST() [40/64]

TEST	(	HopcroftKarp	,
		SingleEdge
	)

Definition at line 846 of file bipartite_test.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 verify_matching().

TEST() [41/64]

TEST	(	HopcroftKarp	,
		SingleIsolatedNode
	)

Definition at line 835 of file bipartite_test.cc.

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

TEST() [42/64]

TEST	(	HopcroftKarp	,
		StarGraph
	)

Definition at line 928 of file bipartite_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), create_star_graph(), and verify_matching().

TEST() [43/64]

TEST	(	HopcroftKarp	,
		StressK100_100
	)

Definition at line 1127 of file bipartite_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), create_complete_bipartite(), and verify_matching().

TEST() [44/64]

TEST	(	HopcroftKarp	,
		StressK50_50
	)

Definition at line 1116 of file bipartite_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), create_complete_bipartite(), and verify_matching().

TEST() [45/64]

TEST	(	HopcroftKarp	,
		StressPath200
	)

Definition at line 1138 of file bipartite_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), create_path_graph(), and verify_matching().

TEST() [46/64]

TEST	(	HopcroftKarp	,
		TriangleThrows
	)

Definition at line 952 of file bipartite_test.cc.

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

TEST() [47/64]

TEST	(	HopcroftKarp	,
		TwoDisconnectedCompleteBipartite
	)

Definition at line 1014 of file bipartite_test.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(), l1, l2, and verify_matching().

TEST() [48/64]

TEST	(	HopcroftKarp	,
		TwoDisconnectedEdges
	)

Definition at line 972 of file bipartite_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), create_disconnected_bipartite(), and verify_matching().

TEST() [49/64]

TEST	(	HopcroftKarp	,
		UnbalancedK25
	)

Definition at line 917 of file bipartite_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), create_complete_bipartite(), and verify_matching().

TEST() [50/64]

TEST	(	MaximumMatching	,
		CompleteBipartiteK22
	)

Definition at line 582 of file bipartite_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), create_complete_bipartite(), and verify_matching().

TEST() [51/64]

TEST	(	MaximumMatching	,
		CompleteBipartiteK33
	)

Definition at line 595 of file bipartite_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), create_complete_bipartite(), and verify_matching().

TEST() [52/64]

TEST	(	MaximumMatching	,
		CompleteBipartiteK55
	)

Definition at line 608 of file bipartite_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), create_complete_bipartite(), and verify_matching().

TEST() [53/64]

TEST	(	MaximumMatching	,
		EmptyGraphReturnsEmpty
	)

Definition at line 529 of file bipartite_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST() [54/64]

TEST	(	MaximumMatching	,
		EvenCycle
	)

Definition at line 660 of file bipartite_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), create_cycle_graph(), and verify_matching().

TEST() [55/64]

TEST	(	MaximumMatching	,
		PathGraph4
	)

Definition at line 556 of file bipartite_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), create_path_graph(), and verify_matching().

TEST() [56/64]

TEST	(	MaximumMatching	,
		PathGraph5
	)

Definition at line 569 of file bipartite_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), create_path_graph(), and verify_matching().

TEST() [57/64]

TEST	(	MaximumMatching	,
		SingleEdge
	)

Definition at line 541 of file bipartite_test.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 verify_matching().

TEST() [58/64]

TEST	(	MaximumMatching	,
		StarGraph
	)

Definition at line 647 of file bipartite_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), create_star_graph(), and verify_matching().

TEST() [59/64]

TEST	(	MaximumMatching	,
		ThrowsOnNonBipartite
	)

Definition at line 673 of file bipartite_test.cc.

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

TEST() [60/64]

TEST	(	MaximumMatching	,
		UnbalancedK25
	)

Definition at line 621 of file bipartite_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), create_complete_bipartite(), and verify_matching().

TEST() [61/64]

TEST	(	MaximumMatching	,
		UnbalancedK52
	)

Definition at line 634 of file bipartite_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), create_complete_bipartite(), and verify_matching().

TEST() [62/64]

TEST	(	MaximumMatchingClass	,
		BasicUsage
	)

Definition at line 688 of file bipartite_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), create_complete_bipartite(), and verify_matching().

TEST() [63/64]

TEST	(	MaximumMatchingClass	,
		ThrowsOnNonBipartite
	)

Definition at line 700 of file bipartite_test.cc.

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

TEST() [64/64]

TEST	(	MaximumMatchingStress	,
		LargeMatching
	)

Definition at line 740 of file bipartite_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), create_complete_bipartite(), and verify_matching().

verify_bipartition()

bool verify_bipartition	(	const Graph &	g,
		const DynDlist< Graph::Node * > &	l,
		const DynDlist< Graph::Node * > &	r
	)

Verifies that a bipartition is valid:

• All partitioned nodes are in exactly one partition
• No edge between partitioned nodes connects two nodes in the same partition

Note: This function only verifies edges between nodes that were partitioned. Edges involving non-partitioned nodes (from disconnected components) are ignored.

Definition at line 197 of file bipartite_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), LocateFunctions< Container, Type >::get_it(), GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::DynSetTree< Key, Tree, Compare >::insert(), l, Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), and r.

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

verify_matching()

bool verify_matching	(	const Graph &	g,
		const DynDlist< Graph::Arc * > &	matching
	)

Verifies that a matching is valid:

• No two edges share a vertex

Definition at line 243 of file bipartite_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), GraphCommon< GT, Node, Arc >::get_src_node(), and GraphCommon< GT, Node, Arc >::get_tgt_node().

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