Comprehensive test suite for min-cut algorithms. More...

#include <iostream>
#include <iomanip>
#include <chrono>
#include <cassert>
#include <cmath>
#include <string>
#include <sstream>
#include <functional>
#include <Karger.H>
#include <Stoer_Wagner.H>
#include <tpl_graph.H>
#include <tpl_sgraph.H>

Include dependency graph for min_cut_test.cc:

Classes
class	Timer

Macros
#define	TEST(name)

#define	PASS()

#define	FAIL(msg)

#define	CHECK(cond, msg)

#define	CHECK_EQ(a, b, msg)

Typedefs
using	UnweightedGraph = List_Graph< Graph_Node< int >, Graph_Arc< int > >

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

Functions
void	build_path_graph (UnweightedGraph &g, int n)
	Build a path graph: 0 - 1 - 2 - ... - (n-1) Min-cut: 1 (any single edge)

void	build_cycle_graph (UnweightedGraph &g, int n)
	Build a cycle graph: 0 - 1 - 2 - ... - (n-1) - 0 Min-cut: 2 (need to cut two edges to disconnect)

void	build_complete_graph (UnweightedGraph &g, int n)
	Build a complete graph Kn Min-cut: n-1 (isolate any single vertex)

void	build_barbell_graph (UnweightedGraph &g, int k)
	Build a barbell graph: two K_k cliques connected by a single edge Min-cut: 1 (the bridge between cliques)

void	build_two_clusters (UnweightedGraph &g, int cluster_size, int bridge_count)
	Build two clusters connected by k edges Min-cut: k.

void	build_weighted_chain (WeightedGraph &g, int w1, int w2, int w3)
	Build a weighted graph with known min-cut Structure: A-B-C-D where weights determine the cut.

void	test_ks_empty_graph ()

void	test_ks_single_edge ()

void	test_ks_triangle ()

void	test_ks_barbell ()

void	test_ks_path ()

void	test_ks_cycle ()

void	test_ks_two_clusters ()

void	test_ks_find_with_iterations ()

void	test_ks_seed_reproducibility ()

void	test_sw_empty_graph ()

void	test_sw_single_edge ()

void	test_sw_triangle_weighted ()

void	test_sw_chain_weighted ()

void	test_sw_complete_k4 ()

void	test_sw_two_heavy_clusters ()

void	test_sw_min_cut_weight_only ()

void	test_sw_unit_weight ()

void	test_cross_comparison ()

void	test_performance_ks ()

void	test_performance_sw ()

int	main ()

Variables
static int	tests_passed = 0

static int	tests_failed = 0

static int	total_tests = 0

Detailed Description

Comprehensive test suite for min-cut algorithms.

Tests both Karger-Stein (randomized) and Stoer-Wagner (deterministic) algorithms against known graphs with analytically computed min-cuts.

TEST CATEGORIES:

Basic correctness tests (small graphs with known min-cuts)
Edge cases (empty graphs, single node, disconnected)
Special graph structures (complete, bipartite, path, cycle)
Weighted graph tests (for Stoer-Wagner)
Performance tests (timing on larger graphs)
Consistency tests (multiple runs should converge)

COMPILE: g++ -std=c++20 -O2 -I.. -o min_cut_test min_cut_test.cc -lgsl -lgslcblas -lpthread

RUN: ./min_cut_test

Definition in file min_cut_test.cc.

Macro Definition Documentation

◆ CHECK

#define CHECK	(	cond,
		msg
	)

Value:

  do { \
    if (!(cond)) { FAIL(msg); return; } \
  } while(0)

Definition at line 67 of file min_cut_test.cc.

◆ CHECK_EQ

#define CHECK_EQ	(	a,
		b,
		msg
	)

Value:

  do { \
    if ((a) != (b)) { \
      stringstream ss; \
      ss << msg << " (expected " << (b) << ", got " << (a) << ")"; \
      FAIL(ss.str()); \
      return; \
    } \
  } while(0)

Definition at line 72 of file min_cut_test.cc.

◆ FAIL

#define FAIL ( msg )

Value:

  do { \
    tests_failed++; \
    cout << "\033[31mFAIL\033[0m (" << msg << ")\n"; \
  } while(0)

Definition at line 61 of file min_cut_test.cc.

◆ PASS

#define PASS ( )

Value:

  do { \
    tests_passed++; \
    cout << "\033[32mPASS\033[0m\n"; \
  } while(0)

