Karger's randomized minimum cut algorithm. More...

#include <Karger.H>

Classes
class	ArcIndex
	Arc index with O(1) operations and deterministic ordering. More...

Public Member Functions
	Karger_Min_Cut (const unsigned long _seed=time(nullptr), SA _sa=SA())
	Construct a Karger minimum cut solver.

	~Karger_Min_Cut ()
	Destructor. Frees the random number generator (if not moved).

	Karger_Min_Cut (const Karger_Min_Cut &)=delete
	Disable copy constructor (class owns gsl_rng pointer)

Karger_Min_Cut &	operator= (const Karger_Min_Cut &)=delete
	Disable copy assignment (class owns gsl_rng pointer)

	Karger_Min_Cut (Karger_Min_Cut &&other) noexcept
	Move constructor. Transfers ownership of the random number generator.

Karger_Min_Cut &	operator= (Karger_Min_Cut &&other) noexcept
	Move assignment operator. Transfers ownership of the random number generator.

unsigned long	get_seed () const noexcept
	Get the random seed used by this solver (useful for reproducibility).

void	reseed (const unsigned long new_seed) noexcept
	Change the random seed.

size_t	compute_min_cut_size (GT &g, size_t num_iter=0)
	Compute only the minimum cut size (without partition info).

size_t	operator() (GT &g, DynList< typename GT::Node * > &vs, DynList< typename GT::Node * > &vt, DynList< typename GT::Arc * > &cut, const size_t num_iter)
	Compute a minimum cut with a specified number of iterations.

size_t	operator() (GT &g, DynList< typename GT::Node * > &vs, DynList< typename GT::Node * > &vt, DynList< typename GT::Arc * > &cut)
	Compute minimum cut with default number of iterations.

size_t	fast (GT &g, DynList< typename GT::Node * > &vs, DynList< typename GT::Node * > &vt, DynList< typename GT::Arc * > &cut, size_t num_iter=0)
	Compute minimum cut using Karger-Stein fast algorithm.

Private Types
using	Knode = Graph_Node< DynList< typename GT::Node * > >

using	Karc = Graph_Arc< typename GT::Arc * >

using	Kgraph = List_Graph< Knode, Karc >

using	Node = typename GT::Node

using	Arc = typename GT::Arc

Private Member Functions
bool	has_self_loop (const GT &g) const

bool	is_connected_filtered (const GT &g) const

void	validate_graph (GT &g) const

void	build_kgraph (GT &g, Kgraph &kg, ArcIndex &arcs)
	Build the contracted graph representation from the original graph.

void	update_arcs (Kgraph &kg, Knode p, Knode t, Knode *cp, ArcIndex &arcs)
	Update arcs when contracting nodes p and t into cp.

void	rebuild_arc_index (Kgraph &kg, ArcIndex &arcs)
	Rebuild the arc index from scratch for the given graph.

void	contract (Kgraph &kg, size_t left_num_nodes, ArcIndex &arcs)
	Contract the graph by randomly merging edges until left_num_nodes remain.

size_t	karger_min_cut (GT &g, DynList< typename GT::Node * > &vs, DynList< typename GT::Node * > &vt, DynList< typename GT::Arc * > &cut, const size_t num_iter)
	Internal implementation of Karger's minimum cut algorithm.

size_t	__fast_karger_min_cut (Kgraph &kg, ArcIndex &arcs)
	Karger-Stein fast minimum cut algorithm (recursive version).

Private Attributes
unsigned long	seed

gsl_rng *	r

SA	sa

Detailed Description

template<class GT, class SA = Dft_Show_Arc<GT>>
class Aleph::Karger_Min_Cut< GT, SA >

Karger's randomized minimum cut algorithm.

This class implements Karger's algorithm for finding a minimum cut in an undirected graph. A minimum cut is a partition of the graph's vertices into two non-empty sets such that the number of edges crossing the partition is minimized.

The algorithm works by repeatedly contracting randomly selected edges until only two "super-nodes" remain. The edges between these super-nodes form a cut. By running multiple iterations, the algorithm finds the minimum cut with high probability.

Template parameters:

