Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

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 recommeded 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()
>>> G.add_edge('x', 'a', weight=3)
>>> G.add_edge('x', 'b', weight=1)
>>> G.add_edge('a', 'c', weight=3)
>>> G.add_edge('b', 'c', weight=5)
>>> G.add_edge('b', 'd', weight=4)
>>> G.add_edge('d', 'e', weight=2)
>>> G.add_edge('c', 'y', weight=2)
>>> G.add_edge('e', 'y', weight=3)
>>> cut_value, partition = nx.stoer_wagner(G)
>>> cut_value
4