Definition at line 55 of file min_cut_test.cc.

◆ TEST

#define TEST ( name )

Value:

  do { \
    total_tests++; \
    cout << "  Testing: " << name << "... " << flush; \
  } while(0)

Definition at line 49 of file min_cut_test.cc.

Typedef Documentation

◆ UnweightedGraph

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

Definition at line 99 of file min_cut_test.cc.

◆ WeightedGraph

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

Definition at line 100 of file min_cut_test.cc.

Function Documentation

◆ build_barbell_graph()

void build_barbell_graph	(	UnweightedGraph &	g,
		int	k
	)

Build a barbell graph: two K_k cliques connected by a single edge Min-cut: 1 (the bridge between cliques)

Definition at line 163 of file min_cut_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_ks_barbell(), and test_ks_find_with_iterations().

◆ build_complete_graph()

void build_complete_graph	(	UnweightedGraph &	g,
		int	n
	)

Build a complete graph Kn Min-cut: n-1 (isolate any single vertex)

Definition at line 145 of file min_cut_test.cc.

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

◆ build_cycle_graph()

void build_cycle_graph	(	UnweightedGraph &	g,
		int	n
	)

Build a cycle graph: 0 - 1 - 2 - ... - (n-1) - 0 Min-cut: 2 (need to cut two edges to disconnect)

Definition at line 127 of file min_cut_test.cc.

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

Referenced by test_ks_cycle().

◆ build_path_graph()

void build_path_graph	(	UnweightedGraph &	g,
		int	n
	)

Build a path graph: 0 - 1 - 2 - ... - (n-1) Min-cut: 1 (any single edge)

Definition at line 110 of file min_cut_test.cc.

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

Referenced by test_ks_path().

◆ build_two_clusters()

void build_two_clusters	(	UnweightedGraph &	g,
		int	cluster_size,
		int	bridge_count
	)

Build two clusters connected by k edges Min-cut: k.

Definition at line 198 of file min_cut_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_ks_seed_reproducibility(), and test_ks_two_clusters().

◆ build_weighted_chain()

void build_weighted_chain	(	WeightedGraph &	g,
		int	w1,
		int	w2,
		int	w3
	)

Build a weighted graph with known min-cut Structure: A-B-C-D where weights determine the cut.

Definition at line 236 of file min_cut_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_sw_chain_weighted(), and test_sw_min_cut_weight_only().

◆ main()

◆ test_cross_comparison()

void test_cross_comparison ( )

Definition at line 642 of file min_cut_test.cc.

References CHECK, Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::maps(), min(), PASS, and TEST.

Referenced by main().

◆ test_ks_barbell()

void test_ks_barbell ( )

Definition at line 318 of file min_cut_test.cc.

References build_barbell_graph(), CHECK, Aleph::maps(), min(), PASS, and TEST.

Referenced by main().

◆ test_ks_cycle()

void test_ks_cycle ( )

Definition at line 363 of file min_cut_test.cc.

References build_cycle_graph(), CHECK, Aleph::maps(), min(), PASS, and TEST.

Referenced by main().

◆ test_ks_empty_graph()

void test_ks_empty_graph ( )

Definition at line 255 of file min_cut_test.cc.

References PASS, and TEST.

Referenced by main().

◆ test_ks_find_with_iterations()

void test_ks_find_with_iterations ( )

Definition at line 407 of file min_cut_test.cc.

References build_barbell_graph(), CHECK, Aleph::HTList::is_empty(), Aleph::maps(), PASS, and TEST.

Referenced by main().

◆ test_ks_path()

void test_ks_path ( )

Definition at line 341 of file min_cut_test.cc.

References build_path_graph(), CHECK, Aleph::maps(), min(), PASS, and TEST.

Referenced by main().

◆ test_ks_seed_reproducibility()

void test_ks_seed_reproducibility ( )

Definition at line 426 of file min_cut_test.cc.

References build_two_clusters(), CHECK_EQ, Aleph::maps(), PASS, and TEST.

Referenced by main().

◆ test_ks_single_edge()

void test_ks_single_edge ( )

Definition at line 263 of file min_cut_test.cc.

References CHECK, Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::maps(), min(), PASS, and TEST.

Referenced by main().

◆ test_ks_triangle()

void test_ks_triangle ( )

Definition at line 289 of file min_cut_test.cc.

References CHECK, Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::maps(), min(), PASS, and TEST.

Referenced by main().

◆ test_ks_two_clusters()

