Note

This documents the development version of NetworkX. Documentation for the current release can be found here.

# networkx.algorithms.connectivity.stoerwagner.stoer_wagner¶

stoer_wagner(G, weight='weight', heap=<class 'networkx.utils.heaps.BinaryHeap'>)[source]

Returns the weighted minimum edge cut using the Stoer-Wagner algorithm.

Determine the minimum edge cut of a connected graph using the Stoer-Wagner algorithm. In weighted cases, all weights must be nonnegative.

The running time of the algorithm depends on the type of heaps used:

Type of heap

Running time

Binary heap

$$O(n (m + n) \log n)$$

Fibonacci heap

$$O(nm + n^2 \log n)$$

Pairing heap

$$O(2^{2 \sqrt{\log \log n}} nm + n^2 \log n)$$

Parameters
• G (NetworkX graph) – Edges of the graph are expected to have an attribute named by the weight parameter below. If this attribute is not present, the edge is considered to have unit weight.

• weight (string) – Name of the weight attribute of the edges. If the attribute is not present, unit weight is assumed. Default value: ‘weight’.

• heap (class) – Type of heap to be used in the algorithm. It should be a subclass of MinHeap or implement a compatible interface.

If a stock heap implementation is to be used, BinaryHeap is recommended over PairingHeap for Python implementations without optimized attribute accesses (e.g., CPython) despite a slower asymptotic running time. For Python implementations with optimized attribute accesses (e.g., PyPy), PairingHeap provides better performance. Default value: BinaryHeap.

Returns

• cut_value (integer or float) – The sum of weights of edges in a minimum cut.

• partition (pair of node lists) – A partitioning of the nodes that defines a minimum cut.

Raises
• NetworkXNotImplemented – If the graph is directed or a multigraph.

• NetworkXError – If the graph has less than two nodes, is not connected or has a negative-weighted edge.

Examples

>>> G = nx.Graph()