karger.cc File Reference

Tests for Karger. More...

#include <gtest/gtest.h>
#include <tpl_sgraph.H>
#include <Karger.H>

Include dependency graph for karger.cc:

Go to the source code of this file.

Classes
struct	Weight_Filter< GT >

Typedefs
using	Grafo = List_SGraph< Graph_Snode< int >, Graph_Sarc< int > >
using	Node = Grafo::Node
using	Arc = Grafo::Arc

Functions
	TEST (KargerConstruction, constructs_with_default_seed)
	TEST (KargerConstruction, constructs_with_explicit_seed)
	TEST (KargerErrors, throws_on_empty_graph)
	TEST (KargerErrors, throws_on_single_node_graph)
	TEST (KargerErrors, throws_on_single_node_with_self_loop)
	TEST (KargerErrors, throws_on_self_loop_in_graph)
	TEST (KargerErrors, throws_on_disconnected_graph)
	TEST (KargerMinCut, finds_cut_on_triangle)
	TEST (KargerMinCut, finds_cut_on_square)
	TEST (KargerMinCut, finds_obvious_cut_on_barbell)
	TEST (KargerMinCut, finds_cut_on_path)
	TEST (KargerMinCut, finds_cut_on_cycle)
	TEST (KargerMinCut, finds_cut_on_k4)
	TEST (KargerMinCut, finds_cut_on_k5)
	TEST (KargerReproducibility, same_seed_same_result)
	TEST (KargerIterations, more_iterations_not_worse)
	TEST (KargerDefaultIterations, works_with_default_iterations)
	TEST (KargerPartitions, partitions_are_valid)
	TEST (KargerCutEdges, cut_edges_are_valid)
	TEST (KargerEdgeCases, handles_two_node_graph)
	TEST (KargerMultiEdge, handles_multiple_edges_between_nodes)
	TEST (KargerStress, handles_larger_graph)
	TEST (KargerArcFilter, filters_arcs_by_weight)
	TEST (KargerArcFilter, throws_when_filter_disconnects_graph)
	TEST (KargerArcFilter, default_filter_includes_all)
	TEST (KargerArcFilter, works_with_explicit_template)
	TEST (KargerCutValidity, cut_edges_cross_partition)
	TEST (KargerDisconnected, handles_star_graph)
	TEST (KargerIterations, zero_iterations_behavior)
	TEST (KargerNonCopyable, class_is_moveable)
	TEST (KargerFast, finds_valid_cut_on_barbell)
	TEST (KargerFast, finds_cut_on_path)
	TEST (KargerFast, finds_cut_on_cycle)
	TEST (KargerFast, finds_cut_on_complete_graph)
	TEST (KargerFast, partitions_are_valid)
	TEST (KargerFast, cut_edges_are_valid)
	TEST (KargerFast, respects_num_iter_parameter)
	TEST (KargerSeed, get_seed_returns_construction_seed)
	TEST (KargerMoveSemantics, move_constructor_works)
	TEST (KargerMoveSemantics, move_assignment_works)
	TEST (KargerEarlyTermination, terminates_early_on_cut_of_one)
	TEST (KargerEarlyTermination, fast_terminates_early_on_cut_of_one)
	TEST (KargerReseed, reseed_changes_behavior)
	TEST (KargerReseed, reseed_allows_reproducibility)
	TEST (KargerSizeOnly, compute_min_cut_size_works)
	TEST (KargerSizeOnly, compute_min_cut_size_with_default_iterations)
	TEST (KargerSizeOnly, compute_min_cut_size_throws_on_invalid_graph)
	TEST (KargerSizeOnly, size_only_matches_full_computation)

Detailed Description

Tests for Karger.

Definition in file karger.cc.

Typedef Documentation

Arc

using Arc = Grafo::Arc

Definition at line 49 of file karger.cc.

Grafo

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

Definition at line 47 of file karger.cc.

Node

using Node = Grafo::Node

Definition at line 48 of file karger.cc.

Function Documentation

TEST() [1/48]

TEST	(	KargerArcFilter	,
		default_filter_includes_all
	)

Definition at line 623 of file karger.cc.

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

TEST() [2/48]