void test_ks_two_clusters ( )

Definition at line 385 of file min_cut_test.cc.

References build_two_clusters(), CHECK, Aleph::maps(), min(), PASS, and TEST.

Referenced by main().

◆ test_performance_ks()

void test_performance_ks ( )

Definition at line 708 of file min_cut_test.cc.

References CHECK, Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::maps(), N, nodes, PASS, and TEST.

Referenced by main().

◆ test_performance_sw()

void test_performance_sw ( )

Definition at line 747 of file min_cut_test.cc.

References CHECK, Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::maps(), N, nodes, PASS, TEST, and Aleph::to_string().

Referenced by main().

◆ test_sw_chain_weighted()

void test_sw_chain_weighted ( )

Definition at line 518 of file min_cut_test.cc.

References build_weighted_chain(), CHECK, Aleph::maps(), Aleph::min_cut(), PASS, and TEST.

Referenced by main().

◆ test_sw_complete_k4()

void test_sw_complete_k4 ( )

Definition at line 535 of file min_cut_test.cc.

References CHECK, Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::maps(), Aleph::min_cut(), PASS, and TEST.

Referenced by main().

◆ test_sw_empty_graph()

void test_sw_empty_graph ( )

Definition at line 450 of file min_cut_test.cc.

References CHECK_EQ, Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::maps(), Aleph::min_cut(), PASS, Aleph::HTList::size(), and TEST.

Referenced by main().

◆ test_sw_min_cut_weight_only()

void test_sw_min_cut_weight_only ( )

Definition at line 594 of file min_cut_test.cc.

References build_weighted_chain(), CHECK, Aleph::maps(), Aleph::min_cut(), PASS, and TEST.

Referenced by main().

◆ test_sw_single_edge()

void test_sw_single_edge ( )

Definition at line 469 of file min_cut_test.cc.

References CHECK, Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::maps(), Aleph::min_cut(), PASS, and TEST.

Referenced by main().

◆ test_sw_triangle_weighted()

void test_sw_triangle_weighted ( )

Definition at line 489 of file min_cut_test.cc.

References CHECK, Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::maps(), Aleph::min_cut(), PASS, and TEST.

Referenced by main().

◆ test_sw_two_heavy_clusters()

void test_sw_two_heavy_clusters ( )

Definition at line 565 of file min_cut_test.cc.

References CHECK, Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::maps(), Aleph::min_cut(), PASS, and TEST.

Referenced by main().

◆ test_sw_unit_weight()

void test_sw_unit_weight ( )

Definition at line 608 of file min_cut_test.cc.

References CHECK, Aleph::maps(), Aleph::min_cut(), PASS, and TEST.

Referenced by main().

Variable Documentation

◆ tests_failed

int tests_failed = 0

static

Definition at line 46 of file min_cut_test.cc.

Referenced by main().

◆ tests_passed

int tests_passed = 0

static

Definition at line 45 of file min_cut_test.cc.

Referenced by main().

◆ total_tests

int total_tests = 0

static

Definition at line 47 of file min_cut_test.cc.

Referenced by main().

Classes

Macros

Typedefs

Functions

Variables

Detailed Description

TEST CATEGORIES:

Macro Definition Documentation

◆ CHECK

◆ CHECK_EQ

◆ FAIL

◆ PASS

◆ TEST

Typedef Documentation

◆ UnweightedGraph

◆ WeightedGraph

Function Documentation

◆ build_barbell_graph()

◆ build_complete_graph()

◆ build_cycle_graph()

◆ build_path_graph()

◆ build_two_clusters()

◆ build_weighted_chain()

◆ main()

◆ test_cross_comparison()

◆ test_ks_barbell()

◆ test_ks_cycle()

◆ test_ks_empty_graph()

◆ test_ks_find_with_iterations()

◆ test_ks_path()

◆ test_ks_seed_reproducibility()

◆ test_ks_single_edge()

◆ test_ks_triangle()

◆ test_ks_two_clusters()

◆ test_performance_ks()

◆ test_performance_sw()

◆ test_sw_chain_weighted()

◆ test_sw_complete_k4()

◆ test_sw_empty_graph()

◆ test_sw_min_cut_weight_only()

◆ test_sw_single_edge()

◆ test_sw_triangle_weighted()

◆ test_sw_two_heavy_clusters()

◆ test_sw_unit_weight()

Variable Documentation

◆ tests_failed

◆ tests_passed

◆ total_tests