GT: Graph type (must be based on List_Graph with node/arc types).
SA: Arc filter that determines which arcs to consider. Must provide bool operator()(Arc*) returning true if the arc should be included. Defaults to Dft_Show_Arc<GT> which includes all arcs.

Time complexity:

Standard version: O(n^2 * m) per iteration, O(n^4) for n^2 iterations
Fast version (Karger-Stein): O(n^2 log^3 n)

Features:

Early termination when a cut of size 1 is found
Reuses internal graph structures across iterations for efficiency
Move-only semantics (non-copyable, moveable)
Reproducible results with seed control

Note: This algorithm is designed for undirected graphs.; The graph must be connected (considering the arc filter) and contain no self-loops.; The graph must have at least 2 nodes and 1 arc.

Example: Finding minimum cut: using GT = List_Graph<Graph_Node<int>, Graph_Arc<int>>;

GT g;

// Create a simple graph with known min-cut

auto a = g.insert_node(1);

auto b = g.insert_node(2);

auto c = g.insert_node(3);

auto d = g.insert_node(4);

// Left side

g.insert_arc(a, b);

// Right side

g.insert_arc(c, d);

// Bridge (min-cut)

g.insert_arc(b, c);

// Find minimum cut

Karger_Min_Cut<GT> karger;

DynList<GT::Node*> S, T;

DynList<GT::Arc*> cut_arcs;

size_t min_cut_size = karger(g, S, T, cut_arcs);

// min_cut_size will be 1 (the bridge)

// One valid partition is S={a, b}, T={c, d} (order may vary)

Aleph::DynList
Dynamic singly linked list with functional programming support.
Definition htlist.H:1423

Aleph::Karger_Min_Cut
Karger's randomized minimum cut algorithm.
Definition Karger.H:158

Aleph::List_Graph< Graph_Node< int >, Graph_Arc< int > >

Aleph::List_Graph::insert_node
virtual Node * insert_node(Node *node) noexcept
Insertion of a node already allocated.
Definition tpl_graph.H:524

Aleph::List_Graph::insert_arc
Arc * insert_arc(Node *src_node, Node *tgt_node, void *a)
Definition tpl_graph.H:604

Aleph::T
std::decay_t< typename HeadC::Item_Type > T
Definition ah-zip.H:107

Aleph::maps
DynList< T > maps(const C &c, Op op)
Classic map operation.
Definition ahFunctional.H:693

Aleph::Graph_Arc
Arc of graph implemented with double-linked adjacency lists.
Definition tpl_graph.H:222

Example: Multiple iterations for better probability: Karger_Min_Cut<GT> karger(12345); // Seed for reproducibility

size_t best_cut = numeric_limits<size_t>::max();

DynList<GT::Node*> best_S, best_T;

// Run multiple iterations

for (int i = 0; i < 10; ++i)

{

DynList<GT::Node*> S, T;

DynList<GT::Arc*> cut_arcs;

size_t cut_size = karger(g, S, T, cut_arcs);

if (cut_size < best_cut)

{

best_cut = cut_size;

best_S = S;

best_T = T;

}

}

Example: Using fast Karger-Stein algorithm: Karger_Min_Cut<GT> karger;

DynList<GT::Node*> S, T;

DynList<GT::Arc*> cut_arcs;

// Fast version: O(n^2 log^3 n)

size_t cut_size = karger.fast(g, S, T, cut_arcs);

See also: https://en.wikipedia.org/wiki/Karger%27s_algorithm

Definition at line 157 of file Karger.H.

Member Typedef Documentation

◆ Arc

template<class GT , class SA = Dft_Show_Arc<GT>>

using Aleph::Karger_Min_Cut< GT, SA >::Arc = typename GT::Arc

private

Definition at line 165 of file Karger.H.

◆ Karc

template<class GT , class SA = Dft_Show_Arc<GT>>

using Aleph::Karger_Min_Cut< GT, SA >::Karc = Graph_Arc<typename GT::Arc *>

private

Definition at line 161 of file Karger.H.

◆ Kgraph

template<class GT , class SA = Dft_Show_Arc<GT>>

