Stoer-Wagner deterministic minimum cut algorithm. More...

#include <Stoer_Wagner.H>

Collaboration diagram for Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >:

Classes
struct	PQEntry

struct	SWNode

Public Types
using	Node = typename GT::Node

using	Arc = typename GT::Arc

using	Weight = typename Distance::Distance_Type

Public Member Functions
	Stoer_Wagner_Min_Cut ()=default
	Default constructor.

	Stoer_Wagner_Min_Cut (Distance _distance)
	Constructor with custom distance functor.

Weight	operator() (GT &g, DynList< Node * > &vs, DynList< Node * > &vt, DynList< Arc * > &cut)
	Find minimum cut in graph.

Weight	min_cut_weight (GT &g)
	Find only the minimum cut weight (faster, no partition info).

Private Member Functions
void	init_from_graph (GT &g)

std::tuple< size_t, size_t, Weight >	minimum_cut_phase ()

void	merge_nodes (size_t s, size_t t)

Private Attributes
Distance	distance

SA	sa

std::vector< std::vector< Weight > >	adj

std::vector< SWNode >	nodes

size_t	active_count

Detailed Description

template<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, ArcFilter< GT > SA = Dft_Show_Arc<GT>>
class Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >

Stoer-Wagner deterministic minimum cut algorithm.

This class implements the Stoer-Wagner algorithm for finding the global minimum cut in an undirected weighted graph. Unlike randomized algorithms (Karger, Karger-Stein), Stoer-Wagner is deterministic and always finds the exact minimum cut.

Algorithm Overview

The algorithm is based on the observation that for any two vertices s and t, the global minimum cut is either:

The minimum s-t cut, OR
The minimum cut of the graph with s and t merged

It uses Maximum Adjacency Search to efficiently find minimum s-t cuts.

Template Parameters

GT: Graph type (must be based on List_Graph)
Distance: Functor to extract edge weight. Must provide Weight operator()(Arc*). Defaults to extracting arc->get_info() as the weight.
SA: Arc filter functor. Defaults to showing all arcs.

Weight Type

The algorithm works with any numeric weight type that supports:

Addition (+)
Comparison (<)
Assignment (=)
Zero initialization

Example Usage

#include <Stoer_Wagner.H>
#include <tpl_graph.H>
 
using GT = List_Graph<Graph_Node<string>, Graph_Arc<int>>;
GT g;
 
// Build weighted graph
auto a = g.insert_node("A");
auto b = g.insert_node("B");
auto c = g.insert_node("C");
auto d = g.insert_node("D");
 
g.insert_arc(a, b, 2);  // Weight 2
g.insert_arc(b, c, 3);
g.insert_arc(c, d, 4);
g.insert_arc(d, a, 1);
g.insert_arc(a, c, 5);
 
// Find minimum cut
Stoer_Wagner_Min_Cut<GT> solver;
DynList<GT::Node*> S, T;
DynList<GT::Arc*> cut_arcs;
 
int cut_weight = solver(g, S, T, cut_arcs);
cout << "Min-cut weight: " << cut_weight << endl;

Example: Unweighted graph (all edges have weight 1): // For unweighted graphs, use a constant distance functor

struct UnitWeight {

int operator()(GT::Arc*) const { return 1; }

};

Stoer_Wagner_Min_Cut<GT, UnitWeight> solver;

int cut_size = solver(g, S, T, cut_arcs);

See also: Karger_Min_Cut Randomized algorithm (simpler, slower); Karger_Stein_Min_Cut Faster randomized algorithm; https://en.wikipedia.org/wiki/Stoer%E2%80%93Wagner_algorithm

Definition at line 205 of file Stoer_Wagner.H.

Member Typedef Documentation

◆ Arc

template<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

using Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >::Arc = typename GT::Arc

Definition at line 209 of file Stoer_Wagner.H.

◆ Node

template<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

using Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >::Node = typename GT::Node

Definition at line 208 of file Stoer_Wagner.H.

◆ Weight

template<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

using Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >::Weight = typename Distance::Distance_Type

Definition at line 210 of file Stoer_Wagner.H.

Constructor & Destructor Documentation

◆ Stoer_Wagner_Min_Cut() [1/2]

template<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >::Stoer_Wagner_Min_Cut ( )

default

Default constructor.

◆ Stoer_Wagner_Min_Cut() [2/2]

template<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >::Stoer_Wagner_Min_Cut ( Distance _distance )

inlineexplicit

Constructor with custom distance functor.

Parameters

_distance Functor to extract edge weights

Definition at line 401 of file Stoer_Wagner.H.

Member Function Documentation

◆ init_from_graph()

template<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

void Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >::init_from_graph ( GT & g )

inlineprivate

Definition at line 242 of file Stoer_Wagner.H.

References Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >::active_count, Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >::adj, Aleph::blossom_maximum_cardinality_matching(), Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >::distance, GraphCommon< GT, Node, Arc >::get_num_nodes(), GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), NODE_COUNTER, Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >::nodes, Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >::sa, and w.

Referenced by Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >::min_cut_weight(), and Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >::operator()().

◆ merge_nodes()

template<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

void Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >::merge_nodes	(	size_t	s,
		size_t	t
	)

inlineprivate

Definition at line 366 of file Stoer_Wagner.H.

References Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >::active_count, Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >::adj, and Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >::nodes.

Referenced by Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >::min_cut_weight(), and Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >::operator()().

◆ min_cut_weight()

template<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

Weight Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >::min_cut_weight ( GT & g )

inline

Find only the minimum cut weight (faster, no partition info).

If you only need the cut weight and not the actual partition, this method is slightly more efficient.

Parameters

[in] g Input graph

Returns: Weight of the minimum cut

Definition at line 511 of file Stoer_Wagner.H.

References Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >::active_count, Aleph::blossom_maximum_cardinality_matching(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >::init_from_graph(), Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >::merge_nodes(), and Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >::minimum_cut_phase().

Referenced by example_api_patterns(), TEST(), TEST(), TEST(), TEST(), and test_sw_min_cut_weight_only().

◆ minimum_cut_phase()

template<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

std::tuple< size_t, size_t, Weight > Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >::minimum_cut_phase ( )

inlineprivate

Definition at line 275 of file Stoer_Wagner.H.

References Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >::active_count, Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >::adj, Aleph::blossom_maximum_cardinality_matching(), Aleph::count(), Aleph::next(), and Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >::nodes.

Referenced by Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >::min_cut_weight(), and Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >::operator()().

◆ operator()()

template<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

Weight Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >::operator()	(	GT &	g,
		DynList< Node * > &	vs,
		DynList< Node * > &	vt,
		DynList< Arc * > &	cut
	)

inline

Find minimum cut in graph.

Executes the Stoer-Wagner algorithm to find the exact minimum cut. For weighted graphs, returns the minimum total weight of cut edges. For unweighted graphs (weight=1), returns the minimum number of edges.

Parameters