Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/connectivity/kcutsets.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 Kanevsky all minimum node k cutsets algorithm. | |
3 """ | |
4 import copy | |
5 from collections import defaultdict | |
6 from itertools import combinations | |
7 from operator import itemgetter | |
8 | |
9 import networkx as nx | |
10 from .utils import build_auxiliary_node_connectivity | |
11 from networkx.algorithms.flow import ( | |
12 build_residual_network, | |
13 edmonds_karp, | |
14 shortest_augmenting_path, | |
15 ) | |
16 | |
17 default_flow_func = edmonds_karp | |
18 | |
19 | |
20 __all__ = ["all_node_cuts"] | |
21 | |
22 | |
23 def all_node_cuts(G, k=None, flow_func=None): | |
24 r"""Returns all minimum k cutsets of an undirected graph G. | |
25 | |
26 This implementation is based on Kanevsky's algorithm [1]_ for finding all | |
27 minimum-size node cut-sets of an undirected graph G; ie the set (or sets) | |
28 of nodes of cardinality equal to the node connectivity of G. Thus if | |
29 removed, would break G into two or more connected components. | |
30 | |
31 Parameters | |
32 ---------- | |
33 G : NetworkX graph | |
34 Undirected graph | |
35 | |
36 k : Integer | |
37 Node connectivity of the input graph. If k is None, then it is | |
38 computed. Default value: None. | |
39 | |
40 flow_func : function | |
41 Function to perform the underlying flow computations. Default value | |
42 edmonds_karp. This function performs better in sparse graphs with | |
43 right tailed degree distributions. shortest_augmenting_path will | |
44 perform better in denser graphs. | |
45 | |
46 | |
47 Returns | |
48 ------- | |
49 cuts : a generator of node cutsets | |
50 Each node cutset has cardinality equal to the node connectivity of | |
51 the input graph. | |
52 | |
53 Examples | |
54 -------- | |
55 >>> # A two-dimensional grid graph has 4 cutsets of cardinality 2 | |
56 >>> G = nx.grid_2d_graph(5, 5) | |
57 >>> cutsets = list(nx.all_node_cuts(G)) | |
58 >>> len(cutsets) | |
59 4 | |
60 >>> all(2 == len(cutset) for cutset in cutsets) | |
61 True | |
62 >>> nx.node_connectivity(G) | |
63 2 | |
64 | |
65 Notes | |
66 ----- | |
67 This implementation is based on the sequential algorithm for finding all | |
68 minimum-size separating vertex sets in a graph [1]_. The main idea is to | |
69 compute minimum cuts using local maximum flow computations among a set | |
70 of nodes of highest degree and all other non-adjacent nodes in the Graph. | |
71 Once we find a minimum cut, we add an edge between the high degree | |
72 node and the target node of the local maximum flow computation to make | |
73 sure that we will not find that minimum cut again. | |
74 | |
75 See also | |
76 -------- | |
77 node_connectivity | |
78 edmonds_karp | |
79 shortest_augmenting_path | |
80 | |
81 References | |
82 ---------- | |
83 .. [1] Kanevsky, A. (1993). Finding all minimum-size separating vertex | |
84 sets in a graph. Networks 23(6), 533--541. | |
85 http://onlinelibrary.wiley.com/doi/10.1002/net.3230230604/abstract | |
86 | |
87 """ | |
88 if not nx.is_connected(G): | |
89 raise nx.NetworkXError("Input graph is disconnected.") | |
90 | |
91 # Address some corner cases first. | |
92 # For complete Graphs | |
93 if nx.density(G) == 1: | |
94 for cut_set in combinations(G, len(G) - 1): | |
95 yield set(cut_set) | |
96 return | |
97 # Initialize data structures. | |
98 # Keep track of the cuts already computed so we do not repeat them. | |
99 seen = [] | |
100 # Even-Tarjan reduction is what we call auxiliary digraph | |
101 # for node connectivity. | |
102 H = build_auxiliary_node_connectivity(G) | |
103 H_nodes = H.nodes # for speed | |
104 mapping = H.graph["mapping"] | |
105 # Keep a copy of original predecessors, H will be modified later. | |
106 # Shallow copy is enough. | |
107 original_H_pred = copy.copy(H._pred) | |
108 R = build_residual_network(H, "capacity") | |
109 kwargs = dict(capacity="capacity", residual=R) | |
110 # Define default flow function | |
111 if flow_func is None: | |
112 flow_func = default_flow_func | |
113 if flow_func is shortest_augmenting_path: | |
114 kwargs["two_phase"] = True | |
115 # Begin the actual algorithm | |
116 # step 1: Find node connectivity k of G | |
117 if k is None: | |
118 k = nx.node_connectivity(G, flow_func=flow_func) | |
119 # step 2: | |
120 # Find k nodes with top degree, call it X: | |
121 X = {n for n, d in sorted(G.degree(), key=itemgetter(1), reverse=True)[:k]} | |
122 # Check if X is a k-node-cutset | |
123 if _is_separating_set(G, X): | |
124 seen.append(X) | |
125 yield X | |
126 | |
127 for x in X: | |
128 # step 3: Compute local connectivity flow of x with all other | |
129 # non adjacent nodes in G | |
130 non_adjacent = set(G) - X - set(G[x]) | |
131 for v in non_adjacent: | |
132 # step 4: compute maximum flow in an Even-Tarjan reduction H of G | |
133 # and step 5: build the associated residual network R | |
134 R = flow_func(H, f"{mapping[x]}B", f"{mapping[v]}A", **kwargs) | |
135 flow_value = R.graph["flow_value"] | |
136 | |
137 if flow_value == k: | |
138 # Find the nodes incident to the flow. | |
139 E1 = flowed_edges = [ | |
140 (u, w) for (u, w, d) in R.edges(data=True) if d["flow"] != 0 | |
141 ] | |
142 VE1 = incident_nodes = {n for edge in E1 for n in edge} | |
143 # Remove saturated edges form the residual network. | |
144 # Note that reversed edges are introduced with capacity 0 | |
145 # in the residual graph and they need to be removed too. | |
146 saturated_edges = [ | |
147 (u, w, d) | |
148 for (u, w, d) in R.edges(data=True) | |
149 if d["capacity"] == d["flow"] or d["capacity"] == 0 | |
150 ] | |
151 R.remove_edges_from(saturated_edges) | |
152 R_closure = nx.transitive_closure(R) | |
153 # step 6: shrink the strongly connected components of | |
154 # residual flow network R and call it L. | |
155 L = nx.condensation(R) | |
156 cmap = L.graph["mapping"] | |
157 inv_cmap = defaultdict(list) | |
158 for n, scc in cmap.items(): | |
159 inv_cmap[scc].append(n) | |
160 # Find the incident nodes in the condensed graph. | |
161 VE1 = {cmap[n] for n in VE1} | |
162 # step 7: Compute all antichains of L; | |
163 # they map to closed sets in H. | |
164 # Any edge in H that links a closed set is part of a cutset. | |
165 for antichain in nx.antichains(L): | |
166 # Only antichains that are subsets of incident nodes counts. | |
167 # Lemma 8 in reference. | |
168 if not set(antichain).issubset(VE1): | |
169 continue | |
170 # Nodes in an antichain of the condensation graph of | |
171 # the residual network map to a closed set of nodes that | |
172 # define a node partition of the auxiliary digraph H | |
173 # through taking all of antichain's predecessors in the | |
174 # transitive closure. | |
175 S = set() | |
176 for scc in antichain: | |
177 S.update(inv_cmap[scc]) | |
178 S_ancestors = set() | |
179 for n in S: | |
180 S_ancestors.update(R_closure._pred[n]) | |
181 S.update(S_ancestors) | |
182 if f"{mapping[x]}B" not in S or f"{mapping[v]}A" in S: | |
183 continue | |
184 # Find the cutset that links the node partition (S,~S) in H | |
185 cutset = set() | |
186 for u in S: | |
187 cutset.update((u, w) for w in original_H_pred[u] if w not in S) | |
188 # The edges in H that form the cutset are internal edges | |
189 # (ie edges that represent a node of the original graph G) | |
190 if any([H_nodes[u]["id"] != H_nodes[w]["id"] for u, w in cutset]): | |
191 continue | |
192 node_cut = {H_nodes[u]["id"] for u, _ in cutset} | |
193 | |
194 if len(node_cut) == k: | |
195 # The cut is invalid if it includes internal edges of | |
196 # end nodes. The other half of Lemma 8 in ref. | |
197 if x in node_cut or v in node_cut: | |
198 continue | |
199 if node_cut not in seen: | |
200 yield node_cut | |
201 seen.append(node_cut) | |
202 | |
203 # Add an edge (x, v) to make sure that we do not | |
204 # find this cutset again. This is equivalent | |
205 # of adding the edge in the input graph | |
206 # G.add_edge(x, v) and then regenerate H and R: | |
207 # Add edges to the auxiliary digraph. | |
208 # See build_residual_network for convention we used | |
209 # in residual graphs. | |
210 H.add_edge(f"{mapping[x]}B", f"{mapping[v]}A", capacity=1) | |
211 H.add_edge(f"{mapping[v]}B", f"{mapping[x]}A", capacity=1) | |
212 # Add edges to the residual network. | |
213 R.add_edge(f"{mapping[x]}B", f"{mapping[v]}A", capacity=1) | |
214 R.add_edge(f"{mapping[v]}A", f"{mapping[x]}B", capacity=0) | |
215 R.add_edge(f"{mapping[v]}B", f"{mapping[x]}A", capacity=1) | |
216 R.add_edge(f"{mapping[x]}A", f"{mapping[v]}B", capacity=0) | |
217 | |
218 # Add again the saturated edges to reuse the residual network | |
219 R.add_edges_from(saturated_edges) | |
220 | |
221 | |
222 def _is_separating_set(G, cut): | |
223 """Assumes that the input graph is connected""" | |
224 if len(cut) == len(G) - 1: | |
225 return True | |
226 | |
227 H = nx.restricted_view(G, cut, []) | |
228 if nx.is_connected(H): | |
229 return False | |
230 return True |