stoer_wagner_min_cut

Determines a min-cut and the min-cut weight of a connected, undirected graph.

Complexity: O(V * E + V2 log V)
Defined in: <boost/graph/stoer_wagner_min_cut.hpp>

Description

A cut of a graph G is a partition of the vertices into two, non-empty sets. The weight of such a partition is the number of edges between the two sets if G is unweighted, or the sum of the weights of all edges between the two sets if G is weighted. A min-cut is a cut having the least weight.

Sometimes a graph has multiple min-cuts, but all have the same weight. The stoer_wagner_min_cut function implements the Stoer-Wagner algorithm and determines exactly one of the min-cuts as well as its weight.

A min-cut of a weighted graph having min-cut weight 4
Figure 1. A min-cut of a weighted graph having min-cut weight 4

The stoer_wagner_min_cut function moved to namespace boost::graph. The boost:: overloads, both positional and named parameter, are kept for backward compatibility but are deprecated. Removal planned for Boost 1.95.

Overloads

(1) Fully Positional

namespace boost::graph {
template <class UndirectedGraph, class WeightMap, class ParityMap,
          class VertexAssignmentMap, class KeyedUpdatablePriorityQueue,
          class IndexMap>
typename property_traits<WeightMap>::value_type
stoer_wagner_min_cut(
    const UndirectedGraph& g, WeightMap weights,
    ParityMap parities, VertexAssignmentMap assignments,
    KeyedUpdatablePriorityQueue& pq, IndexMap index_map);
}
Direction Parameter Description

IN

const UndirectedGraph& g

A connected, undirected graph. The graph type must be a model of Vertex List Graph and Incidence Graph.

IN

WeightMap weights

The weight or length of each edge in the graph. The WeightMap type must be a model of Readable Property Map and its value type must be Less Than Comparable and summable. The key type of this map needs to be the graph’s edge descriptor type.

OUT

ParityMap parities

Records which of the two min-cut sets each vertex belongs to, by setting the parity to true (one set) or false (the other). ParityMap must be a model of a Writable Property Map and its value type should be a bool type. The key type must be the graph’s vertex descriptor type. Pass boost::dummy_property_map() when only the min-cut weight is needed.

UTIL

VertexAssignmentMap assignments

Work space mapping each vertex to the vertex it is assigned to. Must be a model of Read/Write Property Map. The key and value types must be the graph’s vertex descriptor type. No particular meaning should be derived from its values after completion.

UTIL

KeyedUpdatablePriorityQueue& pq

A max priority queue keyed on the reach counts. It must be a model of Keyed Updatable Queue and a max-Updatable Priority Queue. The value type must be the graph’s vertex descriptor and the key type must be the weight type. It must be empty when passed in.

IN

IndexMap index_map

Maps each vertex to an integer in the range [0, num_vertices(g)). IndexMap must be a model of Readable Property Map. The value type must be an integer type and the key type the graph’s vertex descriptor type.

Example

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/stoer_wagner_min_cut.hpp>
#include <boost/property_map/property_map.hpp>
#include <iostream>

struct EdgeProps { int weight; };

using Graph = boost::adjacency_list< boost::vecS, boost::vecS, boost::undirectedS,
    boost::no_property, EdgeProps >;

int main() {
    Graph g{4};
    boost::add_edge(0, 1, EdgeProps{2}, g);
    boost::add_edge(0, 2, EdgeProps{3}, g);
    boost::add_edge(1, 2, EdgeProps{3}, g);
    boost::add_edge(1, 3, EdgeProps{2}, g);
    boost::add_edge(2, 3, EdgeProps{4}, g);

    auto weight_map = get(&EdgeProps::weight, g);
    // only the min-cut weight is needed here, so discard the partition
    int cut = boost::graph::stoer_wagner_min_cut(g, weight_map, boost::dummy_property_map());
    std::cout << "Stoer-Wagner min cut: " << cut << "\n";
}
Stoer-Wagner min cut: 5

(2) Five arguments overload

The index map is the least interesting argument, so this form defaults it to get(vertex_index, g). Requires the graph to have an interior vertex_index_t property.

namespace boost::graph {
template <class UndirectedGraph, class WeightMap, class ParityMap,
          class VertexAssignmentMap, class KeyedUpdatablePriorityQueue>
typename property_traits<WeightMap>::value_type
stoer_wagner_min_cut(
    const UndirectedGraph& g, WeightMap weights,
    ParityMap parities, VertexAssignmentMap assignments,
    KeyedUpdatablePriorityQueue& pq);
}

(3) Three arguments overload

Building the assignment map and the priority queue is the cumbersome part, so this form defaults them along with the index map. Pass boost::dummy_property_map() for parities when only the min-cut weight is needed.