TEST	(	KargerArcFilter	,
		filters_arcs_by_weight
	)

Definition at line 560 of file karger.cc.

References Aleph::filter(), LocateFunctions< Container, Type >::get_it(), Aleph::maps(), and Aleph::min_cut().

TEST() [3/48]

TEST	(	KargerArcFilter	,
		throws_when_filter_disconnects_graph
	)

Definition at line 601 of file karger.cc.

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

TEST() [4/48]

TEST	(	KargerArcFilter	,
		works_with_explicit_template
	)

Definition at line 647 of file karger.cc.

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

TEST() [5/48]

TEST	(	KargerConstruction	,
		constructs_with_default_seed
	)

Definition at line 167 of file karger.cc.

References Aleph::maps().

TEST() [6/48]

TEST	(	KargerConstruction	,
		constructs_with_explicit_seed
	)

Definition at line 172 of file karger.cc.

References Aleph::maps().

TEST() [7/48]

TEST	(	KargerCutEdges	,
		cut_edges_are_valid
	)

Definition at line 465 of file karger.cc.

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

TEST() [8/48]

TEST	(	KargerCutValidity	,
		cut_edges_cross_partition
	)

Definition at line 667 of file karger.cc.

References LocateFunctions< Container, Type >::get_it(), Aleph::DynList< T >::insert(), and Aleph::maps().

TEST() [9/48]

TEST	(	KargerDefaultIterations	,
		works_with_default_iterations
	)

Definition at line 418 of file karger.cc.

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

TEST() [10/48]

TEST	(	KargerDisconnected	,
		handles_star_graph
	)

Definition at line 702 of file karger.cc.

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

TEST() [11/48]

TEST	(	KargerEarlyTermination	,
		fast_terminates_early_on_cut_of_one
	)

Definition at line 964 of file karger.cc.

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

TEST() [12/48]

TEST	(	KargerEarlyTermination	,
		terminates_early_on_cut_of_one
	)

Definition at line 938 of file karger.cc.

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

TEST() [13/48]

TEST	(	KargerEdgeCases	,
		handles_two_node_graph
	)

Definition at line 485 of file karger.cc.

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

TEST() [14/48]

TEST	(	KargerErrors	,
		throws_on_disconnected_graph
	)

Definition at line 236 of file karger.cc.

References Aleph::maps().

TEST() [15/48]

TEST	(	KargerErrors	,
		throws_on_empty_graph
	)

Definition at line 178 of file karger.cc.

References Aleph::maps().

TEST() [16/48]

TEST	(	KargerErrors	,
		throws_on_self_loop_in_graph
	)

Definition at line 218 of file karger.cc.

References Aleph::maps().

TEST() [17/48]

TEST	(	KargerErrors	,
		throws_on_single_node_graph
	)

Definition at line 192 of file karger.cc.

References Aleph::maps().

TEST() [18/48]

TEST	(	KargerErrors	,
		throws_on_single_node_with_self_loop
	)

Definition at line 204 of file karger.cc.

References Aleph::maps().

TEST() [19/48]

TEST	(	KargerFast	,
		cut_edges_are_valid
	)

Definition at line 846 of file karger.cc.

References LocateFunctions< Container, Type >::get_it(), Aleph::DynList< T >::insert(), and Aleph::maps().

TEST() [20/48]

TEST	(	KargerFast	,
		finds_cut_on_complete_graph
	)

Definition at line 807 of file karger.cc.

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

TEST() [21/48]

TEST	(	KargerFast	,
		finds_cut_on_cycle
	)

Definition at line 793 of file karger.cc.

References create_cycle(), Aleph::maps(), and Aleph::min_cut().

TEST() [22/48]

TEST	(	KargerFast	,
		finds_cut_on_path
	)

Definition at line 779 of file karger.cc.

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

TEST() [23/48]

TEST	(	KargerFast	,
		finds_valid_cut_on_barbell
	)

Definition at line 761 of file karger.cc.

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

TEST() [24/48]

TEST	(	KargerFast	,
		partitions_are_valid
	)

Definition at line 824 of file karger.cc.

