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