namespace boost::graph {
template <class UndirectedGraph, class WeightMap, class ParityMap>
typename property_traits<WeightMap>::value_type
stoer_wagner_min_cut(const UndirectedGraph& g, WeightMap weights, ParityMap parities);
}

(4) Six arguments overload (deprecated)

Deprecated: this overload moved to namespace boost::graph. Use the positional boost::graph::stoer_wagner_min_cut overloads instead. Removal planned for Boost 1.95.

 
namespace boost {
template <class UndirectedGraph, class WeightMap, class ParityMap,
          class VertexAssignmentMap, class KeyedUpdatablePriorityQueue,
          class IndexMap>
typename property_traits<WeightMap>::value_type
stoer_wagner_min_cut(
    const UndirectedGraph& g, WeightMap weights,
    ParityMap parities, VertexAssignmentMap assignments,
    KeyedUpdatablePriorityQueue& pq, IndexMap index_map);
}

Identical to overload (1) except for its namespace. Kept in boost:: for backward compatibility.

(5) Named parameter version (deprecated)

Deprecated: the named parameter interface is deprecated. Use the positional boost::graph::stoer_wagner_min_cut overloads instead. Removal planned for Boost 1.95.

 
template <class UndirectedGraph, class WeightMap,
          class P, class T, class R>
weight_type stoer_wagner_min_cut(
    const UndirectedGraph& g,
    WeightMap weights,
    const bgl_named_params<P, T, R>& params = all defaults);
Direction Parameter Description

IN

const UndirectedGraph& g

A connected, undirected graph. The graph type must be a model of Vertex List Graph and Incidence Graph.

IN

WeightMap weights

The weight or length of each edge in the graph. The WeightMap type must be a model of Readable Property Map and its value type must be Less Than Comparable and summable. The key type of this map needs to be the graph’s edge descriptor type.
Direction Named Parameter Description / Default

OUT

parity_map(ParityMap parities)

The algorithm computes a min-cut, which divides the set of vertices into two, non-empty sets. The stoer_wagner_min_cut function records which of the two sets that each vertex belongs to by setting the parity to true (representing one set) or false (for the other). ParityMap must be a model of a Writable Property Map and its value type should be a bool type. The key type must be the graph’s vertex descriptor type.
Default: boost::dummy_property_map

IN

vertex_index_map(VertexIndexMap vertexIndices)

This maps each vertex to an integer in the range [0, num_vertices(g)). This is only necessary if the default is used for the assignment, index-in-heap, or distance maps. VertexIndexMap must be a model of Readable Property Map. The value type of the map must be an integer type. The key type must be the graph’s vertex descriptor type.
Default: get(boost::vertex_index, g)

UTIL

assignment_map(AssignmentMap assignments)

AssignmentMap must be a model of Read/Write Property Map. The key and value types must be the graph’s vertex descriptor type.
Default: A boost::iterator_property_map using a std::vector of num_vertices(g) vertex descriptors and vertexIndices for the index map.

UTIL

max_priority_queue(MaxPriorityQueue& pq)

MaxPriorityQueue must be a model of Keyed Updatable Queue and a max-Updatable Priority Queue. The value type must be the graph’s vertex descriptor and the key type must be the weight type.
Default: A boost::d_ary_heap_indirect using a default index-in-heap and distance map.

UTIL

index_in_heap_map(IndexInHeapMap indicesInHeap)

This parameter only has an effect when the default max-priority queue is used.
IndexInHeapMap must be a model of Read/Write Property Map. The key type must be the graph’s vertex descriptor type. The value type must be a size type (typename std::vector<vertex_descriptor>::size_type).
Default: A boost::iterator_property_map using a std::vector of num_vertices(g) size type objects and vertexIndices for the index map.

UTIL

distance_map(DistanceMap wAs)

This parameter only has an effect when the default max-priority queue is used.
DistanceMap must be a model of Read/Write Property Map. The key type must be the graph’s vertex descriptor type. The value type must be the weight type (typename boost::property_traits<WeightMap>::value_type).
Default: A boost::iterator_property_map using a std::vector of num_vertices(g) weight type objects and vertexIndices for the index map.

Returns

The weight of the min-cut.

Throws

bad_graph

If num_vertices(g) is less than 2.

std::invalid_argument

If a max-priority queue is given as an argument and it is not empty.

References

  • [74] Mehlhorn, Kurt and Christian Uhrig (1995). The minimum cut algorithm of Stoer and Wagner.

  • [75] Stoer, Mechthild and Frank Wagner (1997). A simple min-cut algorithm. Journal of the ACM 44 (4), 585-591.

  • [76] Zwick, Uri (2008). Global minimum cuts.