min_cut_example.cc File Reference

Educational examples for minimum cut algorithms. More...

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <cmath>
#include <limits>
#include <Karger_Stein.H>
#include <Stoer_Wagner.H>
#include <tpl_graph.H>

Include dependency graph for min_cut_example.cc:

Go to the source code of this file.

Functions
template<typename GT >
void	print_partition (const string &name, const DynList< typename GT::Node * > &partition)
template<typename GT >
void	print_cut_edges (GT &g, const DynList< typename GT::Arc * > &cut)
void	example_network_reliability ()
void	example_weighted_bandwidth ()
void	example_community_detection ()
void	example_algorithm_comparison ()
void	example_api_patterns ()
void	example_algorithm_selection ()
int	main ()

Detailed Description

Educational examples for minimum cut algorithms.

This file provides comprehensive, well-documented examples of using the Karger-Stein and Stoer-Wagner min-cut algorithms in Aleph-w.

---

WHAT IS A MINIMUM CUT?

A minimum cut (min-cut) of a graph is a partition of vertices into two non-empty sets S and T such that the total weight of edges crossing between S and T is minimized.

Key Properties:

• Every graph with n vertices has at least one min-cut
• A graph can have multiple min-cuts with the same weight
• Min-cut ≤ min degree of any vertex
• For complete graph Kn: min-cut = n-1

---

ALGORITHMS COMPARED

1. KARGER-STEIN (Randomized)
   • Time: O(n² log³ n)
   • Space: O(n + m)
   • Pros: Fast for large graphs, simple concept
   • Cons: Probabilistic (may need multiple runs)
   • Best for: Large sparse graphs, approximate solutions OK
2. STOER-WAGNER (Deterministic)
   • Time: O(nm + n² log n)
   • Space: O(n²)
   • Pros: Always correct, handles weights naturally
   • Cons: O(n²) space for adjacency matrix
   • Best for: Weighted graphs, exact solution required

---

COMPILE & RUN

g++ -std=c++20 -O2 -I.. -o min_cut_example min_cut_example.cc \ -lgsl -lgslcblas -lpthread ./min_cut_example

Definition in file min_cut_example.cc.

Function Documentation

example_algorithm_comparison()

void example_algorithm_comparison

(

)

Definition at line 319 of file min_cut_example.cc.

References GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and Aleph::maps().

example_algorithm_selection()

void example_algorithm_selection

(

)

Definition at line 498 of file min_cut_example.cc.

References Aleph::maps().

example_api_patterns()

void example_api_patterns

(

)

Definition at line 402 of file min_cut_example.cc.

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

example_community_detection()

void example_community_detection

(

)

Definition at line 242 of file min_cut_example.cc.

References Aleph::maps().

example_network_reliability()

void example_network_reliability

(

)

Definition at line 103 of file min_cut_example.cc.

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

example_weighted_bandwidth()

void example_weighted_bandwidth

(

)

Definition at line 177 of file min_cut_example.cc.

References Aleph::maps().

main()

int main

(

)

Definition at line 560 of file min_cut_example.cc.

print_cut_edges()

template<typename GT >

void print_cut_edges	(	GT &	g,
		const DynList< typename GT::Arc * > &	cut
	)

Definition at line 85 of file min_cut_example.cc.

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

print_partition()

template<typename GT >

void print_partition	(	const string &	name,
		const DynList< typename GT::Node * > &	partition
	)

Definition at line 67 of file min_cut_example.cc.

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