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, DISABLED_EmptyGraph)
	TEST (Bipartite, EmptyGraphThrowsRangeError)
	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, EmptyGraphThrowsRangeError)
	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(), 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(), 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(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and Aleph::maps().

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 1165 of file bipartite_test.cc.

References Aleph::maps().

TEST() [1/65]

TEST	(	Bipartite	,
		CompleteBipartiteK22
	)

Definition at line 363 of file bipartite_test.cc.

References create_complete_bipartite(), l, Aleph::maps(), Aleph::HTList::size(), Aleph::DynDlist< T >::size(), and verify_bipartition().

TEST() [2/65]

TEST	(	Bipartite	,
		CompleteBipartiteK25
	)

Definition at line 389 of file bipartite_test.cc.

References create_complete_bipartite(), l, Aleph::maps(), Aleph::HTList::size(), Aleph::DynDlist< T >::size(), and verify_bipartition().

TEST() [3/65]

TEST	(	Bipartite	,
		CompleteBipartiteK33
	)

Definition at line 376 of file bipartite_test.cc.

References create_complete_bipartite(), l, Aleph::maps(), Aleph::HTList::size(), Aleph::DynDlist< T >::size(), and verify_bipartition().

TEST() [4/65]

TEST	(	Bipartite	,
		CompleteGraphK3Throws
	)

Definition at line 445 of file bipartite_test.cc.

References create_triangle(), l, and Aleph::maps().

TEST() [5/65]

TEST	(	Bipartite	,
		DISABLED_EmptyGraph
	)

Definition at line 271 of file bipartite_test.cc.

References Aleph::Dlink::is_empty(), Aleph::HTList::is_empty(), l, and Aleph::maps().

TEST() [6/65]

TEST	(	Bipartite	,
		DisconnectedBipartiteComponents
	)

Definition at line 500 of file bipartite_test.cc.

References create_disconnected_bipartite(), l, Aleph::maps(), Aleph::HTList::size(), Aleph::DynDlist< T >::size(), and verify_bipartition().

TEST() [7/65]

TEST	(	Bipartite	,
		EmptyGraphThrowsRangeError
	)

Definition at line 284 of file bipartite_test.cc.

References l, and Aleph::maps().

TEST() [8/65]

TEST	(	Bipartite	,
		EvenCycle
	)

Definition at line 401 of file bipartite_test.cc.

References create_cycle_graph(), l, Aleph::maps(), Aleph::HTList::size(), Aleph::DynDlist< T >::size(), and verify_bipartition().

TEST() [9/65]

TEST	(	Bipartite	,
		GraphWithOddCycleAttached
	)

Definition at line 455 of file bipartite_test.cc.

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

TEST() [10/65]

TEST	(	Bipartite	,
		IsolatedNodeWithBipartiteComponent
	)

Definition at line 804 of file bipartite_test.cc.

References Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), l, Aleph::maps(), Aleph::HTList::size(), and Aleph::DynDlist< T >::size().

TEST() [11/65]

TEST	(	Bipartite	,
		LargeOddCycleThrows
	)

Definition at line 436 of file bipartite_test.cc.

References create_cycle_graph(), l, and Aleph::maps().

TEST() [12/65]

TEST	(	Bipartite	,
		MultipleEdgesBetweenSameNodes
	)

Definition at line 785 of file bipartite_test.cc.

References Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), l, Aleph::maps(), Aleph::HTList::size(), and Aleph::DynDlist< T >::size().

TEST() [13/65]

TEST	(	Bipartite	,
		OddCycleThrows
	)

Definition at line 427 of file bipartite_test.cc.

References create_cycle_graph(), l, and Aleph::maps().

TEST() [14/65]

TEST	(	Bipartite	,
		PathGraphEven
	)

Definition at line 322 of file bipartite_test.cc.

References create_path_graph(), l, Aleph::maps(), Aleph::HTList::size(), Aleph::DynDlist< T >::size(), and verify_bipartition().

TEST() [15/65]

TEST	(	Bipartite	,
		PathGraphOdd
	)

Definition at line 336 of file bipartite_test.cc.

