Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/connectivity/stoerwagner.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 """ | |
2 Stoer-Wagner minimum cut algorithm. | |
3 """ | |
4 from itertools import islice | |
5 | |
6 import networkx as nx | |
7 from ...utils import BinaryHeap | |
8 from ...utils import not_implemented_for | |
9 from ...utils import arbitrary_element | |
10 | |
11 __all__ = ["stoer_wagner"] | |
12 | |
13 | |
14 @not_implemented_for("directed") | |
15 @not_implemented_for("multigraph") | |
16 def stoer_wagner(G, weight="weight", heap=BinaryHeap): | |
17 r"""Returns the weighted minimum edge cut using the Stoer-Wagner algorithm. | |
18 | |
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. | |
22 | |
23 The running time of the algorithm depends on the type of heaps used: | |
24 | |
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 ============== ============================================= | |
32 | |
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. | |
39 | |
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'. | |
43 | |
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. | |
47 | |
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`. | |
54 | |
55 Returns | |
56 ------- | |
57 cut_value : integer or float | |
58 The sum of weights of edges in a minimum cut. | |
59 | |
60 partition : pair of node lists | |
61 A partitioning of the nodes that defines a minimum cut. | |
62 | |
63 Raises | |
64 ------ | |
65 NetworkXNotImplemented | |
66 If the graph is directed or a multigraph. | |
67 | |
68 NetworkXError | |
69 If the graph has less than two nodes, is not connected or has a | |
70 negative-weighted edge. | |
71 | |
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.") | |
92 | |
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 ) | |
97 | |
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.") | |
101 | |
102 cut_value = float("inf") | |
103 nodes = set(G) | |
104 contractions = [] # contracted node pairs | |
105 | |
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) | |
142 | |
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)) | |
149 | |
150 return cut_value, partition |