References LocateFunctions< Container, Type >::get_it(), Aleph::DynList< T >::insert(), Aleph::maps(), and Aleph::HTList::size().

TEST() [25/48]

TEST	(	KargerFast	,
		respects_num_iter_parameter
	)

Definition at line 876 of file karger.cc.

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

TEST() [26/48]

TEST	(	KargerIterations	,
		more_iterations_not_worse
	)

Definition at line 398 of file karger.cc.

References Aleph::maps().

TEST() [27/48]

TEST	(	KargerIterations	,
		zero_iterations_behavior
	)

Definition at line 727 of file karger.cc.

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

TEST() [28/48]

TEST	(	KargerMinCut	,
		finds_cut_on_cycle
	)

Definition at line 331 of file karger.cc.

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

TEST() [29/48]

TEST	(	KargerMinCut	,
		finds_cut_on_k4
	)

Definition at line 347 of file karger.cc.

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

TEST() [30/48]

TEST	(	KargerMinCut	,
		finds_cut_on_k5
	)

Definition at line 363 of file karger.cc.

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

TEST() [31/48]

TEST	(	KargerMinCut	,
		finds_cut_on_path
	)

Definition at line 316 of file karger.cc.

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

TEST() [32/48]

TEST	(	KargerMinCut	,
		finds_cut_on_square
	)

Definition at line 279 of file karger.cc.

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

TEST() [33/48]

TEST	(	KargerMinCut	,
		finds_cut_on_triangle
	)

Definition at line 257 of file karger.cc.

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

TEST() [34/48]

TEST	(	KargerMinCut	,
		finds_obvious_cut_on_barbell
	)

Definition at line 297 of file karger.cc.

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

TEST() [35/48]

TEST	(	KargerMoveSemantics	,
		move_assignment_works
	)

Definition at line 922 of file karger.cc.

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

TEST() [36/48]

TEST	(	KargerMoveSemantics	,
		move_constructor_works
	)

Definition at line 905 of file karger.cc.

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

TEST() [37/48]

TEST	(	KargerMultiEdge	,
		handles_multiple_edges_between_nodes
	)

Definition at line 504 of file karger.cc.

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

TEST() [38/48]

TEST	(	KargerNonCopyable	,
		class_is_moveable
	)

Definition at line 749 of file karger.cc.

References Aleph::maps().

TEST() [39/48]

TEST	(	KargerPartitions	,
		partitions_are_valid
	)

Definition at line 434 of file karger.cc.

References LocateFunctions< Container, Type >::get_it(), Aleph::DynSetTree< Key, Tree, Compare >::has(), Aleph::DynSetTree< Key, Tree, Compare >::insert(), Aleph::DynList< T >::insert(), and Aleph::maps().

TEST() [40/48]

TEST	(	KargerReproducibility	,
		same_seed_same_result
	)

Definition at line 378 of file karger.cc.

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

TEST() [41/48]

TEST	(	KargerReseed	,
		reseed_allows_reproducibility
	)

Definition at line 1014 of file karger.cc.

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

TEST() [42/48]

TEST	(	KargerReseed	,
		reseed_changes_behavior
	)

Definition at line 991 of file karger.cc.

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

TEST() [43/48]

TEST	(	KargerSeed	,
		get_seed_returns_construction_seed
	)

Definition at line 896 of file karger.cc.

References Aleph::maps().

TEST() [44/48]

TEST	(	KargerSizeOnly	,
		compute_min_cut_size_throws_on_invalid_graph
	)

Definition at line 1064 of file karger.cc.

References Aleph::maps().

TEST() [45/48]

TEST	(	KargerSizeOnly	,
		compute_min_cut_size_with_default_iterations
	)

Definition at line 1052 of file karger.cc.

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

TEST() [46/48]

TEST	(	KargerSizeOnly	,
		compute_min_cut_size_works
	)

Definition at line 1041 of file karger.cc.

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

TEST() [47/48]

TEST	(	KargerSizeOnly	,
		size_only_matches_full_computation
	)

Definition at line 1072 of file karger.cc.

References Aleph::maps().

TEST() [48/48]

TEST	(	KargerStress	,
		handles_larger_graph
	)

Definition at line 530 of file karger.cc.

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