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