References create_path_graph(), l, Aleph::maps(), Aleph::HTList::size(), Aleph::DynDlist< T >::size(), and verify_bipartition().

TEST() [16/65]

TEST	(	Bipartite	,
		SingleNode
	)

Definition at line 293 of file bipartite_test.cc.

References Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), l, Aleph::maps(), Aleph::HTList::size(), and Aleph::DynDlist< T >::size().

TEST() [17/65]

TEST	(	Bipartite	,
		StarGraph
	)

Definition at line 348 of file bipartite_test.cc.

References create_star_graph(), l, Aleph::maps(), Aleph::HTList::size(), Aleph::DynDlist< T >::size(), and verify_bipartition().

TEST() [18/65]

TEST	(	Bipartite	,
		TriangleThrows
	)

Definition at line 418 of file bipartite_test.cc.

References create_triangle(), l, and Aleph::maps().

TEST() [19/65]

TEST	(	Bipartite	,
		TwoConnectedNodes
	)

Definition at line 306 of file bipartite_test.cc.

References Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), l, Aleph::maps(), Aleph::HTList::size(), Aleph::DynDlist< T >::size(), and verify_bipartition().

TEST() [20/65]

TEST	(	Bipartite	,
		TwoDisconnectedNodes
	)

Definition at line 483 of file bipartite_test.cc.

References Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), l, Aleph::maps(), Aleph::HTList::size(), and Aleph::DynDlist< T >::size().

TEST() [21/65]

TEST	(	BipartiteColor	,
		EnumValues
	)

Definition at line 828 of file bipartite_test.cc.

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

TEST() [22/65]

TEST	(	BipartiteStress	,
		LargeBipartiteGraph
	)

Definition at line 731 of file bipartite_test.cc.

References create_complete_bipartite(), l, Aleph::maps(), Aleph::HTList::size(), Aleph::DynDlist< T >::size(), and verify_bipartition().

TEST() [23/65]

TEST	(	BipartiteStress	,
		LargeEvenCycle
	)

Definition at line 768 of file bipartite_test.cc.

References create_cycle_graph(), l, Aleph::maps(), Aleph::HTList::size(), Aleph::DynDlist< T >::size(), and verify_bipartition().

TEST() [24/65]

TEST	(	BipartiteStress	,
		LargePathGraph
	)

Definition at line 743 of file bipartite_test.cc.

References create_path_graph(), l, Aleph::maps(), Aleph::HTList::size(), Aleph::DynDlist< T >::size(), and verify_bipartition().

TEST() [25/65]

TEST	(	ComputeBipartiteClass	,
		BasicUsage
	)

Definition at line 519 of file bipartite_test.cc.

References create_complete_bipartite(), l, Aleph::maps(), Aleph::HTList::size(), Aleph::DynDlist< T >::size(), and verify_bipartition().

TEST() [26/65]

TEST	(	ComputeBipartiteClass	,
		ThrowsOnNonBipartite
	)

Definition at line 531 of file bipartite_test.cc.

References create_triangle(), l, and Aleph::maps().

TEST() [27/65]

TEST	(	HopcroftKarp	,
		CompleteBipartiteK22
	)

Definition at line 900 of file bipartite_test.cc.

References create_complete_bipartite(), Aleph::maps(), Aleph::HTList::size(), and verify_matching().

TEST() [28/65]

TEST	(	HopcroftKarp	,
		CompleteBipartiteK33
	)

Definition at line 911 of file bipartite_test.cc.

References create_complete_bipartite(), Aleph::maps(), Aleph::HTList::size(), and verify_matching().

TEST() [29/65]

TEST	(	HopcroftKarp	,
		CompleteBipartiteK55
	)

Definition at line 922 of file bipartite_test.cc.

References create_complete_bipartite(), Aleph::maps(), Aleph::HTList::size(), and verify_matching().

TEST() [30/65]

TEST	(	HopcroftKarp	,
		CrossValidateEvenCycle8
	)

Definition at line 1092 of file bipartite_test.cc.

References create_cycle_graph(), Aleph::maps(), and Aleph::HTList::size().