using Aleph::Karger_Min_Cut< GT, SA >::Kgraph = List_Graph<Knode, Karc>

private

Definition at line 162 of file Karger.H.

◆ Knode

template<class GT , class SA = Dft_Show_Arc<GT>>

using Aleph::Karger_Min_Cut< GT, SA >::Knode = Graph_Node<DynList<typename GT::Node *> >

private

Definition at line 160 of file Karger.H.

◆ Node

template<class GT , class SA = Dft_Show_Arc<GT>>

using Aleph::Karger_Min_Cut< GT, SA >::Node = typename GT::Node

private

Definition at line 164 of file Karger.H.

Constructor & Destructor Documentation

◆ Karger_Min_Cut() [1/3]

template<class GT , class SA = Dft_Show_Arc<GT>>

Aleph::Karger_Min_Cut< GT, SA >::Karger_Min_Cut	(	const unsigned long	_seed = `time(nullptr)`,
		SA	_sa = `SA()`
	)

inline

Construct a Karger minimum cut solver.

Parameters

[in]	_seed	Random seed for the algorithm. Defaults to current time. Using the same seed produces reproducible results.
[in]	_sa	Arc filter to determine which arcs to consider. Defaults to Dft_Show_Arc<GT> which includes all arcs.

Definition at line 469 of file Karger.H.

References Aleph::maps(), Aleph::Karger_Min_Cut< GT, SA >::r, and Aleph::Karger_Min_Cut< GT, SA >::seed.

◆ ~Karger_Min_Cut()

template<class GT , class SA = Dft_Show_Arc<GT>>

Aleph::Karger_Min_Cut< GT, SA >::~Karger_Min_Cut ( )

inline

Destructor. Frees the random number generator (if not moved).

Definition at line 476 of file Karger.H.

References Aleph::maps(), and Aleph::Karger_Min_Cut< GT, SA >::r.

◆ Karger_Min_Cut() [2/3]

template<class GT , class SA = Dft_Show_Arc<GT>>

Aleph::Karger_Min_Cut< GT, SA >::Karger_Min_Cut ( const Karger_Min_Cut< GT, SA > & )

delete

Disable copy constructor (class owns gsl_rng pointer)

◆ Karger_Min_Cut() [3/3]

template<class GT , class SA = Dft_Show_Arc<GT>>

Aleph::Karger_Min_Cut< GT, SA >::Karger_Min_Cut ( Karger_Min_Cut< GT, SA > && other )

inlinenoexcept

Move constructor. Transfers ownership of the random number generator.

Definition at line 489 of file Karger.H.

References Aleph::maps().

Member Function Documentation

◆ __fast_karger_min_cut()

template<class GT , class SA = Dft_Show_Arc<GT>>

size_t Aleph::Karger_Min_Cut< GT, SA >::__fast_karger_min_cut	(	Kgraph &	kg,
		ArcIndex &	arcs
	)

inlineprivate

Karger-Stein fast minimum cut algorithm (recursive version).

Time complexity: O(n^2 log^3 n)

Definition at line 419 of file Karger.H.

References Aleph::Karger_Min_Cut< GT, SA >::__fast_karger_min_cut(), arcs, Aleph::Karger_Min_Cut< GT, SA >::contract(), Aleph::maps(), Aleph::Karger_Min_Cut< GT, SA >::rebuild_arc_index(), and Aleph::DynList< T >::swap().

Referenced by Aleph::Karger_Min_Cut< GT, SA >::__fast_karger_min_cut(), and Aleph::Karger_Min_Cut< GT, SA >::fast().

◆ build_kgraph()

template<class GT , class SA = Dft_Show_Arc<GT>>

void Aleph::Karger_Min_Cut< GT, SA >::build_kgraph	(	GT &	g,
		Kgraph &	kg,
		ArcIndex &	arcs
	)

inlineprivate

Build the contracted graph representation from the original graph.

Each node in kg contains a list of original nodes it represents.

Parameters

[in]	g	The original graph.
[out]	kg	The contracted graph (cleared and rebuilt).
[out]	arcs	Index of arcs for O(1) random selection.

