Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/approximation/connectivity.py: 10%
119 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1""" Fast approximation for node connectivity
2"""
3import itertools
4from operator import itemgetter
6import networkx as nx
8__all__ = [
9 "local_node_connectivity",
10 "node_connectivity",
11 "all_pairs_node_connectivity",
12]
15@nx._dispatch(name="approximate_local_node_connectivity")
16def local_node_connectivity(G, source, target, cutoff=None):
17 """Compute node connectivity between source and target.
19 Pairwise or local node connectivity between two distinct and nonadjacent
20 nodes is the minimum number of nodes that must be removed (minimum
21 separating cutset) to disconnect them. By Menger's theorem, this is equal
22 to the number of node independent paths (paths that share no nodes other
23 than source and target). Which is what we compute in this function.
25 This algorithm is a fast approximation that gives an strict lower
26 bound on the actual number of node independent paths between two nodes [1]_.
27 It works for both directed and undirected graphs.
29 Parameters
30 ----------
32 G : NetworkX graph
34 source : node
35 Starting node for node connectivity
37 target : node
38 Ending node for node connectivity
40 cutoff : integer
41 Maximum node connectivity to consider. If None, the minimum degree
42 of source or target is used as a cutoff. Default value None.
44 Returns
45 -------
46 k: integer
47 pairwise node connectivity
49 Examples
50 --------
51 >>> # Platonic octahedral graph has node connectivity 4
52 >>> # for each non adjacent node pair
53 >>> from networkx.algorithms import approximation as approx
54 >>> G = nx.octahedral_graph()
55 >>> approx.local_node_connectivity(G, 0, 5)
56 4
58 Notes
59 -----
60 This algorithm [1]_ finds node independents paths between two nodes by
61 computing their shortest path using BFS, marking the nodes of the path
62 found as 'used' and then searching other shortest paths excluding the
63 nodes marked as used until no more paths exist. It is not exact because
64 a shortest path could use nodes that, if the path were longer, may belong
65 to two different node independent paths. Thus it only guarantees an
66 strict lower bound on node connectivity.
68 Note that the authors propose a further refinement, losing accuracy and
69 gaining speed, which is not implemented yet.
71 See also
72 --------
73 all_pairs_node_connectivity
74 node_connectivity
76 References
77 ----------
78 .. [1] White, Douglas R., and Mark Newman. 2001 A Fast Algorithm for
79 Node-Independent Paths. Santa Fe Institute Working Paper #01-07-035
80 http://eclectic.ss.uci.edu/~drwhite/working.pdf
82 """
83 if target == source:
84 raise nx.NetworkXError("source and target have to be different nodes.")
86 # Maximum possible node independent paths
87 if G.is_directed():
88 possible = min(G.out_degree(source), G.in_degree(target))
89 else:
90 possible = min(G.degree(source), G.degree(target))
92 K = 0
93 if not possible:
94 return K
96 if cutoff is None:
97 cutoff = float("inf")
99 exclude = set()
100 for i in range(min(possible, cutoff)):
101 try:
102 path = _bidirectional_shortest_path(G, source, target, exclude)
103 exclude.update(set(path))
104 K += 1
105 except nx.NetworkXNoPath:
106 break
108 return K
111@nx._dispatch(name="approximate_node_connectivity")
112def node_connectivity(G, s=None, t=None):
113 r"""Returns an approximation for node connectivity for a graph or digraph G.
115 Node connectivity is equal to the minimum number of nodes that
116 must be removed to disconnect G or render it trivial. By Menger's theorem,
117 this is equal to the number of node independent paths (paths that
118 share no nodes other than source and target).
120 If source and target nodes are provided, this function returns the
121 local node connectivity: the minimum number of nodes that must be
122 removed to break all paths from source to target in G.
124 This algorithm is based on a fast approximation that gives an strict lower
125 bound on the actual number of node independent paths between two nodes [1]_.
126 It works for both directed and undirected graphs.
128 Parameters
129 ----------
130 G : NetworkX graph
131 Undirected graph
133 s : node
134 Source node. Optional. Default value: None.
136 t : node
137 Target node. Optional. Default value: None.
139 Returns
140 -------
141 K : integer
142 Node connectivity of G, or local node connectivity if source
143 and target are provided.
145 Examples
146 --------
147 >>> # Platonic octahedral graph is 4-node-connected
148 >>> from networkx.algorithms import approximation as approx
149 >>> G = nx.octahedral_graph()
150 >>> approx.node_connectivity(G)
151 4
153 Notes
154 -----
155 This algorithm [1]_ finds node independents paths between two nodes by
156 computing their shortest path using BFS, marking the nodes of the path
157 found as 'used' and then searching other shortest paths excluding the
158 nodes marked as used until no more paths exist. It is not exact because
159 a shortest path could use nodes that, if the path were longer, may belong
160 to two different node independent paths. Thus it only guarantees an
161 strict lower bound on node connectivity.
163 See also
164 --------
165 all_pairs_node_connectivity
166 local_node_connectivity
168 References
169 ----------
170 .. [1] White, Douglas R., and Mark Newman. 2001 A Fast Algorithm for
171 Node-Independent Paths. Santa Fe Institute Working Paper #01-07-035
172 http://eclectic.ss.uci.edu/~drwhite/working.pdf
174 """
175 if (s is not None and t is None) or (s is None and t is not None):
176 raise nx.NetworkXError("Both source and target must be specified.")
178 # Local node connectivity
179 if s is not None and t is not None:
180 if s not in G:
181 raise nx.NetworkXError(f"node {s} not in graph")
182 if t not in G:
183 raise nx.NetworkXError(f"node {t} not in graph")
184 return local_node_connectivity(G, s, t)
186 # Global node connectivity
187 if G.is_directed():
188 connected_func = nx.is_weakly_connected
189 iter_func = itertools.permutations
191 def neighbors(v):
192 return itertools.chain(G.predecessors(v), G.successors(v))
194 else:
195 connected_func = nx.is_connected
196 iter_func = itertools.combinations
197 neighbors = G.neighbors
199 if not connected_func(G):
200 return 0
202 # Choose a node with minimum degree
203 v, minimum_degree = min(G.degree(), key=itemgetter(1))
204 # Node connectivity is bounded by minimum degree
205 K = minimum_degree
206 # compute local node connectivity with all non-neighbors nodes
207 # and store the minimum
208 for w in set(G) - set(neighbors(v)) - {v}:
209 K = min(K, local_node_connectivity(G, v, w, cutoff=K))
210 # Same for non adjacent pairs of neighbors of v
211 for x, y in iter_func(neighbors(v), 2):
212 if y not in G[x] and x != y:
213 K = min(K, local_node_connectivity(G, x, y, cutoff=K))
214 return K
217@nx._dispatch(name="approximate_all_pairs_node_connectivity")
218def all_pairs_node_connectivity(G, nbunch=None, cutoff=None):
219 """Compute node connectivity between all pairs of nodes.
221 Pairwise or local node connectivity between two distinct and nonadjacent
222 nodes is the minimum number of nodes that must be removed (minimum
223 separating cutset) to disconnect them. By Menger's theorem, this is equal
224 to the number of node independent paths (paths that share no nodes other
225 than source and target). Which is what we compute in this function.
227 This algorithm is a fast approximation that gives an strict lower
228 bound on the actual number of node independent paths between two nodes [1]_.
229 It works for both directed and undirected graphs.
232 Parameters
233 ----------
234 G : NetworkX graph
236 nbunch: container
237 Container of nodes. If provided node connectivity will be computed
238 only over pairs of nodes in nbunch.
240 cutoff : integer
241 Maximum node connectivity to consider. If None, the minimum degree
242 of source or target is used as a cutoff in each pair of nodes.
243 Default value None.
245 Returns
246 -------
247 K : dictionary
248 Dictionary, keyed by source and target, of pairwise node connectivity
250 Examples
251 --------
252 A 3 node cycle with one extra node attached has connectivity 2 between all
253 nodes in the cycle and connectivity 1 between the extra node and the rest:
255 >>> G = nx.cycle_graph(3)
256 >>> G.add_edge(2, 3)
257 >>> import pprint # for nice dictionary formatting
258 >>> pprint.pprint(nx.all_pairs_node_connectivity(G))
259 {0: {1: 2, 2: 2, 3: 1},
260 1: {0: 2, 2: 2, 3: 1},
261 2: {0: 2, 1: 2, 3: 1},
262 3: {0: 1, 1: 1, 2: 1}}
264 See Also
265 --------
266 local_node_connectivity
267 node_connectivity
269 References
270 ----------
271 .. [1] White, Douglas R., and Mark Newman. 2001 A Fast Algorithm for
272 Node-Independent Paths. Santa Fe Institute Working Paper #01-07-035
273 http://eclectic.ss.uci.edu/~drwhite/working.pdf
274 """
275 if nbunch is None:
276 nbunch = G
277 else:
278 nbunch = set(nbunch)
280 directed = G.is_directed()
281 if directed:
282 iter_func = itertools.permutations
283 else:
284 iter_func = itertools.combinations
286 all_pairs = {n: {} for n in nbunch}
288 for u, v in iter_func(nbunch, 2):
289 k = local_node_connectivity(G, u, v, cutoff=cutoff)
290 all_pairs[u][v] = k
291 if not directed:
292 all_pairs[v][u] = k
294 return all_pairs
297def _bidirectional_shortest_path(G, source, target, exclude):
298 """Returns shortest path between source and target ignoring nodes in the
299 container 'exclude'.
301 Parameters
302 ----------
304 G : NetworkX graph
306 source : node
307 Starting node for path
309 target : node
310 Ending node for path
312 exclude: container
313 Container for nodes to exclude from the search for shortest paths
315 Returns
316 -------
317 path: list
318 Shortest path between source and target ignoring nodes in 'exclude'
320 Raises
321 ------
322 NetworkXNoPath
323 If there is no path or if nodes are adjacent and have only one path
324 between them
326 Notes
327 -----
328 This function and its helper are originally from
329 networkx.algorithms.shortest_paths.unweighted and are modified to
330 accept the extra parameter 'exclude', which is a container for nodes
331 already used in other paths that should be ignored.
333 References
334 ----------
335 .. [1] White, Douglas R., and Mark Newman. 2001 A Fast Algorithm for
336 Node-Independent Paths. Santa Fe Institute Working Paper #01-07-035
337 http://eclectic.ss.uci.edu/~drwhite/working.pdf
339 """
340 # call helper to do the real work
341 results = _bidirectional_pred_succ(G, source, target, exclude)
342 pred, succ, w = results
344 # build path from pred+w+succ
345 path = []
346 # from source to w
347 while w is not None:
348 path.append(w)
349 w = pred[w]
350 path.reverse()
351 # from w to target
352 w = succ[path[-1]]
353 while w is not None:
354 path.append(w)
355 w = succ[w]
357 return path
360def _bidirectional_pred_succ(G, source, target, exclude):
361 # does BFS from both source and target and meets in the middle
362 # excludes nodes in the container "exclude" from the search
364 # handle either directed or undirected
365 if G.is_directed():
366 Gpred = G.predecessors
367 Gsucc = G.successors
368 else:
369 Gpred = G.neighbors
370 Gsucc = G.neighbors
372 # predecessor and successors in search
373 pred = {source: None}
374 succ = {target: None}
376 # initialize fringes, start with forward
377 forward_fringe = [source]
378 reverse_fringe = [target]
380 level = 0
382 while forward_fringe and reverse_fringe:
383 # Make sure that we iterate one step forward and one step backwards
384 # thus source and target will only trigger "found path" when they are
385 # adjacent and then they can be safely included in the container 'exclude'
386 level += 1
387 if level % 2 != 0:
388 this_level = forward_fringe
389 forward_fringe = []
390 for v in this_level:
391 for w in Gsucc(v):
392 if w in exclude:
393 continue
394 if w not in pred:
395 forward_fringe.append(w)
396 pred[w] = v
397 if w in succ:
398 return pred, succ, w # found path
399 else:
400 this_level = reverse_fringe
401 reverse_fringe = []
402 for v in this_level:
403 for w in Gpred(v):
404 if w in exclude:
405 continue
406 if w not in succ:
407 succ[w] = v
408 reverse_fringe.append(w)
409 if w in pred:
410 return pred, succ, w # found path
412 raise nx.NetworkXNoPath(f"No path between {source} and {target}.")