Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/connectivity/edge_augmentation.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 Algorithms for finding k-edge-augmentations | |
3 | |
4 A k-edge-augmentation is a set of edges, that once added to a graph, ensures | |
5 that the graph is k-edge-connected; i.e. the graph cannot be disconnected | |
6 unless k or more edges are removed. Typically, the goal is to find the | |
7 augmentation with minimum weight. In general, it is not guaranteed that a | |
8 k-edge-augmentation exists. | |
9 | |
10 See Also | |
11 -------- | |
12 :mod:`edge_kcomponents` : algorithms for finding k-edge-connected components | |
13 :mod:`connectivity` : algorithms for determening edge connectivity. | |
14 """ | |
15 import math | |
16 import itertools as it | |
17 import networkx as nx | |
18 from networkx.utils import not_implemented_for, py_random_state | |
19 from collections import defaultdict, namedtuple | |
20 | |
21 __all__ = ["k_edge_augmentation", "is_k_edge_connected", "is_locally_k_edge_connected"] | |
22 | |
23 | |
24 @not_implemented_for("directed") | |
25 @not_implemented_for("multigraph") | |
26 def is_k_edge_connected(G, k): | |
27 """Tests to see if a graph is k-edge-connected. | |
28 | |
29 Is it impossible to disconnect the graph by removing fewer than k edges? | |
30 If so, then G is k-edge-connected. | |
31 | |
32 Parameters | |
33 ---------- | |
34 G : NetworkX graph | |
35 An undirected graph. | |
36 | |
37 k : integer | |
38 edge connectivity to test for | |
39 | |
40 Returns | |
41 ------- | |
42 boolean | |
43 True if G is k-edge-connected. | |
44 | |
45 See Also | |
46 -------- | |
47 :func:`is_locally_k_edge_connected` | |
48 | |
49 Example | |
50 ------- | |
51 >>> G = nx.barbell_graph(10, 0) | |
52 >>> nx.is_k_edge_connected(G, k=1) | |
53 True | |
54 >>> nx.is_k_edge_connected(G, k=2) | |
55 False | |
56 """ | |
57 if k < 1: | |
58 raise ValueError(f"k must be positive, not {k}") | |
59 # First try to quickly determine if G is not k-edge-connected | |
60 if G.number_of_nodes() < k + 1: | |
61 return False | |
62 elif any(d < k for n, d in G.degree()): | |
63 return False | |
64 else: | |
65 # Otherwise perform the full check | |
66 if k == 1: | |
67 return nx.is_connected(G) | |
68 elif k == 2: | |
69 return not nx.has_bridges(G) | |
70 else: | |
71 return nx.edge_connectivity(G, cutoff=k) >= k | |
72 | |
73 | |
74 @not_implemented_for("directed") | |
75 @not_implemented_for("multigraph") | |
76 def is_locally_k_edge_connected(G, s, t, k): | |
77 """Tests to see if an edge in a graph is locally k-edge-connected. | |
78 | |
79 Is it impossible to disconnect s and t by removing fewer than k edges? | |
80 If so, then s and t are locally k-edge-connected in G. | |
81 | |
82 Parameters | |
83 ---------- | |
84 G : NetworkX graph | |
85 An undirected graph. | |
86 | |
87 s : node | |
88 Source node | |
89 | |
90 t : node | |
91 Target node | |
92 | |
93 k : integer | |
94 local edge connectivity for nodes s and t | |
95 | |
96 Returns | |
97 ------- | |
98 boolean | |
99 True if s and t are locally k-edge-connected in G. | |
100 | |
101 See Also | |
102 -------- | |
103 :func:`is_k_edge_connected` | |
104 | |
105 Example | |
106 ------- | |
107 >>> from networkx.algorithms.connectivity import is_locally_k_edge_connected | |
108 >>> G = nx.barbell_graph(10, 0) | |
109 >>> is_locally_k_edge_connected(G, 5, 15, k=1) | |
110 True | |
111 >>> is_locally_k_edge_connected(G, 5, 15, k=2) | |
112 False | |
113 >>> is_locally_k_edge_connected(G, 1, 5, k=2) | |
114 True | |
115 """ | |
116 if k < 1: | |
117 raise ValueError(f"k must be positive, not {k}") | |
118 | |
119 # First try to quickly determine s, t is not k-locally-edge-connected in G | |
120 if G.degree(s) < k or G.degree(t) < k: | |
121 return False | |
122 else: | |
123 # Otherwise perform the full check | |
124 if k == 1: | |
125 return nx.has_path(G, s, t) | |
126 else: | |
127 localk = nx.connectivity.local_edge_connectivity(G, s, t, cutoff=k) | |
128 return localk >= k | |
129 | |
130 | |
131 @not_implemented_for("directed") | |
132 @not_implemented_for("multigraph") | |
133 def k_edge_augmentation(G, k, avail=None, weight=None, partial=False): | |
134 """Finds set of edges to k-edge-connect G. | |
135 | |
136 Adding edges from the augmentation to G make it impossible to disconnect G | |
137 unless k or more edges are removed. This function uses the most efficient | |
138 function available (depending on the value of k and if the problem is | |
139 weighted or unweighted) to search for a minimum weight subset of available | |
140 edges that k-edge-connects G. In general, finding a k-edge-augmentation is | |
141 NP-hard, so solutions are not garuenteed to be minimal. Furthermore, a | |
142 k-edge-augmentation may not exist. | |
143 | |
144 Parameters | |
145 ---------- | |
146 G : NetworkX graph | |
147 An undirected graph. | |
148 | |
149 k : integer | |
150 Desired edge connectivity | |
151 | |
152 avail : dict or a set of 2 or 3 tuples | |
153 The available edges that can be used in the augmentation. | |
154 | |
155 If unspecified, then all edges in the complement of G are available. | |
156 Otherwise, each item is an available edge (with an optional weight). | |
157 | |
158 In the unweighted case, each item is an edge ``(u, v)``. | |
159 | |
160 In the weighted case, each item is a 3-tuple ``(u, v, d)`` or a dict | |
161 with items ``(u, v): d``. The third item, ``d``, can be a dictionary | |
162 or a real number. If ``d`` is a dictionary ``d[weight]`` | |
163 correspondings to the weight. | |
164 | |
165 weight : string | |
166 key to use to find weights if ``avail`` is a set of 3-tuples where the | |
167 third item in each tuple is a dictionary. | |
168 | |
169 partial : boolean | |
170 If partial is True and no feasible k-edge-augmentation exists, then all | |
171 a partial k-edge-augmentation is generated. Adding the edges in a | |
172 partial augmentation to G, minimizes the number of k-edge-connected | |
173 components and maximizes the edge connectivity between those | |
174 components. For details, see :func:`partial_k_edge_augmentation`. | |
175 | |
176 Yields | |
177 ------ | |
178 edge : tuple | |
179 Edges that, once added to G, would cause G to become k-edge-connected. | |
180 If partial is False, an error is raised if this is not possible. | |
181 Otherwise, generated edges form a partial augmentation, which | |
182 k-edge-connects any part of G where it is possible, and maximally | |
183 connects the remaining parts. | |
184 | |
185 Raises | |
186 ------ | |
187 NetworkXUnfeasible | |
188 If partial is False and no k-edge-augmentation exists. | |
189 | |
190 NetworkXNotImplemented | |
191 If the input graph is directed or a multigraph. | |
192 | |
193 ValueError: | |
194 If k is less than 1 | |
195 | |
196 Notes | |
197 ----- | |
198 When k=1 this returns an optimal solution. | |
199 | |
200 When k=2 and ``avail`` is None, this returns an optimal solution. | |
201 Otherwise when k=2, this returns a 2-approximation of the optimal solution. | |
202 | |
203 For k>3, this problem is NP-hard and this uses a randomized algorithm that | |
204 produces a feasible solution, but provides no guarantees on the | |
205 solution weight. | |
206 | |
207 Example | |
208 ------- | |
209 >>> # Unweighted cases | |
210 >>> G = nx.path_graph((1, 2, 3, 4)) | |
211 >>> G.add_node(5) | |
212 >>> sorted(nx.k_edge_augmentation(G, k=1)) | |
213 [(1, 5)] | |
214 >>> sorted(nx.k_edge_augmentation(G, k=2)) | |
215 [(1, 5), (5, 4)] | |
216 >>> sorted(nx.k_edge_augmentation(G, k=3)) | |
217 [(1, 4), (1, 5), (2, 5), (3, 5), (4, 5)] | |
218 >>> complement = list(nx.k_edge_augmentation(G, k=5, partial=True)) | |
219 >>> G.add_edges_from(complement) | |
220 >>> nx.edge_connectivity(G) | |
221 4 | |
222 | |
223 Example | |
224 ------- | |
225 >>> # Weighted cases | |
226 >>> G = nx.path_graph((1, 2, 3, 4)) | |
227 >>> G.add_node(5) | |
228 >>> # avail can be a tuple with a dict | |
229 >>> avail = [(1, 5, {"weight": 11}), (2, 5, {"weight": 10})] | |
230 >>> sorted(nx.k_edge_augmentation(G, k=1, avail=avail, weight="weight")) | |
231 [(2, 5)] | |
232 >>> # or avail can be a 3-tuple with a real number | |
233 >>> avail = [(1, 5, 11), (2, 5, 10), (4, 3, 1), (4, 5, 51)] | |
234 >>> sorted(nx.k_edge_augmentation(G, k=2, avail=avail)) | |
235 [(1, 5), (2, 5), (4, 5)] | |
236 >>> # or avail can be a dict | |
237 >>> avail = {(1, 5): 11, (2, 5): 10, (4, 3): 1, (4, 5): 51} | |
238 >>> sorted(nx.k_edge_augmentation(G, k=2, avail=avail)) | |
239 [(1, 5), (2, 5), (4, 5)] | |
240 >>> # If augmentation is infeasible, then a partial solution can be found | |
241 >>> avail = {(1, 5): 11} | |
242 >>> sorted(nx.k_edge_augmentation(G, k=2, avail=avail, partial=True)) | |
243 [(1, 5)] | |
244 """ | |
245 try: | |
246 if k <= 0: | |
247 raise ValueError(f"k must be a positive integer, not {k}") | |
248 elif G.number_of_nodes() < k + 1: | |
249 msg = f"impossible to {k} connect in graph with less than {k + 1} nodes" | |
250 raise nx.NetworkXUnfeasible(msg) | |
251 elif avail is not None and len(avail) == 0: | |
252 if not nx.is_k_edge_connected(G, k): | |
253 raise nx.NetworkXUnfeasible("no available edges") | |
254 aug_edges = [] | |
255 elif k == 1: | |
256 aug_edges = one_edge_augmentation( | |
257 G, avail=avail, weight=weight, partial=partial | |
258 ) | |
259 elif k == 2: | |
260 aug_edges = bridge_augmentation(G, avail=avail, weight=weight) | |
261 else: | |
262 # raise NotImplementedError(f'not implemented for k>2. k={k}') | |
263 aug_edges = greedy_k_edge_augmentation( | |
264 G, k=k, avail=avail, weight=weight, seed=0 | |
265 ) | |
266 # Do eager evaulation so we can catch any exceptions | |
267 # Before executing partial code. | |
268 yield from list(aug_edges) | |
269 except nx.NetworkXUnfeasible: | |
270 if partial: | |
271 # Return all available edges | |
272 if avail is None: | |
273 aug_edges = complement_edges(G) | |
274 else: | |
275 # If we can't k-edge-connect the entire graph, try to | |
276 # k-edge-connect as much as possible | |
277 aug_edges = partial_k_edge_augmentation( | |
278 G, k=k, avail=avail, weight=weight | |
279 ) | |
280 yield from aug_edges | |
281 else: | |
282 raise | |
283 | |
284 | |
285 def partial_k_edge_augmentation(G, k, avail, weight=None): | |
286 """Finds augmentation that k-edge-connects as much of the graph as possible. | |
287 | |
288 When a k-edge-augmentation is not possible, we can still try to find a | |
289 small set of edges that partially k-edge-connects as much of the graph as | |
290 possible. All possible edges are generated between remaining parts. | |
291 This minimizes the number of k-edge-connected subgraphs in the resulting | |
292 graph and maxmizes the edge connectivity between those subgraphs. | |
293 | |
294 Parameters | |
295 ---------- | |
296 G : NetworkX graph | |
297 An undirected graph. | |
298 | |
299 k : integer | |
300 Desired edge connectivity | |
301 | |
302 avail : dict or a set of 2 or 3 tuples | |
303 For more details, see :func:`k_edge_augmentation`. | |
304 | |
305 weight : string | |
306 key to use to find weights if ``avail`` is a set of 3-tuples. | |
307 For more details, see :func:`k_edge_augmentation`. | |
308 | |
309 Yields | |
310 ------ | |
311 edge : tuple | |
312 Edges in the partial augmentation of G. These edges k-edge-connect any | |
313 part of G where it is possible, and maximally connects the remaining | |
314 parts. In other words, all edges from avail are generated except for | |
315 those within subgraphs that have already become k-edge-connected. | |
316 | |
317 Notes | |
318 ----- | |
319 Construct H that augments G with all edges in avail. | |
320 Find the k-edge-subgraphs of H. | |
321 For each k-edge-subgraph, if the number of nodes is more than k, then find | |
322 the k-edge-augmentation of that graph and add it to the solution. Then add | |
323 all edges in avail between k-edge subgraphs to the solution. | |
324 | |
325 See Also | |
326 -------- | |
327 :func:`k_edge_augmentation` | |
328 | |
329 Example | |
330 ------- | |
331 >>> G = nx.path_graph((1, 2, 3, 4, 5, 6, 7)) | |
332 >>> G.add_node(8) | |
333 >>> avail = [(1, 3), (1, 4), (1, 5), (2, 4), (2, 5), (3, 5), (1, 8)] | |
334 >>> sorted(partial_k_edge_augmentation(G, k=2, avail=avail)) | |
335 [(1, 5), (1, 8)] | |
336 """ | |
337 | |
338 def _edges_between_disjoint(H, only1, only2): | |
339 """ finds edges between disjoint nodes """ | |
340 only1_adj = {u: set(H.adj[u]) for u in only1} | |
341 for u, neighbs in only1_adj.items(): | |
342 # Find the neighbors of u in only1 that are also in only2 | |
343 neighbs12 = neighbs.intersection(only2) | |
344 for v in neighbs12: | |
345 yield (u, v) | |
346 | |
347 avail_uv, avail_w = _unpack_available_edges(avail, weight=weight, G=G) | |
348 | |
349 # Find which parts of the graph can be k-edge-connected | |
350 H = G.copy() | |
351 H.add_edges_from( | |
352 ( | |
353 (u, v, {"weight": w, "generator": (u, v)}) | |
354 for (u, v), w in zip(avail, avail_w) | |
355 ) | |
356 ) | |
357 k_edge_subgraphs = list(nx.k_edge_subgraphs(H, k=k)) | |
358 | |
359 # Generate edges to k-edge-connect internal subgraphs | |
360 for nodes in k_edge_subgraphs: | |
361 if len(nodes) > 1: | |
362 # Get the k-edge-connected subgraph | |
363 C = H.subgraph(nodes).copy() | |
364 # Find the internal edges that were available | |
365 sub_avail = { | |
366 d["generator"]: d["weight"] | |
367 for (u, v, d) in C.edges(data=True) | |
368 if "generator" in d | |
369 } | |
370 # Remove potential augmenting edges | |
371 C.remove_edges_from(sub_avail.keys()) | |
372 # Find a subset of these edges that makes the compoment | |
373 # k-edge-connected and ignore the rest | |
374 yield from nx.k_edge_augmentation(C, k=k, avail=sub_avail) | |
375 | |
376 # Generate all edges between CCs that could not be k-edge-connected | |
377 for cc1, cc2 in it.combinations(k_edge_subgraphs, 2): | |
378 for (u, v) in _edges_between_disjoint(H, cc1, cc2): | |
379 d = H.get_edge_data(u, v) | |
380 edge = d.get("generator", None) | |
381 if edge is not None: | |
382 yield edge | |
383 | |
384 | |
385 @not_implemented_for("multigraph") | |
386 @not_implemented_for("directed") | |
387 def one_edge_augmentation(G, avail=None, weight=None, partial=False): | |
388 """Finds minimum weight set of edges to connect G. | |
389 | |
390 Equivalent to :func:`k_edge_augmentation` when k=1. Adding the resulting | |
391 edges to G will make it 1-edge-connected. The solution is optimal for both | |
392 weighted and non-weighted variants. | |
393 | |
394 Parameters | |
395 ---------- | |
396 G : NetworkX graph | |
397 An undirected graph. | |
398 | |
399 avail : dict or a set of 2 or 3 tuples | |
400 For more details, see :func:`k_edge_augmentation`. | |
401 | |
402 weight : string | |
403 key to use to find weights if ``avail`` is a set of 3-tuples. | |
404 For more details, see :func:`k_edge_augmentation`. | |
405 | |
406 partial : boolean | |
407 If partial is True and no feasible k-edge-augmentation exists, then the | |
408 augmenting edges minimize the number of connected components. | |
409 | |
410 Yields | |
411 ------ | |
412 edge : tuple | |
413 Edges in the one-augmentation of G | |
414 | |
415 Raises | |
416 ------ | |
417 NetworkXUnfeasible | |
418 If partial is False and no one-edge-augmentation exists. | |
419 | |
420 Notes | |
421 ----- | |
422 Uses either :func:`unconstrained_one_edge_augmentation` or | |
423 :func:`weighted_one_edge_augmentation` depending on whether ``avail`` is | |
424 specified. Both algorithms are based on finding a minimum spanning tree. | |
425 As such both algorithms find optimal solutions and run in linear time. | |
426 | |
427 See Also | |
428 -------- | |
429 :func:`k_edge_augmentation` | |
430 """ | |
431 if avail is None: | |
432 return unconstrained_one_edge_augmentation(G) | |
433 else: | |
434 return weighted_one_edge_augmentation( | |
435 G, avail=avail, weight=weight, partial=partial | |
436 ) | |
437 | |
438 | |
439 @not_implemented_for("multigraph") | |
440 @not_implemented_for("directed") | |
441 def bridge_augmentation(G, avail=None, weight=None): | |
442 """Finds the a set of edges that bridge connects G. | |
443 | |
444 Equivalent to :func:`k_edge_augmentation` when k=2, and partial=False. | |
445 Adding the resulting edges to G will make it 2-edge-connected. If no | |
446 constraints are specified the returned set of edges is minimum an optimal, | |
447 otherwise the solution is approximated. | |
448 | |
449 Parameters | |
450 ---------- | |
451 G : NetworkX graph | |
452 An undirected graph. | |
453 | |
454 avail : dict or a set of 2 or 3 tuples | |
455 For more details, see :func:`k_edge_augmentation`. | |
456 | |
457 weight : string | |
458 key to use to find weights if ``avail`` is a set of 3-tuples. | |
459 For more details, see :func:`k_edge_augmentation`. | |
460 | |
461 Yields | |
462 ------ | |
463 edge : tuple | |
464 Edges in the bridge-augmentation of G | |
465 | |
466 Raises | |
467 ------ | |
468 NetworkXUnfeasible | |
469 If no bridge-augmentation exists. | |
470 | |
471 Notes | |
472 ----- | |
473 If there are no constraints the solution can be computed in linear time | |
474 using :func:`unconstrained_bridge_augmentation`. Otherwise, the problem | |
475 becomes NP-hard and is the solution is approximated by | |
476 :func:`weighted_bridge_augmentation`. | |
477 | |
478 See Also | |
479 -------- | |
480 :func:`k_edge_augmentation` | |
481 """ | |
482 if G.number_of_nodes() < 3: | |
483 raise nx.NetworkXUnfeasible("impossible to bridge connect less than 3 nodes") | |
484 if avail is None: | |
485 return unconstrained_bridge_augmentation(G) | |
486 else: | |
487 return weighted_bridge_augmentation(G, avail, weight=weight) | |
488 | |
489 | |
490 # --- Algorithms and Helpers --- | |
491 | |
492 | |
493 def _ordered(u, v): | |
494 """Returns the nodes in an undirected edge in lower-triangular order""" | |
495 return (u, v) if u < v else (v, u) | |
496 | |
497 | |
498 def _unpack_available_edges(avail, weight=None, G=None): | |
499 """Helper to separate avail into edges and corresponding weights""" | |
500 if weight is None: | |
501 weight = "weight" | |
502 if isinstance(avail, dict): | |
503 avail_uv = list(avail.keys()) | |
504 avail_w = list(avail.values()) | |
505 else: | |
506 | |
507 def _try_getitem(d): | |
508 try: | |
509 return d[weight] | |
510 except TypeError: | |
511 return d | |
512 | |
513 avail_uv = [tup[0:2] for tup in avail] | |
514 avail_w = [1 if len(tup) == 2 else _try_getitem(tup[-1]) for tup in avail] | |
515 | |
516 if G is not None: | |
517 # Edges already in the graph are filtered | |
518 flags = [not G.has_edge(u, v) for u, v in avail_uv] | |
519 avail_uv = list(it.compress(avail_uv, flags)) | |
520 avail_w = list(it.compress(avail_w, flags)) | |
521 return avail_uv, avail_w | |
522 | |
523 | |
524 MetaEdge = namedtuple("MetaEdge", ("meta_uv", "uv", "w")) | |
525 | |
526 | |
527 def _lightest_meta_edges(mapping, avail_uv, avail_w): | |
528 """Maps available edges in the original graph to edges in the metagraph. | |
529 | |
530 Parameters | |
531 ---------- | |
532 mapping : dict | |
533 mapping produced by :func:`collapse`, that maps each node in the | |
534 original graph to a node in the meta graph | |
535 | |
536 avail_uv : list | |
537 list of edges | |
538 | |
539 avail_w : list | |
540 list of edge weights | |
541 | |
542 Notes | |
543 ----- | |
544 Each node in the metagraph is a k-edge-connected component in the original | |
545 graph. We don't care about any edge within the same k-edge-connected | |
546 component, so we ignore self edges. We also are only intereseted in the | |
547 minimum weight edge bridging each k-edge-connected component so, we group | |
548 the edges by meta-edge and take the lightest in each group. | |
549 | |
550 Example | |
551 ------- | |
552 >>> # Each group represents a meta-node | |
553 >>> groups = ([1, 2, 3], [4, 5], [6]) | |
554 >>> mapping = {n: meta_n for meta_n, ns in enumerate(groups) for n in ns} | |
555 >>> avail_uv = [(1, 2), (3, 6), (1, 4), (5, 2), (6, 1), (2, 6), (3, 1)] | |
556 >>> avail_w = [20, 99, 20, 15, 50, 99, 20] | |
557 >>> sorted(_lightest_meta_edges(mapping, avail_uv, avail_w)) | |
558 [MetaEdge(meta_uv=(0, 1), uv=(5, 2), w=15), MetaEdge(meta_uv=(0, 2), uv=(6, 1), w=50)] | |
559 """ | |
560 grouped_wuv = defaultdict(list) | |
561 for w, (u, v) in zip(avail_w, avail_uv): | |
562 # Order the meta-edge so it can be used as a dict key | |
563 meta_uv = _ordered(mapping[u], mapping[v]) | |
564 # Group each available edge using the meta-edge as a key | |
565 grouped_wuv[meta_uv].append((w, u, v)) | |
566 | |
567 # Now that all available edges are grouped, choose one per group | |
568 for (mu, mv), choices_wuv in grouped_wuv.items(): | |
569 # Ignore available edges within the same meta-node | |
570 if mu != mv: | |
571 # Choose the lightest available edge belonging to each meta-edge | |
572 w, u, v = min(choices_wuv) | |
573 yield MetaEdge((mu, mv), (u, v), w) | |
574 | |
575 | |
576 def unconstrained_one_edge_augmentation(G): | |
577 """Finds the smallest set of edges to connect G. | |
578 | |
579 This is a variant of the unweighted MST problem. | |
580 If G is not empty, a feasible solution always exists. | |
581 | |
582 Parameters | |
583 ---------- | |
584 G : NetworkX graph | |
585 An undirected graph. | |
586 | |
587 Yields | |
588 ------ | |
589 edge : tuple | |
590 Edges in the one-edge-augmentation of G | |
591 | |
592 See Also | |
593 -------- | |
594 :func:`one_edge_augmentation` | |
595 :func:`k_edge_augmentation` | |
596 | |
597 Example | |
598 ------- | |
599 >>> G = nx.Graph([(1, 2), (2, 3), (4, 5)]) | |
600 >>> G.add_nodes_from([6, 7, 8]) | |
601 >>> sorted(unconstrained_one_edge_augmentation(G)) | |
602 [(1, 4), (4, 6), (6, 7), (7, 8)] | |
603 """ | |
604 ccs1 = list(nx.connected_components(G)) | |
605 C = collapse(G, ccs1) | |
606 # When we are not constrained, we can just make a meta graph tree. | |
607 meta_nodes = list(C.nodes()) | |
608 # build a path in the metagraph | |
609 meta_aug = list(zip(meta_nodes, meta_nodes[1:])) | |
610 # map that path to the original graph | |
611 inverse = defaultdict(list) | |
612 for k, v in C.graph["mapping"].items(): | |
613 inverse[v].append(k) | |
614 for mu, mv in meta_aug: | |
615 yield (inverse[mu][0], inverse[mv][0]) | |
616 | |
617 | |
618 def weighted_one_edge_augmentation(G, avail, weight=None, partial=False): | |
619 """Finds the minimum weight set of edges to connect G if one exists. | |
620 | |
621 This is a variant of the weighted MST problem. | |
622 | |
623 Parameters | |
624 ---------- | |
625 G : NetworkX graph | |
626 An undirected graph. | |
627 | |
628 avail : dict or a set of 2 or 3 tuples | |
629 For more details, see :func:`k_edge_augmentation`. | |
630 | |
631 weight : string | |
632 key to use to find weights if ``avail`` is a set of 3-tuples. | |
633 For more details, see :func:`k_edge_augmentation`. | |
634 | |
635 partial : boolean | |
636 If partial is True and no feasible k-edge-augmentation exists, then the | |
637 augmenting edges minimize the number of connected components. | |
638 | |
639 Yields | |
640 ------ | |
641 edge : tuple | |
642 Edges in the subset of avail chosen to connect G. | |
643 | |
644 See Also | |
645 -------- | |
646 :func:`one_edge_augmentation` | |
647 :func:`k_edge_augmentation` | |
648 | |
649 Example | |
650 ------- | |
651 >>> G = nx.Graph([(1, 2), (2, 3), (4, 5)]) | |
652 >>> G.add_nodes_from([6, 7, 8]) | |
653 >>> # any edge not in avail has an implicit weight of infinity | |
654 >>> avail = [(1, 3), (1, 5), (4, 7), (4, 8), (6, 1), (8, 1), (8, 2)] | |
655 >>> sorted(weighted_one_edge_augmentation(G, avail)) | |
656 [(1, 5), (4, 7), (6, 1), (8, 1)] | |
657 >>> # find another solution by giving large weights to edges in the | |
658 >>> # previous solution (note some of the old edges must be used) | |
659 >>> avail = [(1, 3), (1, 5, 99), (4, 7, 9), (6, 1, 99), (8, 1, 99), (8, 2)] | |
660 >>> sorted(weighted_one_edge_augmentation(G, avail)) | |
661 [(1, 5), (4, 7), (6, 1), (8, 2)] | |
662 """ | |
663 avail_uv, avail_w = _unpack_available_edges(avail, weight=weight, G=G) | |
664 # Collapse CCs in the original graph into nodes in a metagraph | |
665 # Then find an MST of the metagraph instead of the original graph | |
666 C = collapse(G, nx.connected_components(G)) | |
667 mapping = C.graph["mapping"] | |
668 # Assign each available edge to an edge in the metagraph | |
669 candidate_mapping = _lightest_meta_edges(mapping, avail_uv, avail_w) | |
670 # nx.set_edge_attributes(C, name='weight', values=0) | |
671 C.add_edges_from( | |
672 (mu, mv, {"weight": w, "generator": uv}) | |
673 for (mu, mv), uv, w in candidate_mapping | |
674 ) | |
675 # Find MST of the meta graph | |
676 meta_mst = nx.minimum_spanning_tree(C) | |
677 if not partial and not nx.is_connected(meta_mst): | |
678 raise nx.NetworkXUnfeasible("Not possible to connect G with available edges") | |
679 # Yield the edge that generated the meta-edge | |
680 for mu, mv, d in meta_mst.edges(data=True): | |
681 if "generator" in d: | |
682 edge = d["generator"] | |
683 yield edge | |
684 | |
685 | |
686 def unconstrained_bridge_augmentation(G): | |
687 """Finds an optimal 2-edge-augmentation of G using the fewest edges. | |
688 | |
689 This is an implementation of the algorithm detailed in [1]_. | |
690 The basic idea is to construct a meta-graph of bridge-ccs, connect leaf | |
691 nodes of the trees to connect the entire graph, and finally connect the | |
692 leafs of the tree in dfs-preorder to bridge connect the entire graph. | |
693 | |
694 Parameters | |
695 ---------- | |
696 G : NetworkX graph | |
697 An undirected graph. | |
698 | |
699 Yields | |
700 ------ | |
701 edge : tuple | |
702 Edges in the bridge augmentation of G | |
703 | |
704 Notes | |
705 ----- | |
706 Input: a graph G. | |
707 First find the bridge components of G and collapse each bridge-cc into a | |
708 node of a metagraph graph C, which is guaranteed to be a forest of trees. | |
709 | |
710 C contains p "leafs" --- nodes with exactly one incident edge. | |
711 C contains q "isolated nodes" --- nodes with no incident edges. | |
712 | |
713 Theorem: If p + q > 1, then at least :math:`ceil(p / 2) + q` edges are | |
714 needed to bridge connect C. This algorithm achieves this min number. | |
715 | |
716 The method first adds enough edges to make G into a tree and then pairs | |
717 leafs in a simple fashion. | |
718 | |
719 Let n be the number of trees in C. Let v(i) be an isolated vertex in the | |
720 i-th tree if one exists, otherwise it is a pair of distinct leafs nodes | |
721 in the i-th tree. Alternating edges from these sets (i.e. adding edges | |
722 A1 = [(v(i)[0], v(i + 1)[1]), v(i + 1)[0], v(i + 2)[1])...]) connects C | |
723 into a tree T. This tree has p' = p + 2q - 2(n -1) leafs and no isolated | |
724 vertices. A1 has n - 1 edges. The next step finds ceil(p' / 2) edges to | |
725 biconnect any tree with p' leafs. | |
726 | |
727 Convert T into an arborescence T' by picking an arbitrary root node with | |
728 degree >= 2 and directing all edges away from the root. Note the | |
729 implementation implicitly constructs T'. | |
730 | |
731 The leafs of T are the nodes with no existing edges in T'. | |
732 Order the leafs of T' by DFS prorder. Then break this list in half | |
733 and add the zipped pairs to A2. | |
734 | |
735 The set A = A1 + A2 is the minimum augmentation in the metagraph. | |
736 | |
737 To convert this to edges in the original graph | |
738 | |
739 References | |
740 ---------- | |
741 .. [1] Eswaran, Kapali P., and R. Endre Tarjan. (1975) Augmentation problems. | |
742 http://epubs.siam.org/doi/abs/10.1137/0205044 | |
743 | |
744 See Also | |
745 -------- | |
746 :func:`bridge_augmentation` | |
747 :func:`k_edge_augmentation` | |
748 | |
749 Example | |
750 ------- | |
751 >>> G = nx.path_graph((1, 2, 3, 4, 5, 6, 7)) | |
752 >>> sorted(unconstrained_bridge_augmentation(G)) | |
753 [(1, 7)] | |
754 >>> G = nx.path_graph((1, 2, 3, 2, 4, 5, 6, 7)) | |
755 >>> sorted(unconstrained_bridge_augmentation(G)) | |
756 [(1, 3), (3, 7)] | |
757 >>> G = nx.Graph([(0, 1), (0, 2), (1, 2)]) | |
758 >>> G.add_node(4) | |
759 >>> sorted(unconstrained_bridge_augmentation(G)) | |
760 [(1, 4), (4, 0)] | |
761 """ | |
762 # ----- | |
763 # Mapping of terms from (Eswaran and Tarjan): | |
764 # G = G_0 - the input graph | |
765 # C = G_0' - the bridge condensation of G. (This is a forest of trees) | |
766 # A1 = A_1 - the edges to connect the forest into a tree | |
767 # leaf = pendant - a node with degree of 1 | |
768 | |
769 # alpha(v) = maps the node v in G to its meta-node in C | |
770 # beta(x) = maps the meta-node x in C to any node in the bridge | |
771 # component of G corresponding to x. | |
772 | |
773 # find the 2-edge-connected components of G | |
774 bridge_ccs = list(nx.connectivity.bridge_components(G)) | |
775 # condense G into an forest C | |
776 C = collapse(G, bridge_ccs) | |
777 | |
778 # Choose pairs of distinct leaf nodes in each tree. If this is not | |
779 # possible then make a pair using the single isolated node in the tree. | |
780 vset1 = [ | |
781 tuple(cc) * 2 # case1: an isolated node | |
782 if len(cc) == 1 | |
783 else sorted(cc, key=C.degree)[0:2] # case2: pair of leaf nodes | |
784 for cc in nx.connected_components(C) | |
785 ] | |
786 if len(vset1) > 1: | |
787 # Use this set to construct edges that connect C into a tree. | |
788 nodes1 = [vs[0] for vs in vset1] | |
789 nodes2 = [vs[1] for vs in vset1] | |
790 A1 = list(zip(nodes1[1:], nodes2)) | |
791 else: | |
792 A1 = [] | |
793 # Connect each tree in the forest to construct an arborescence | |
794 T = C.copy() | |
795 T.add_edges_from(A1) | |
796 | |
797 # If there are only two leaf nodes, we simply connect them. | |
798 leafs = [n for n, d in T.degree() if d == 1] | |
799 if len(leafs) == 1: | |
800 A2 = [] | |
801 if len(leafs) == 2: | |
802 A2 = [tuple(leafs)] | |
803 else: | |
804 # Choose an arbitrary non-leaf root | |
805 try: | |
806 root = next(n for n, d in T.degree() if d > 1) | |
807 except StopIteration: # no nodes found with degree > 1 | |
808 return | |
809 # order the leaves of C by (induced directed) preorder | |
810 v2 = [n for n in nx.dfs_preorder_nodes(T, root) if T.degree(n) == 1] | |
811 # connecting first half of the leafs in pre-order to the second | |
812 # half will bridge connect the tree with the fewest edges. | |
813 half = int(math.ceil(len(v2) / 2.0)) | |
814 A2 = list(zip(v2[:half], v2[-half:])) | |
815 | |
816 # collect the edges used to augment the original forest | |
817 aug_tree_edges = A1 + A2 | |
818 | |
819 # Construct the mapping (beta) from meta-nodes to regular nodes | |
820 inverse = defaultdict(list) | |
821 for k, v in C.graph["mapping"].items(): | |
822 inverse[v].append(k) | |
823 # sort so we choose minimum degree nodes first | |
824 inverse = { | |
825 mu: sorted(mapped, key=lambda u: (G.degree(u), u)) | |
826 for mu, mapped in inverse.items() | |
827 } | |
828 | |
829 # For each meta-edge, map back to an arbitrary pair in the original graph | |
830 G2 = G.copy() | |
831 for mu, mv in aug_tree_edges: | |
832 # Find the first available edge that doesn't exist and return it | |
833 for u, v in it.product(inverse[mu], inverse[mv]): | |
834 if not G2.has_edge(u, v): | |
835 G2.add_edge(u, v) | |
836 yield u, v | |
837 break | |
838 | |
839 | |
840 def weighted_bridge_augmentation(G, avail, weight=None): | |
841 """Finds an approximate min-weight 2-edge-augmentation of G. | |
842 | |
843 This is an implementation of the approximation algorithm detailed in [1]_. | |
844 It chooses a set of edges from avail to add to G that renders it | |
845 2-edge-connected if such a subset exists. This is done by finding a | |
846 minimum spanning arborescence of a specially constructed metagraph. | |
847 | |
848 Parameters | |
849 ---------- | |
850 G : NetworkX graph | |
851 An undirected graph. | |
852 | |
853 avail : set of 2 or 3 tuples. | |
854 candidate edges (with optional weights) to choose from | |
855 | |
856 weight : string | |
857 key to use to find weights if avail is a set of 3-tuples where the | |
858 third item in each tuple is a dictionary. | |
859 | |
860 Yields | |
861 ------ | |
862 edge : tuple | |
863 Edges in the subset of avail chosen to bridge augment G. | |
864 | |
865 Notes | |
866 ----- | |
867 Finding a weighted 2-edge-augmentation is NP-hard. | |
868 Any edge not in ``avail`` is considered to have a weight of infinity. | |
869 The approximation factor is 2 if ``G`` is connected and 3 if it is not. | |
870 Runs in :math:`O(m + n log(n))` time | |
871 | |
872 References | |
873 ---------- | |
874 .. [1] Khuller, Samir, and Ramakrishna Thurimella. (1993) Approximation | |
875 algorithms for graph augmentation. | |
876 http://www.sciencedirect.com/science/article/pii/S0196677483710102 | |
877 | |
878 See Also | |
879 -------- | |
880 :func:`bridge_augmentation` | |
881 :func:`k_edge_augmentation` | |
882 | |
883 Example | |
884 ------- | |
885 >>> G = nx.path_graph((1, 2, 3, 4)) | |
886 >>> # When the weights are equal, (1, 4) is the best | |
887 >>> avail = [(1, 4, 1), (1, 3, 1), (2, 4, 1)] | |
888 >>> sorted(weighted_bridge_augmentation(G, avail)) | |
889 [(1, 4)] | |
890 >>> # Giving (1, 4) a high weight makes the two edge solution the best. | |
891 >>> avail = [(1, 4, 1000), (1, 3, 1), (2, 4, 1)] | |
892 >>> sorted(weighted_bridge_augmentation(G, avail)) | |
893 [(1, 3), (2, 4)] | |
894 >>> # ------ | |
895 >>> G = nx.path_graph((1, 2, 3, 4)) | |
896 >>> G.add_node(5) | |
897 >>> avail = [(1, 5, 11), (2, 5, 10), (4, 3, 1), (4, 5, 1)] | |
898 >>> sorted(weighted_bridge_augmentation(G, avail=avail)) | |
899 [(1, 5), (4, 5)] | |
900 >>> avail = [(1, 5, 11), (2, 5, 10), (4, 3, 1), (4, 5, 51)] | |
901 >>> sorted(weighted_bridge_augmentation(G, avail=avail)) | |
902 [(1, 5), (2, 5), (4, 5)] | |
903 """ | |
904 | |
905 if weight is None: | |
906 weight = "weight" | |
907 | |
908 # If input G is not connected the approximation factor increases to 3 | |
909 if not nx.is_connected(G): | |
910 H = G.copy() | |
911 connectors = list(one_edge_augmentation(H, avail=avail, weight=weight)) | |
912 H.add_edges_from(connectors) | |
913 | |
914 yield from connectors | |
915 else: | |
916 connectors = [] | |
917 H = G | |
918 | |
919 if len(avail) == 0: | |
920 if nx.has_bridges(H): | |
921 raise nx.NetworkXUnfeasible("no augmentation possible") | |
922 | |
923 avail_uv, avail_w = _unpack_available_edges(avail, weight=weight, G=H) | |
924 | |
925 # Collapse input into a metagraph. Meta nodes are bridge-ccs | |
926 bridge_ccs = nx.connectivity.bridge_components(H) | |
927 C = collapse(H, bridge_ccs) | |
928 | |
929 # Use the meta graph to shrink avail to a small feasible subset | |
930 mapping = C.graph["mapping"] | |
931 # Choose the minimum weight feasible edge in each group | |
932 meta_to_wuv = { | |
933 (mu, mv): (w, uv) | |
934 for (mu, mv), uv, w in _lightest_meta_edges(mapping, avail_uv, avail_w) | |
935 } | |
936 | |
937 # Mapping of terms from (Khuller and Thurimella): | |
938 # C : G_0 = (V, E^0) | |
939 # This is the metagraph where each node is a 2-edge-cc in G. | |
940 # The edges in C represent bridges in the original graph. | |
941 # (mu, mv) : E - E^0 # they group both avail and given edges in E | |
942 # T : \Gamma | |
943 # D : G^D = (V, E_D) | |
944 | |
945 # The paper uses ancestor because children point to parents, which is | |
946 # contrary to networkx standards. So, we actually need to run | |
947 # nx.least_common_ancestor on the reversed Tree. | |
948 | |
949 # Pick an arbitrary leaf from C as the root | |
950 try: | |
951 root = next(n for n, d in C.degree() if d == 1) | |
952 except StopIteration: # no nodes found with degree == 1 | |
953 return | |
954 # Root C into a tree TR by directing all edges away from the root | |
955 # Note in their paper T directs edges towards the root | |
956 TR = nx.dfs_tree(C, root) | |
957 | |
958 # Add to D the directed edges of T and set their weight to zero | |
959 # This indicates that it costs nothing to use edges that were given. | |
960 D = nx.reverse(TR).copy() | |
961 | |
962 nx.set_edge_attributes(D, name="weight", values=0) | |
963 | |
964 # The LCA of mu and mv in T is the shared ancestor of mu and mv that is | |
965 # located farthest from the root. | |
966 lca_gen = nx.tree_all_pairs_lowest_common_ancestor( | |
967 TR, root=root, pairs=meta_to_wuv.keys() | |
968 ) | |
969 | |
970 for (mu, mv), lca in lca_gen: | |
971 w, uv = meta_to_wuv[(mu, mv)] | |
972 if lca == mu: | |
973 # If u is an ancestor of v in TR, then add edge u->v to D | |
974 D.add_edge(lca, mv, weight=w, generator=uv) | |
975 elif lca == mv: | |
976 # If v is an ancestor of u in TR, then add edge v->u to D | |
977 D.add_edge(lca, mu, weight=w, generator=uv) | |
978 else: | |
979 # If neither u nor v is a ancestor of the other in TR | |
980 # let t = lca(TR, u, v) and add edges t->u and t->v | |
981 # Track the original edge that GENERATED these edges. | |
982 D.add_edge(lca, mu, weight=w, generator=uv) | |
983 D.add_edge(lca, mv, weight=w, generator=uv) | |
984 | |
985 # Then compute a minimum rooted branching | |
986 try: | |
987 # Note the original edges must be directed towards to root for the | |
988 # branching to give us a bridge-augmentation. | |
989 A = _minimum_rooted_branching(D, root) | |
990 except nx.NetworkXException as e: | |
991 # If there is no branching then augmentation is not possible | |
992 raise nx.NetworkXUnfeasible("no 2-edge-augmentation possible") from e | |
993 | |
994 # For each edge e, in the branching that did not belong to the directed | |
995 # tree T, add the corresponding edge that **GENERATED** it (this is not | |
996 # necesarilly e itself!) | |
997 | |
998 # ensure the third case does not generate edges twice | |
999 bridge_connectors = set() | |
1000 for mu, mv in A.edges(): | |
1001 data = D.get_edge_data(mu, mv) | |
1002 if "generator" in data: | |
1003 # Add the avail edge that generated the branching edge. | |
1004 edge = data["generator"] | |
1005 bridge_connectors.add(edge) | |
1006 | |
1007 yield from bridge_connectors | |
1008 | |
1009 | |
1010 def _minimum_rooted_branching(D, root): | |
1011 """Helper function to compute a minimum rooted branching (aka rooted | |
1012 arborescence) | |
1013 | |
1014 Before the branching can be computed, the directed graph must be rooted by | |
1015 removing the predecessors of root. | |
1016 | |
1017 A branching / arborescence of rooted graph G is a subgraph that contains a | |
1018 directed path from the root to every other vertex. It is the directed | |
1019 analog of the minimum spanning tree problem. | |
1020 | |
1021 References | |
1022 ---------- | |
1023 [1] Khuller, Samir (2002) Advanced Algorithms Lecture 24 Notes. | |
1024 https://www.cs.umd.edu/class/spring2011/cmsc651/lec07.pdf | |
1025 """ | |
1026 rooted = D.copy() | |
1027 # root the graph by removing all predecessors to `root`. | |
1028 rooted.remove_edges_from([(u, root) for u in D.predecessors(root)]) | |
1029 # Then compute the branching / arborescence. | |
1030 A = nx.minimum_spanning_arborescence(rooted) | |
1031 return A | |
1032 | |
1033 | |
1034 def collapse(G, grouped_nodes): | |
1035 """Collapses each group of nodes into a single node. | |
1036 | |
1037 This is similar to condensation, but works on undirected graphs. | |
1038 | |
1039 Parameters | |
1040 ---------- | |
1041 G : NetworkX Graph | |
1042 | |
1043 grouped_nodes: list or generator | |
1044 Grouping of nodes to collapse. The grouping must be disjoint. | |
1045 If grouped_nodes are strongly_connected_components then this is | |
1046 equivalent to :func:`condensation`. | |
1047 | |
1048 Returns | |
1049 ------- | |
1050 C : NetworkX Graph | |
1051 The collapsed graph C of G with respect to the node grouping. The node | |
1052 labels are integers corresponding to the index of the component in the | |
1053 list of grouped_nodes. C has a graph attribute named 'mapping' with a | |
1054 dictionary mapping the original nodes to the nodes in C to which they | |
1055 belong. Each node in C also has a node attribute 'members' with the set | |
1056 of original nodes in G that form the group that the node in C | |
1057 represents. | |
1058 | |
1059 Examples | |
1060 -------- | |
1061 >>> # Collapses a graph using disjoint groups, but not necesarilly connected | |
1062 >>> G = nx.Graph([(1, 0), (2, 3), (3, 1), (3, 4), (4, 5), (5, 6), (5, 7)]) | |
1063 >>> G.add_node("A") | |
1064 >>> grouped_nodes = [{0, 1, 2, 3}, {5, 6, 7}] | |
1065 >>> C = collapse(G, grouped_nodes) | |
1066 >>> members = nx.get_node_attributes(C, "members") | |
1067 >>> sorted(members.keys()) | |
1068 [0, 1, 2, 3] | |
1069 >>> member_values = set(map(frozenset, members.values())) | |
1070 >>> assert {0, 1, 2, 3} in member_values | |
1071 >>> assert {4} in member_values | |
1072 >>> assert {5, 6, 7} in member_values | |
1073 >>> assert {"A"} in member_values | |
1074 """ | |
1075 mapping = {} | |
1076 members = {} | |
1077 C = G.__class__() | |
1078 i = 0 # required if G is empty | |
1079 remaining = set(G.nodes()) | |
1080 for i, group in enumerate(grouped_nodes): | |
1081 group = set(group) | |
1082 assert remaining.issuperset( | |
1083 group | |
1084 ), "grouped nodes must exist in G and be disjoint" | |
1085 remaining.difference_update(group) | |
1086 members[i] = group | |
1087 mapping.update((n, i) for n in group) | |
1088 # remaining nodes are in their own group | |
1089 for i, node in enumerate(remaining, start=i + 1): | |
1090 group = {node} | |
1091 members[i] = group | |
1092 mapping.update((n, i) for n in group) | |
1093 number_of_groups = i + 1 | |
1094 C.add_nodes_from(range(number_of_groups)) | |
1095 C.add_edges_from( | |
1096 (mapping[u], mapping[v]) for u, v in G.edges() if mapping[u] != mapping[v] | |
1097 ) | |
1098 # Add a list of members (ie original nodes) to each node (ie scc) in C. | |
1099 nx.set_node_attributes(C, name="members", values=members) | |
1100 # Add mapping dict as graph attribute | |
1101 C.graph["mapping"] = mapping | |
1102 return C | |
1103 | |
1104 | |
1105 def complement_edges(G): | |
1106 """Returns only the edges in the complement of G | |
1107 | |
1108 Parameters | |
1109 ---------- | |
1110 G : NetworkX Graph | |
1111 | |
1112 Yields | |
1113 ------ | |
1114 edge : tuple | |
1115 Edges in the complement of G | |
1116 | |
1117 Example | |
1118 ------- | |
1119 >>> G = nx.path_graph((1, 2, 3, 4)) | |
1120 >>> sorted(complement_edges(G)) | |
1121 [(1, 3), (1, 4), (2, 4)] | |
1122 >>> G = nx.path_graph((1, 2, 3, 4), nx.DiGraph()) | |
1123 >>> sorted(complement_edges(G)) | |
1124 [(1, 3), (1, 4), (2, 1), (2, 4), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)] | |
1125 >>> G = nx.complete_graph(1000) | |
1126 >>> sorted(complement_edges(G)) | |
1127 [] | |
1128 """ | |
1129 if G.is_directed(): | |
1130 for u, v in it.combinations(G.nodes(), 2): | |
1131 if v not in G.adj[u]: | |
1132 yield (u, v) | |
1133 if u not in G.adj[v]: | |
1134 yield (v, u) | |
1135 else: | |
1136 for u, v in it.combinations(G.nodes(), 2): | |
1137 if v not in G.adj[u]: | |
1138 yield (u, v) | |
1139 | |
1140 | |
1141 def _compat_shuffle(rng, input): | |
1142 """wrapper around rng.shuffle for python 2 compatibility reasons""" | |
1143 rng.shuffle(input) | |
1144 | |
1145 | |
1146 @py_random_state(4) | |
1147 @not_implemented_for("multigraph") | |
1148 @not_implemented_for("directed") | |
1149 def greedy_k_edge_augmentation(G, k, avail=None, weight=None, seed=None): | |
1150 """Greedy algorithm for finding a k-edge-augmentation | |
1151 | |
1152 Parameters | |
1153 ---------- | |
1154 G : NetworkX graph | |
1155 An undirected graph. | |
1156 | |
1157 k : integer | |
1158 Desired edge connectivity | |
1159 | |
1160 avail : dict or a set of 2 or 3 tuples | |
1161 For more details, see :func:`k_edge_augmentation`. | |
1162 | |
1163 weight : string | |
1164 key to use to find weights if ``avail`` is a set of 3-tuples. | |
1165 For more details, see :func:`k_edge_augmentation`. | |
1166 | |
1167 seed : integer, random_state, or None (default) | |
1168 Indicator of random number generation state. | |
1169 See :ref:`Randomness<randomness>`. | |
1170 | |
1171 Yields | |
1172 ------ | |
1173 edge : tuple | |
1174 Edges in the greedy augmentation of G | |
1175 | |
1176 Notes | |
1177 ----- | |
1178 The algorithm is simple. Edges are incrementally added between parts of the | |
1179 graph that are not yet locally k-edge-connected. Then edges are from the | |
1180 augmenting set are pruned as long as local-edge-connectivity is not broken. | |
1181 | |
1182 This algorithm is greedy and does not provide optimality guarantees. It | |
1183 exists only to provide :func:`k_edge_augmentation` with the ability to | |
1184 generate a feasible solution for arbitrary k. | |
1185 | |
1186 See Also | |
1187 -------- | |
1188 :func:`k_edge_augmentation` | |
1189 | |
1190 Example | |
1191 ------- | |
1192 >>> G = nx.path_graph((1, 2, 3, 4, 5, 6, 7)) | |
1193 >>> sorted(greedy_k_edge_augmentation(G, k=2)) | |
1194 [(1, 7)] | |
1195 >>> sorted(greedy_k_edge_augmentation(G, k=1, avail=[])) | |
1196 [] | |
1197 >>> G = nx.path_graph((1, 2, 3, 4, 5, 6, 7)) | |
1198 >>> avail = {(u, v): 1 for (u, v) in complement_edges(G)} | |
1199 >>> # randomized pruning process can produce different solutions | |
1200 >>> sorted(greedy_k_edge_augmentation(G, k=4, avail=avail, seed=2)) | |
1201 [(1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (2, 4), (2, 6), (3, 7), (5, 7)] | |
1202 >>> sorted(greedy_k_edge_augmentation(G, k=4, avail=avail, seed=3)) | |
1203 [(1, 3), (1, 5), (1, 6), (2, 4), (2, 6), (3, 7), (4, 7), (5, 7)] | |
1204 """ | |
1205 # Result set | |
1206 aug_edges = [] | |
1207 | |
1208 done = is_k_edge_connected(G, k) | |
1209 if done: | |
1210 return | |
1211 if avail is None: | |
1212 # all edges are available | |
1213 avail_uv = list(complement_edges(G)) | |
1214 avail_w = [1] * len(avail_uv) | |
1215 else: | |
1216 # Get the unique set of unweighted edges | |
1217 avail_uv, avail_w = _unpack_available_edges(avail, weight=weight, G=G) | |
1218 | |
1219 # Greedy: order lightest edges. Use degree sum to tie-break | |
1220 tiebreaker = [sum(map(G.degree, uv)) for uv in avail_uv] | |
1221 avail_wduv = sorted(zip(avail_w, tiebreaker, avail_uv)) | |
1222 avail_uv = [uv for w, d, uv in avail_wduv] | |
1223 | |
1224 # Incrementally add edges in until we are k-connected | |
1225 H = G.copy() | |
1226 for (u, v) in avail_uv: | |
1227 done = False | |
1228 if not is_locally_k_edge_connected(H, u, v, k=k): | |
1229 # Only add edges in parts that are not yet locally k-edge-connected | |
1230 aug_edges.append((u, v)) | |
1231 H.add_edge(u, v) | |
1232 # Did adding this edge help? | |
1233 if H.degree(u) >= k and H.degree(v) >= k: | |
1234 done = is_k_edge_connected(H, k) | |
1235 if done: | |
1236 break | |
1237 | |
1238 # Check for feasibility | |
1239 if not done: | |
1240 raise nx.NetworkXUnfeasible("not able to k-edge-connect with available edges") | |
1241 | |
1242 # Randomized attempt to reduce the size of the solution | |
1243 _compat_shuffle(seed, aug_edges) | |
1244 for (u, v) in list(aug_edges): | |
1245 # Don't remove if we know it would break connectivity | |
1246 if H.degree(u) <= k or H.degree(v) <= k: | |
1247 continue | |
1248 H.remove_edge(u, v) | |
1249 aug_edges.remove((u, v)) | |
1250 if not is_k_edge_connected(H, k=k): | |
1251 # If removing this edge breaks feasibility, undo | |
1252 H.add_edge(u, v) | |
1253 aug_edges.append((u, v)) | |
1254 | |
1255 # Generate results | |
1256 yield from aug_edges |