Definition at line 247 of file Karger.H.

References Aleph::DynList< T >::append(), arcs, Aleph::clear_graph(), GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::DynList< T >::insert(), GraphCommon< GT, Node, Arc >::map_nodes(), Aleph::maps(), Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), GraphCommon< GT, Node, Arc >::reset_arcs(), GraphCommon< GT, Node, Arc >::reset_nodes(), and Aleph::Karger_Min_Cut< GT, SA >::sa.

Referenced by Aleph::Karger_Min_Cut< GT, SA >::compute_min_cut_size(), Aleph::Karger_Min_Cut< GT, SA >::fast(), and Aleph::Karger_Min_Cut< GT, SA >::karger_min_cut().

◆ compute_min_cut_size()

template<class GT , class SA = Dft_Show_Arc<GT>>

size_t Aleph::Karger_Min_Cut< GT, SA >::compute_min_cut_size	(	GT &	g,
		size_t	num_iter = `0`
	)

inline

Compute only the minimum cut size (without partition info).

This is more efficient when you only need the cut size, not the actual partition or cut edges.

Parameters

[in]	g	The undirected graph.
[in]	num_iter	Number of iterations to run.

Returns: The size of the minimum cut found.

Exceptions

std::domain_error if graph is disconnected, contains self-loops, has fewer than 2 nodes, or has no arcs.

Definition at line 532 of file Karger.H.