TEST() [31/65]

TEST	(	HopcroftKarp	,
		CrossValidateK44
	)

Definition at line 1064 of file bipartite_test.cc.

References create_complete_bipartite(), Aleph::maps(), and Aleph::HTList::size().

TEST() [32/65]

TEST	(	HopcroftKarp	,
		CrossValidatePath6
	)

Definition at line 1078 of file bipartite_test.cc.

References create_path_graph(), Aleph::maps(), and Aleph::HTList::size().

TEST() [33/65]

TEST	(	HopcroftKarp	,
		DisconnectedWithIsolatedNodes
	)

Definition at line 999 of file bipartite_test.cc.

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

TEST() [34/65]

TEST	(	HopcroftKarp	,
		EmptyGraph
	)

Definition at line 842 of file bipartite_test.cc.

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

TEST() [35/65]

TEST	(	HopcroftKarp	,
		EvenCycle6
	)

Definition at line 955 of file bipartite_test.cc.

References create_cycle_graph(), Aleph::maps(), Aleph::HTList::size(), and verify_matching().

TEST() [36/65]

TEST	(	HopcroftKarp	,
		FunctorMatchesFreeFunction
	)

Definition at line 1119 of file bipartite_test.cc.

References create_complete_bipartite(), Aleph::maps(), and Aleph::HTList::size().

TEST() [37/65]

TEST	(	HopcroftKarp	,
		FunctorWrapper
	)

Definition at line 1108 of file bipartite_test.cc.

References create_complete_bipartite(), Aleph::maps(), Aleph::HTList::size(), and verify_matching().

TEST() [38/65]

TEST	(	HopcroftKarp	,
		OddCycleThrows
	)

Definition at line 977 of file bipartite_test.cc.

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

TEST() [39/65]

TEST	(	HopcroftKarp	,
		PathGraph4
	)

Definition at line 878 of file bipartite_test.cc.

References create_path_graph(), Aleph::maps(), Aleph::HTList::size(), and verify_matching().

TEST() [40/65]

TEST	(	HopcroftKarp	,
		PathGraph5
	)

Definition at line 889 of file bipartite_test.cc.

References create_path_graph(), Aleph::maps(), Aleph::HTList::size(), and verify_matching().

TEST() [41/65]

TEST	(	HopcroftKarp	,
		SingleEdge
	)

Definition at line 862 of file bipartite_test.cc.

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

TEST() [42/65]

TEST	(	HopcroftKarp	,
		SingleIsolatedNode
	)

Definition at line 851 of file bipartite_test.cc.

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

TEST() [43/65]

TEST	(	HopcroftKarp	,
		StarGraph
	)

Definition at line 944 of file bipartite_test.cc.

References create_star_graph(), Aleph::maps(), Aleph::HTList::size(), and verify_matching().

TEST() [44/65]

TEST	(	HopcroftKarp	,
		StressK100_100
	)

Definition at line 1143 of file bipartite_test.cc.

References create_complete_bipartite(), Aleph::maps(), Aleph::HTList::size(), and verify_matching().

TEST() [45/65]

TEST	(	HopcroftKarp	,
		StressK50_50
	)

Definition at line 1132 of file bipartite_test.cc.

References create_complete_bipartite(), Aleph::maps(), Aleph::HTList::size(), and verify_matching().

TEST() [46/65]

TEST	(	HopcroftKarp	,
		StressPath200
	)

Definition at line 1154 of file bipartite_test.cc.

References create_path_graph(), Aleph::maps(), Aleph::HTList::size(), and verify_matching().

TEST() [47/65]

TEST	(	HopcroftKarp	,
		TriangleThrows
	)

Definition at line 968 of file bipartite_test.cc.

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

TEST() [48/65]

TEST	(	HopcroftKarp	,
		TwoDisconnectedCompleteBipartite
	)

Definition at line 1030 of file bipartite_test.cc.

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

TEST() [49/65]

TEST	(	HopcroftKarp	,
		TwoDisconnectedEdges
	)

Definition at line 988 of file bipartite_test.cc.

