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