References arcs, Aleph::Karger_Min_Cut< GT, SA >::build_kgraph(), Aleph::Karger_Min_Cut< GT, SA >::contract(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::maps(), Aleph::min_cut(), Aleph::Karger_Min_Cut< GT, SA >::r, and Aleph::Karger_Min_Cut< GT, SA >::validate_graph().

◆ contract()

template<class GT , class SA = Dft_Show_Arc<GT>>

void Aleph::Karger_Min_Cut< GT, SA >::contract	(	Kgraph &	kg,
		size_t	left_num_nodes,
		ArcIndex &	arcs
	)

inlineprivate

Contract the graph by randomly merging edges until left_num_nodes remain.

This is the core of Karger's algorithm. Each iteration:

Randomly selects an arc
Contracts its endpoints into a single "super-node"
Removes self-loops created by the contraction
Parameters

[in,out] kg The graph to contract.

[in] left_num_nodes Stop when this many nodes remain.

[in,out] arcs Index of arcs for O(1) random selection.

Definition at line 315 of file Karger.H.

References Aleph::DynList< T >::append(), arcs, Aleph::maps(), Aleph::Karger_Min_Cut< GT, SA >::r, Aleph::DynList< T >::remove(), Aleph::DynList< T >::swap(), and Aleph::Karger_Min_Cut< GT, SA >::update_arcs().

Referenced by Aleph::Karger_Min_Cut< GT, SA >::__fast_karger_min_cut(), Aleph::Karger_Min_Cut< GT, SA >::compute_min_cut_size(), and Aleph::Karger_Min_Cut< GT, SA >::karger_min_cut().

◆ fast()

template<class GT , class SA = Dft_Show_Arc<GT>>

size_t Aleph::Karger_Min_Cut< GT, SA >::fast	(	GT &	g,
		DynList< typename GT::Node * > &	vs,
		DynList< typename GT::Node * > &	vt,
		DynList< typename GT::Arc * > &	cut,
		size_t	num_iter = `0`
	)

inline

Compute minimum cut using Karger-Stein fast algorithm.

This version uses the recursive Karger-Stein algorithm which has better time complexity: O(n^2 log^3 n) vs O(n^4) for the standard.

The algorithm is run O(log^2 n) times to achieve high probability of finding the true minimum cut.

Parameters

[in]	g	The undirected graph.
[out]	vs	Nodes in the first partition (S).
[out]	vt	Nodes in the second partition (T).
[out]	cut	Arcs crossing the minimum cut.
[in]	num_iter	Number of iterations (default: ceil(log^2 n)).

Returns: The size of the minimum cut found.

Exceptions

std::domain_error if graph is disconnected, contains self-loops, has fewer than 2 nodes, or has no arcs.

Definition at line 624 of file Karger.H.

References Aleph::Karger_Min_Cut< GT, SA >::__fast_karger_min_cut(), Aleph::DynList< T >::append(), arcs, Aleph::Karger_Min_Cut< GT, SA >::build_kgraph(), Aleph::DynList< T >::empty(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::Dlink::Iterator::has_curr(), Aleph::maps(), Aleph::Karger_Min_Cut< GT, SA >::r, Aleph::DynList< T >::swap(), and Aleph::Karger_Min_Cut< GT, SA >::validate_graph().

◆ get_seed()

template<class GT , class SA = Dft_Show_Arc<GT>>

unsigned long Aleph::Karger_Min_Cut< GT, SA >::get_seed ( ) const

inlinenoexcept

Get the random seed used by this solver (useful for reproducibility).

Definition at line 511 of file Karger.H.

References Aleph::Karger_Min_Cut< GT, SA >::seed.

◆ has_self_loop()

template<class GT , class SA = Dft_Show_Arc<GT>>

bool Aleph::Karger_Min_Cut< GT, SA >::has_self_loop ( const GT & g ) const

inlineprivate

Definition at line 213 of file Karger.H.

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

Referenced by Aleph::Karger_Min_Cut< GT, SA >::validate_graph().

◆ is_connected_filtered()

template<class GT , class SA = Dft_Show_Arc<GT>>

bool Aleph::Karger_Min_Cut< GT, SA >::is_connected_filtered ( const GT & g ) const

inlineprivate

Definition at line 221 of file Karger.H.

References GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::maps(), and Aleph::Karger_Min_Cut< GT, SA >::sa.

Referenced by Aleph::Karger_Min_Cut< GT, SA >::validate_graph().

◆ karger_min_cut()

template<class GT , class SA = Dft_Show_Arc<GT>>

size_t Aleph::Karger_Min_Cut< GT, SA >::karger_min_cut	(	GT &	g,
		DynList< typename GT::Node * > &	vs,
		DynList< typename GT::Node * > &	vt,
		DynList< typename GT::Arc * > &	cut,
		const size_t	num_iter
	)

inlineprivate

Internal implementation of Karger's minimum cut algorithm.

Runs num_iter independent contractions and returns the best cut found.

Parameters

[in]	g	The original undirected graph.
[out]	vs	Nodes in partition S of the minimum cut.
[out]	vt	Nodes in partition T of the minimum cut.
[out]	cut	Arcs crossing the minimum cut.
[in]	num_iter	Number of independent iterations to run.

Returns: Size of the minimum cut found.

Definition at line 351 of file Karger.H.

References Aleph::DynList< T >::append(), arcs, Aleph::Karger_Min_Cut< GT, SA >::build_kgraph(), Aleph::Karger_Min_Cut< GT, SA >::contract(), Aleph::DynList< T >::empty(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::Dlink::Iterator::has_curr(), Aleph::maps(), Aleph::min_cut(), Aleph::DynList< T >::swap(), and Aleph::Karger_Min_Cut< GT, SA >::validate_graph().

Referenced by Aleph::Karger_Min_Cut< GT, SA >::operator()(), and Aleph::Karger_Min_Cut< GT, SA >::operator()().

◆ operator()() [1/2]

template<class GT , class SA = Dft_Show_Arc<GT>>

size_t Aleph::Karger_Min_Cut< GT, SA >::operator()	(	GT &	g,
		DynList< typename GT::Node * > &	vs,
		DynList< typename GT::Node * > &	vt,
		DynList< typename GT::Arc * > &	cut
	)

inline

Compute minimum cut with default number of iterations.

Uses approximately n^2 iterations where n is the number of nodes, which gives a high probability of finding the true minimum cut.

Parameters

[in]	g	The undirected graph.
[out]	vs	Nodes in the first partition (S).
[out]	vt	Nodes in the second partition (T).
[out]	cut	Arcs crossing the minimum cut.

Returns: The size of the minimum cut found.

Exceptions

std::domain_error if graph is disconnected, contains self-loops, has fewer than 2 nodes, or has no arcs.

Definition at line 596 of file Karger.H.

References GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::Karger_Min_Cut< GT, SA >::karger_min_cut(), Aleph::maps(), and Aleph::Karger_Min_Cut< GT, SA >::r.

◆ operator()() [2/2]

template<class GT , class SA = Dft_Show_Arc<GT>>

size_t Aleph::Karger_Min_Cut< GT, SA >::operator()	(	GT &	g,
		DynList< typename GT::Node * > &	vs,
		DynList< typename GT::Node * > &	vt,
		DynList< typename GT::Arc * > &	cut,
		const size_t	num_iter
	)

inline

Compute a minimum cut with a specified number of iterations.

Parameters

[in]	g	The undirected graph.
[out]	vs	Nodes in the first partition (S).
[out]	vt	Nodes in the second partition (T).
[out]	cut	Arcs crossing the minimum cut.
[in]	num_iter	Number of iterations to run.

Returns: The size of the minimum cut found.

Exceptions

std::domain_error if the graph is disconnected, contains self-loops, has fewer than 2 nodes, or has no arcs.

Definition at line 574 of file Karger.H.

References Aleph::Karger_Min_Cut< GT, SA >::karger_min_cut(), Aleph::maps(), and Aleph::Karger_Min_Cut< GT, SA >::r.

◆ operator=() [1/2]

template<class GT , class SA = Dft_Show_Arc<GT>>

Karger_Min_Cut & Aleph::Karger_Min_Cut< GT, SA >::operator= ( const Karger_Min_Cut< GT, SA > & )

delete

Disable copy assignment (class owns gsl_rng pointer)

◆ operator=() [2/2]

template<class GT , class SA = Dft_Show_Arc<GT>>

Karger_Min_Cut & Aleph::Karger_Min_Cut< GT, SA >::operator= ( Karger_Min_Cut< GT, SA > && other )

inlinenoexcept

Move assignment operator. Transfers ownership of the random number generator.

Definition at line 496 of file Karger.H.

References Aleph::maps(), Aleph::Karger_Min_Cut< GT, SA >::r, Aleph::Karger_Min_Cut< GT, SA >::sa, and Aleph::Karger_Min_Cut< GT, SA >::seed.

◆ rebuild_arc_index()

template<class GT , class SA = Dft_Show_Arc<GT>>

void Aleph::Karger_Min_Cut< GT, SA >::rebuild_arc_index	(	Kgraph &	kg,
		ArcIndex &	arcs
	)

inlineprivate

Rebuild the arc index from scratch for the given graph.

Used after copying a graph to ensure pointers point to the copy's arcs.

Definition at line 300 of file Karger.H.

References arcs, Aleph::Dlink::Iterator::has_curr(), and Aleph::maps().

Referenced by Aleph::Karger_Min_Cut< GT, SA >::__fast_karger_min_cut().

◆ reseed()

template<class GT , class SA = Dft_Show_Arc<GT>>

void Aleph::Karger_Min_Cut< GT, SA >::reseed ( const unsigned long new_seed )

inlinenoexcept

Change the random seed.

Useful for running multiple independent trials.

Parameters

[in] new_seed The new seed value.

Definition at line 515 of file Karger.H.

References Aleph::maps(), Aleph::Karger_Min_Cut< GT, SA >::r, and Aleph::Karger_Min_Cut< GT, SA >::seed.

◆ update_arcs()

template<class GT , class SA = Dft_Show_Arc<GT>>

void Aleph::Karger_Min_Cut< GT, SA >::update_arcs	(	Kgraph &	kg,
		Knode *	p,
		Knode *	t,
		Knode *	cp,
		ArcIndex &	arcs
	)

inlineprivate

Update arcs when contracting nodes p and t into cp.

Moves all arcs from node p to the new contracted node cp, except arcs that connect to t (which become self-loops and are removed).

Parameters

[in,out]	kg	The contracted graph.
[in]	p	Source node being contracted.
[in]	t	Target node being contracted (arcs to t are skipped).
[in]	cp	New contracted node that replaces p and t.
[in,out]	arcs	Index of arcs (updated to reflect changes).