References create_disconnected_bipartite(), Aleph::maps(), Aleph::HTList::size(), and verify_matching().

TEST() [50/65]

TEST	(	HopcroftKarp	,
		UnbalancedK25
	)

Definition at line 933 of file bipartite_test.cc.

References create_complete_bipartite(), Aleph::maps(), Aleph::HTList::size(), and verify_matching().

TEST() [51/65]

TEST	(	MaximumMatching	,
		CompleteBipartiteK22
	)

Definition at line 598 of file bipartite_test.cc.

References create_complete_bipartite(), Aleph::maps(), Aleph::HTList::size(), and verify_matching().

TEST() [52/65]

TEST	(	MaximumMatching	,
		CompleteBipartiteK33
	)

Definition at line 611 of file bipartite_test.cc.

References create_complete_bipartite(), Aleph::maps(), Aleph::HTList::size(), and verify_matching().

TEST() [53/65]

TEST	(	MaximumMatching	,
		CompleteBipartiteK55
	)

Definition at line 624 of file bipartite_test.cc.

References create_complete_bipartite(), Aleph::maps(), Aleph::HTList::size(), and verify_matching().

TEST() [54/65]

TEST	(	MaximumMatching	,
		EmptyGraphThrowsRangeError
	)

Definition at line 546 of file bipartite_test.cc.

References Aleph::maps().

TEST() [55/65]

TEST	(	MaximumMatching	,
		EvenCycle
	)

Definition at line 676 of file bipartite_test.cc.

References create_cycle_graph(), Aleph::maps(), Aleph::HTList::size(), and verify_matching().

TEST() [56/65]

TEST	(	MaximumMatching	,
		PathGraph4
	)

Definition at line 572 of file bipartite_test.cc.

References create_path_graph(), Aleph::maps(), Aleph::HTList::size(), and verify_matching().

TEST() [57/65]

TEST	(	MaximumMatching	,
		PathGraph5
	)

Definition at line 585 of file bipartite_test.cc.

References create_path_graph(), Aleph::maps(), Aleph::HTList::size(), and verify_matching().

TEST() [58/65]

TEST	(	MaximumMatching	,
		SingleEdge
	)

Definition at line 557 of file bipartite_test.cc.

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

TEST() [59/65]

TEST	(	MaximumMatching	,
		StarGraph
	)

Definition at line 663 of file bipartite_test.cc.

References create_star_graph(), Aleph::maps(), Aleph::HTList::size(), and verify_matching().

TEST() [60/65]

TEST	(	MaximumMatching	,
		ThrowsOnNonBipartite
	)

Definition at line 689 of file bipartite_test.cc.

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

TEST() [61/65]

TEST	(	MaximumMatching	,
		UnbalancedK25
	)

Definition at line 637 of file bipartite_test.cc.

References create_complete_bipartite(), Aleph::maps(), Aleph::HTList::size(), and verify_matching().

TEST() [62/65]

TEST	(	MaximumMatching	,
		UnbalancedK52
	)

Definition at line 650 of file bipartite_test.cc.

References create_complete_bipartite(), Aleph::maps(), Aleph::HTList::size(), and verify_matching().

TEST() [63/65]

TEST	(	MaximumMatchingClass	,
		BasicUsage
	)

Definition at line 704 of file bipartite_test.cc.

References create_complete_bipartite(), Aleph::maps(), Aleph::HTList::size(), and verify_matching().

TEST() [64/65]

TEST	(	MaximumMatchingClass	,
		ThrowsOnNonBipartite
	)

Definition at line 716 of file bipartite_test.cc.

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

TEST() [65/65]

TEST	(	MaximumMatchingStress	,
		LargeMatching
	)

Definition at line 756 of file bipartite_test.cc.

References create_complete_bipartite(), Aleph::maps(), Aleph::HTList::size(), 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 LocateFunctions< Container, Type >::get_it(), GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::DynList< T >::insert(), l, Aleph::maps(), and Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne().

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 LocateFunctions< Container, Type >::get_it(), GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::DynList< T >::insert(), and Aleph::maps().

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(), and TEST().