Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""
2Stoer-Wagner minimum cut algorithm.
3"""
5from itertools import islice
7import networkx as nx
9from ...utils import BinaryHeap, arbitrary_element, not_implemented_for
11__all__ = ["stoer_wagner"]
14@not_implemented_for("directed")
15@not_implemented_for("multigraph")
16@nx._dispatchable(edge_attrs="weight")
17def stoer_wagner(G, weight="weight", heap=BinaryHeap):
18 r"""Returns the weighted minimum edge cut using the Stoer-Wagner algorithm.
20 Determine the minimum edge cut of a connected graph using the
21 Stoer-Wagner algorithm. In weighted cases, all weights must be
22 nonnegative.
24 The running time of the algorithm depends on the type of heaps used:
26 ============== =============================================
27 Type of heap Running time
28 ============== =============================================
29 Binary heap $O(n (m + n) \log n)$
30 Fibonacci heap $O(nm + n^2 \log n)$
31 Pairing heap $O(2^{2 \sqrt{\log \log n}} nm + n^2 \log n)$
32 ============== =============================================
34 Parameters
35 ----------
36 G : NetworkX graph
37 Edges of the graph are expected to have an attribute named by the
38 weight parameter below. If this attribute is not present, the edge is
39 considered to have unit weight.
41 weight : string
42 Name of the weight attribute of the edges. If the attribute is not
43 present, unit weight is assumed. Default value: 'weight'.
45 heap : class
46 Type of heap to be used in the algorithm. It should be a subclass of
47 :class:`MinHeap` or implement a compatible interface.
49 If a stock heap implementation is to be used, :class:`BinaryHeap` is
50 recommended over :class:`PairingHeap` for Python implementations without
51 optimized attribute accesses (e.g., CPython) despite a slower
52 asymptotic running time. For Python implementations with optimized
53 attribute accesses (e.g., PyPy), :class:`PairingHeap` provides better
54 performance. Default value: :class:`BinaryHeap`.
56 Returns
57 -------
58 cut_value : integer or float
59 The sum of weights of edges in a minimum cut.
61 partition : pair of node lists
62 A partitioning of the nodes that defines a minimum cut.
64 Raises
65 ------
66 NetworkXNotImplemented
67 If the graph is directed or a multigraph.
69 NetworkXError
70 If the graph has less than two nodes, is not connected or has a
71 negative-weighted edge.
73 Examples
74 --------
75 >>> G = nx.Graph()
76 >>> G.add_edge("x", "a", weight=3)
77 >>> G.add_edge("x", "b", weight=1)
78 >>> G.add_edge("a", "c", weight=3)
79 >>> G.add_edge("b", "c", weight=5)
80 >>> G.add_edge("b", "d", weight=4)
81 >>> G.add_edge("d", "e", weight=2)
82 >>> G.add_edge("c", "y", weight=2)
83 >>> G.add_edge("e", "y", weight=3)
84 >>> cut_value, partition = nx.stoer_wagner(G)
85 >>> cut_value
86 4
87 """
88 n = len(G)
89 if n < 2:
90 raise nx.NetworkXError("graph has less than two nodes.")
91 if not nx.is_connected(G):
92 raise nx.NetworkXError("graph is not connected.")
94 # Make a copy of the graph for internal use.
95 G = nx.Graph(
96 (u, v, {"weight": e.get(weight, 1)}) for u, v, e in G.edges(data=True) if u != v
97 )
98 G.__networkx_cache__ = None # Disable caching
100 for u, v, e in G.edges(data=True):
101 if e["weight"] < 0:
102 raise nx.NetworkXError("graph has a negative-weighted edge.")
104 cut_value = float("inf")
105 nodes = set(G)
106 contractions = [] # contracted node pairs
108 # Repeatedly pick a pair of nodes to contract until only one node is left.
109 for i in range(n - 1):
110 # Pick an arbitrary node u and create a set A = {u}.
111 u = arbitrary_element(G)
112 A = {u}
113 # Repeatedly pick the node "most tightly connected" to A and add it to
114 # A. The tightness of connectivity of a node not in A is defined by the
115 # of edges connecting it to nodes in A.
116 h = heap() # min-heap emulating a max-heap
117 for v, e in G[u].items():
118 h.insert(v, -e["weight"])
119 # Repeat until all but one node has been added to A.
120 for j in range(n - i - 2):
121 u = h.pop()[0]
122 A.add(u)
123 for v, e in G[u].items():
124 if v not in A:
125 h.insert(v, h.get(v, 0) - e["weight"])
126 # A and the remaining node v define a "cut of the phase". There is a
127 # minimum cut of the original graph that is also a cut of the phase.
128 # Due to contractions in earlier phases, v may in fact represent
129 # multiple nodes in the original graph.
130 v, w = h.min()
131 w = -w
132 if w < cut_value:
133 cut_value = w
134 best_phase = i
135 # Contract v and the last node added to A.
136 contractions.append((u, v))
137 for w, e in G[v].items():
138 if w != u:
139 if w not in G[u]:
140 G.add_edge(u, w, weight=e["weight"])
141 else:
142 G[u][w]["weight"] += e["weight"]
143 G.remove_node(v)
145 # Recover the optimal partitioning from the contractions.
146 G = nx.Graph(islice(contractions, best_phase))
147 v = contractions[best_phase][1]
148 G.add_node(v)
149 reachable = set(nx.single_source_shortest_path_length(G, v))
150 partition = (list(reachable), list(nodes - reachable))
152 return cut_value, partition