Statistics
| Branch: | Revision:

## iof-tools / networkxMiCe / networkx-master / networkx / algorithms / connectivity / edge_augmentation.py @ 5cef0f13

 1 ```# -*- coding: utf-8 -*- ``` ```# Copyright (C) 2004-2019 by ``` ```# Aric Hagberg ``` ```# Dan Schult ``` ```# Pieter Swart ``` ```# All rights reserved. ``` ```# BSD license. ``` ```# ``` ```# Authors: Jon Crall (erotemic@gmail.com) ``` ```""" ``` ```Algorithms for finding k-edge-augmentations ``` ``` ``` ```A k-edge-augmentation is a set of edges, that once added to a graph, ensures ``` ```that the graph is k-edge-connected; i.e. the graph cannot be disconnected ``` ```unless k or more edges are removed. Typically, the goal is to find the ``` ```augmentation with minimum weight. In general, it is not guaranteed that a ``` ```k-edge-augmentation exists. ``` ``` ``` ```See Also ``` ```-------- ``` ```:mod:`edge_kcomponents` : algorithms for finding k-edge-connected components ``` ```:mod:`connectivity` : algorithms for determening edge connectivity. ``` ```""" ``` ```import math ``` ```import sys ``` ```import itertools as it ``` ```import networkx as nx ``` ```from networkx.utils import not_implemented_for, py_random_state ``` ```from collections import defaultdict, namedtuple ``` ```__all__ = [ ``` ``` 'k_edge_augmentation', ``` ``` 'is_k_edge_connected', ``` ``` 'is_locally_k_edge_connected', ``` ```] ``` ```@not_implemented_for('directed') ``` ```@not_implemented_for('multigraph') ``` ```def is_k_edge_connected(G, k): ``` ``` """Tests to see if a graph is k-edge-connected. ``` ``` ``` ``` Is it impossible to disconnect the graph by removing fewer than k edges? ``` ``` If so, then G is k-edge-connected. ``` ``` ``` ``` Parameters ``` ``` ---------- ``` ``` G : NetworkX graph ``` ``` An undirected graph. ``` ``` ``` ``` k : integer ``` ``` edge connectivity to test for ``` ``` ``` ``` Returns ``` ``` ------- ``` ``` boolean ``` ``` True if G is k-edge-connected. ``` ``` ``` ``` See Also ``` ``` -------- ``` ``` :func:`is_locally_k_edge_connected` ``` ``` ``` ``` Example ``` ``` ------- ``` ``` >>> G = nx.barbell_graph(10, 0) ``` ``` >>> nx.is_k_edge_connected(G, k=1) ``` ``` True ``` ``` >>> nx.is_k_edge_connected(G, k=2) ``` ``` False ``` ``` """ ``` ``` if k < 1: ``` ``` raise ValueError('k must be positive, not {}'.format(k)) ``` ``` # First try to quickly determine if G is not k-edge-connected ``` ``` if G.number_of_nodes() < k + 1: ``` ``` return False ``` ``` elif any(d < k for n, d in G.degree()): ``` ``` return False ``` ``` else: ``` ``` # Otherwise perform the full check ``` ``` if k == 1: ``` ``` return nx.is_connected(G) ``` ``` elif k == 2: ``` ``` return not nx.has_bridges(G) ``` ``` else: ``` ``` return nx.edge_connectivity(G, cutoff=k) >= k ``` ```@not_implemented_for('directed') ``` ```@not_implemented_for('multigraph') ``` ```def is_locally_k_edge_connected(G, s, t, k): ``` ``` """Tests to see if an edge in a graph is locally k-edge-connected. ``` ``` ``` ``` Is it impossible to disconnect s and t by removing fewer than k edges? ``` ``` If so, then s and t are locally k-edge-connected in G. ``` ``` ``` ``` Parameters ``` ``` ---------- ``` ``` G : NetworkX graph ``` ``` An undirected graph. ``` ``` ``` ``` s : node ``` ``` Source node ``` ``` ``` ``` t : node ``` ``` Target node ``` ``` ``` ``` k : integer ``` ``` local edge connectivity for nodes s and t ``` ``` ``` ``` Returns ``` ``` ------- ``` ``` boolean ``` ``` True if s and t are locally k-edge-connected in G. ``` ``` ``` ``` See Also ``` ``` -------- ``` ``` :func:`is_k_edge_connected` ``` ``` ``` ``` Example ``` ``` ------- ``` ``` >>> from networkx.algorithms.connectivity import is_locally_k_edge_connected ``` ``` >>> G = nx.barbell_graph(10, 0) ``` ``` >>> is_locally_k_edge_connected(G, 5, 15, k=1) ``` ``` True ``` ``` >>> is_locally_k_edge_connected(G, 5, 15, k=2) ``` ``` False ``` ``` >>> is_locally_k_edge_connected(G, 1, 5, k=2) ``` ``` True ``` ``` """ ``` ``` if k < 1: ``` ``` raise ValueError('k must be positive, not {}'.format(k)) ``` ``` # First try to quickly determine s, t is not k-locally-edge-connected in G ``` ``` if G.degree(s) < k or G.degree(t) < k: ``` ``` return False ``` ``` else: ``` ``` # Otherwise perform the full check ``` ``` if k == 1: ``` ``` return nx.has_path(G, s, t) ``` ``` else: ``` ``` localk = nx.connectivity.local_edge_connectivity(G, s, t, cutoff=k) ``` ``` return localk >= k ``` ```@not_implemented_for('directed') ``` ```@not_implemented_for('multigraph') ``` ```def k_edge_augmentation(G, k, avail=None, weight=None, partial=False): ``` ``` """Finds set of edges to k-edge-connect G. ``` ``` ``` ``` Adding edges from the augmentation to G make it impossible to disconnect G ``` ``` unless k or more edges are removed. This function uses the most efficient ``` ``` function available (depending on the value of k and if the problem is ``` ``` weighted or unweighted) to search for a minimum weight subset of available ``` ``` edges that k-edge-connects G. In general, finding a k-edge-augmentation is ``` ``` NP-hard, so solutions are not garuenteed to be minimal. Furthermore, a ``` ``` k-edge-augmentation may not exist. ``` ``` ``` ``` Parameters ``` ``` ---------- ``` ``` G : NetworkX graph ``` ``` An undirected graph. ``` ``` ``` ``` k : integer ``` ``` Desired edge connectivity ``` ``` ``` ``` avail : dict or a set of 2 or 3 tuples ``` ``` The available edges that can be used in the augmentation. ``` ``` ``` ``` If unspecified, then all edges in the complement of G are available. ``` ``` Otherwise, each item is an available edge (with an optional weight). ``` ``` ``` ``` In the unweighted case, each item is an edge ``(u, v)``. ``` ``` ``` ``` In the weighted case, each item is a 3-tuple ``(u, v, d)`` or a dict ``` ``` with items ``(u, v): d``. The third item, ``d``, can be a dictionary ``` ``` or a real number. If ``d`` is a dictionary ``d[weight]`` ``` ``` correspondings to the weight. ``` ``` ``` ``` weight : string ``` ``` key to use to find weights if ``avail`` is a set of 3-tuples where the ``` ``` third item in each tuple is a dictionary. ``` ``` ``` ``` partial : boolean ``` ``` If partial is True and no feasible k-edge-augmentation exists, then all ``` ``` a partial k-edge-augmentation is generated. Adding the edges in a ``` ``` partial augmentation to G, minimizes the number of k-edge-connected ``` ``` components and maximizes the edge connectivity between those ``` ``` components. For details, see :func:`partial_k_edge_augmentation`. ``` ``` ``` ``` Yields ``` ``` ------ ``` ``` edge : tuple ``` ``` Edges that, once added to G, would cause G to become k-edge-connected. ``` ``` If partial is False, an error is raised if this is not possible. ``` ``` Otherwise, generated edges form a partial augmentation, which ``` ``` k-edge-connects any part of G where it is possible, and maximally ``` ``` connects the remaining parts. ``` ``` ``` ``` Raises ``` ``` ------ ``` ``` NetworkXUnfeasible: ``` ``` If partial is False and no k-edge-augmentation exists. ``` ``` ``` ``` NetworkXNotImplemented: ``` ``` If the input graph is directed or a multigraph. ``` ``` ``` ``` ValueError: ``` ``` If k is less than 1 ``` ``` ``` ``` Notes ``` ``` ----- ``` ``` When k=1 this returns an optimal solution. ``` ``` ``` ``` When k=2 and ``avail`` is None, this returns an optimal solution. ``` ``` Otherwise when k=2, this returns a 2-approximation of the optimal solution. ``` ``` ``` ``` For k>3, this problem is NP-hard and this uses a randomized algorithm that ``` ``` produces a feasible solution, but provides no guarantees on the ``` ``` solution weight. ``` ``` ``` ``` Example ``` ``` ------- ``` ``` >>> # Unweighted cases ``` ``` >>> G = nx.path_graph((1, 2, 3, 4)) ``` ``` >>> G.add_node(5) ``` ``` >>> sorted(nx.k_edge_augmentation(G, k=1)) ``` ``` [(1, 5)] ``` ``` >>> sorted(nx.k_edge_augmentation(G, k=2)) ``` ``` [(1, 5), (5, 4)] ``` ``` >>> sorted(nx.k_edge_augmentation(G, k=3)) ``` ``` [(1, 4), (1, 5), (2, 5), (3, 5), (4, 5)] ``` ``` >>> complement = list(nx.k_edge_augmentation(G, k=5, partial=True)) ``` ``` >>> G.add_edges_from(complement) ``` ``` >>> nx.edge_connectivity(G) ``` ``` 4 ``` ``` ``` ``` Example ``` ``` ------- ``` ``` >>> # Weighted cases ``` ``` >>> G = nx.path_graph((1, 2, 3, 4)) ``` ``` >>> G.add_node(5) ``` ``` >>> # avail can be a tuple with a dict ``` ``` >>> avail = [(1, 5, {'weight': 11}), (2, 5, {'weight': 10})] ``` ``` >>> sorted(nx.k_edge_augmentation(G, k=1, avail=avail, weight='weight')) ``` ``` [(2, 5)] ``` ``` >>> # or avail can be a 3-tuple with a real number ``` ``` >>> avail = [(1, 5, 11), (2, 5, 10), (4, 3, 1), (4, 5, 51)] ``` ``` >>> sorted(nx.k_edge_augmentation(G, k=2, avail=avail)) ``` ``` [(1, 5), (2, 5), (4, 5)] ``` ``` >>> # or avail can be a dict ``` ``` >>> avail = {(1, 5): 11, (2, 5): 10, (4, 3): 1, (4, 5): 51} ``` ``` >>> sorted(nx.k_edge_augmentation(G, k=2, avail=avail)) ``` ``` [(1, 5), (2, 5), (4, 5)] ``` ``` >>> # If augmentation is infeasible, then a partial solution can be found ``` ``` >>> avail = {(1, 5): 11} ``` ``` >>> sorted(nx.k_edge_augmentation(G, k=2, avail=avail, partial=True)) ``` ``` [(1, 5)] ``` ``` """ ``` ``` try: ``` ``` if k <= 0: ``` ``` raise ValueError('k must be a positive integer, not {}'.format(k)) ``` ``` elif G.number_of_nodes() < k + 1: ``` ``` msg = 'impossible to {} connect in graph with less than {} nodes' ``` ``` raise nx.NetworkXUnfeasible(msg.format(k, k + 1)) ``` ``` elif avail is not None and len(avail) == 0: ``` ``` if not nx.is_k_edge_connected(G, k): ``` ``` raise nx.NetworkXUnfeasible('no available edges') ``` ``` aug_edges = [] ``` ``` elif k == 1: ``` ``` aug_edges = one_edge_augmentation(G, avail=avail, weight=weight, ``` ``` partial=partial) ``` ``` elif k == 2: ``` ``` aug_edges = bridge_augmentation(G, avail=avail, weight=weight) ``` ``` else: ``` ``` # raise NotImplementedError( ``` ``` # 'not implemented for k>2. k={}'.format(k)) ``` ``` aug_edges = greedy_k_edge_augmentation( ``` ``` G, k=k, avail=avail, weight=weight, seed=0) ``` ``` # Do eager evaulation so we can catch any exceptions ``` ``` # Before executing partial code. ``` ``` for edge in list(aug_edges): ``` ``` yield edge ``` ``` except nx.NetworkXUnfeasible: ``` ``` if partial: ``` ``` # Return all available edges ``` ``` if avail is None: ``` ``` aug_edges = complement_edges(G) ``` ``` else: ``` ``` # If we can't k-edge-connect the entire graph, try to ``` ``` # k-edge-connect as much as possible ``` ``` aug_edges = partial_k_edge_augmentation(G, k=k, avail=avail, ``` ``` weight=weight) ``` ``` for edge in aug_edges: ``` ``` yield edge ``` ``` else: ``` ``` raise ``` ```def partial_k_edge_augmentation(G, k, avail, weight=None): ``` ``` """Finds augmentation that k-edge-connects as much of the graph as possible. ``` ``` ``` ``` When a k-edge-augmentation is not possible, we can still try to find a ``` ``` small set of edges that partially k-edge-connects as much of the graph as ``` ``` possible. All possible edges are generated between remaining parts. ``` ``` This minimizes the number of k-edge-connected subgraphs in the resulting ``` ``` graph and maxmizes the edge connectivity between those subgraphs. ``` ``` ``` ``` Parameters ``` ``` ---------- ``` ``` G : NetworkX graph ``` ``` An undirected graph. ``` ``` ``` ``` k : integer ``` ``` Desired edge connectivity ``` ``` ``` ``` avail : dict or a set of 2 or 3 tuples ``` ``` For more details, see :func:`k_edge_augmentation`. ``` ``` ``` ``` weight : string ``` ``` key to use to find weights if ``avail`` is a set of 3-tuples. ``` ``` For more details, see :func:`k_edge_augmentation`. ``` ``` ``` ``` Yields ``` ``` ------ ``` ``` edge : tuple ``` ``` Edges in the partial augmentation of G. These edges k-edge-connect any ``` ``` part of G where it is possible, and maximally connects the remaining ``` ``` parts. In other words, all edges from avail are generated except for ``` ``` those within subgraphs that have already become k-edge-connected. ``` ``` ``` ``` Notes ``` ``` ----- ``` ``` Construct H that augments G with all edges in avail. ``` ``` Find the k-edge-subgraphs of H. ``` ``` For each k-edge-subgraph, if the number of nodes is more than k, then find ``` ``` the k-edge-augmentation of that graph and add it to the solution. Then add ``` ``` all edges in avail between k-edge subgraphs to the solution. ``` ``` ``` ``` See Also ``` ``` -------- ``` ``` :func:`k_edge_augmentation` ``` ``` ``` ``` Example ``` ``` ------- ``` ``` >>> G = nx.path_graph((1, 2, 3, 4, 5, 6, 7)) ``` ``` >>> G.add_node(8) ``` ``` >>> avail = [(1, 3), (1, 4), (1, 5), (2, 4), (2, 5), (3, 5), (1, 8)] ``` ``` >>> sorted(partial_k_edge_augmentation(G, k=2, avail=avail)) ``` ``` [(1, 5), (1, 8)] ``` ``` """ ``` ``` def _edges_between_disjoint(H, only1, only2): ``` ``` """ finds edges between disjoint nodes """ ``` ``` only1_adj = {u: set(H.adj[u]) for u in only1} ``` ``` for u, neighbs in only1_adj.items(): ``` ``` # Find the neighbors of u in only1 that are also in only2 ``` ``` neighbs12 = neighbs.intersection(only2) ``` ``` for v in neighbs12: ``` ``` yield (u, v) ``` ``` avail_uv, avail_w = _unpack_available_edges(avail, weight=weight, G=G) ``` ``` # Find which parts of the graph can be k-edge-connected ``` ``` H = G.copy() ``` ``` H.add_edges_from( ``` ``` ((u, v, {'weight': w, 'generator': (u, v)}) ``` ``` for (u, v), w in zip(avail, avail_w))) ``` ``` k_edge_subgraphs = list(nx.k_edge_subgraphs(H, k=k)) ``` ``` # Generate edges to k-edge-connect internal subgraphs ``` ``` for nodes in k_edge_subgraphs: ``` ``` if len(nodes) > 1: ``` ``` # Get the k-edge-connected subgraph ``` ``` C = H.subgraph(nodes).copy() ``` ``` # Find the internal edges that were available ``` ``` sub_avail = { ``` ``` d['generator']: d['weight'] ``` ``` for (u, v, d) in C.edges(data=True) ``` ``` if 'generator' in d ``` ``` } ``` ``` # Remove potential augmenting edges ``` ``` C.remove_edges_from(sub_avail.keys()) ``` ``` # Find a subset of these edges that makes the compoment ``` ``` # k-edge-connected and ignore the rest ``` ``` for edge in nx.k_edge_augmentation(C, k=k, avail=sub_avail): ``` ``` yield edge ``` ``` # Generate all edges between CCs that could not be k-edge-connected ``` ``` for cc1, cc2 in it.combinations(k_edge_subgraphs, 2): ``` ``` for (u, v) in _edges_between_disjoint(H, cc1, cc2): ``` ``` d = H.get_edge_data(u, v) ``` ``` edge = d.get('generator', None) ``` ``` if edge is not None: ``` ``` yield edge ``` ```@not_implemented_for('multigraph') ``` ```@not_implemented_for('directed') ``` ```def one_edge_augmentation(G, avail=None, weight=None, partial=False): ``` ``` """Finds minimum weight set of edges to connect G. ``` ``` ``` ``` Equivalent to :func:`k_edge_augmentation` when k=1. Adding the resulting ``` ``` edges to G will make it 1-edge-connected. The solution is optimal for both ``` ``` weighted and non-weighted variants. ``` ``` ``` ``` Parameters ``` ``` ---------- ``` ``` G : NetworkX graph ``` ``` An undirected graph. ``` ``` ``` ``` avail : dict or a set of 2 or 3 tuples ``` ``` For more details, see :func:`k_edge_augmentation`. ``` ``` ``` ``` weight : string ``` ``` key to use to find weights if ``avail`` is a set of 3-tuples. ``` ``` For more details, see :func:`k_edge_augmentation`. ``` ``` ``` ``` partial : boolean ``` ``` If partial is True and no feasible k-edge-augmentation exists, then the ``` ``` augmenting edges minimize the number of connected components. ``` ``` ``` ``` Yields ``` ``` ------ ``` ``` edge : tuple ``` ``` Edges in the one-augmentation of G ``` ``` ``` ``` Raises ``` ``` ------ ``` ``` NetworkXUnfeasible: ``` ``` If partial is False and no one-edge-augmentation exists. ``` ``` ``` ``` Notes ``` ``` ----- ``` ``` Uses either :func:`unconstrained_one_edge_augmentation` or ``` ``` :func:`weighted_one_edge_augmentation` depending on whether ``avail`` is ``` ``` specified. Both algorithms are based on finding a minimum spanning tree. ``` ``` As such both algorithms find optimal solutions and run in linear time. ``` ``` ``` ``` See Also ``` ``` -------- ``` ``` :func:`k_edge_augmentation` ``` ``` """ ``` ``` if avail is None: ``` ``` return unconstrained_one_edge_augmentation(G) ``` ``` else: ``` ``` return weighted_one_edge_augmentation(G, avail=avail, weight=weight, ``` ``` partial=partial) ``` ```@not_implemented_for('multigraph') ``` ```@not_implemented_for('directed') ``` ```def bridge_augmentation(G, avail=None, weight=None): ``` ``` """Finds the a set of edges that bridge connects G. ``` ``` ``` ``` Equivalent to :func:`k_edge_augmentation` when k=2, and partial=False. ``` ``` Adding the resulting edges to G will make it 2-edge-connected. If no ``` ``` constraints are specified the returned set of edges is minimum an optimal, ``` ``` otherwise the solution is approximated. ``` ``` ``` ``` Parameters ``` ``` ---------- ``` ``` G : NetworkX graph ``` ``` An undirected graph. ``` ``` ``` ``` avail : dict or a set of 2 or 3 tuples ``` ``` For more details, see :func:`k_edge_augmentation`. ``` ``` ``` ``` weight : string ``` ``` key to use to find weights if ``avail`` is a set of 3-tuples. ``` ``` For more details, see :func:`k_edge_augmentation`. ``` ``` ``` ``` Yields ``` ``` ------ ``` ``` edge : tuple ``` ``` Edges in the bridge-augmentation of G ``` ``` ``` ``` Raises ``` ``` ------ ``` ``` NetworkXUnfeasible: ``` ``` If no bridge-augmentation exists. ``` ``` ``` ``` Notes ``` ``` ----- ``` ``` If there are no constraints the solution can be computed in linear time ``` ``` using :func:`unconstrained_bridge_augmentation`. Otherwise, the problem ``` ``` becomes NP-hard and is the solution is approximated by ``` ``` :func:`weighted_bridge_augmentation`. ``` ``` ``` ``` See Also ``` ``` -------- ``` ``` :func:`k_edge_augmentation` ``` ``` """ ``` ``` if G.number_of_nodes() < 3: ``` ``` raise nx.NetworkXUnfeasible( ``` ``` 'impossible to bridge connect less than 3 nodes') ``` ``` if avail is None: ``` ``` return unconstrained_bridge_augmentation(G) ``` ``` else: ``` ``` return weighted_bridge_augmentation(G, avail, weight=weight) ``` ```# --- Algorithms and Helpers --- ``` ```def _ordered(u, v): ``` ``` """Returns the nodes in an undirected edge in lower-triangular order""" ``` ``` return (u, v) if u < v else (v, u) ``` ```def _unpack_available_edges(avail, weight=None, G=None): ``` ``` """Helper to separate avail into edges and corresponding weights""" ``` ``` if weight is None: ``` ``` weight = 'weight' ``` ``` if isinstance(avail, dict): ``` ``` avail_uv = list(avail.keys()) ``` ``` avail_w = list(avail.values()) ``` ``` else: ``` ``` def _try_getitem(d): ``` ``` try: ``` ``` return d[weight] ``` ``` except TypeError: ``` ``` return d ``` ``` avail_uv = [tup[0:2] for tup in avail] ``` ``` avail_w = [1 if len(tup) == 2 else _try_getitem(tup[-1]) ``` ``` for tup in avail] ``` ``` if G is not None: ``` ``` # Edges already in the graph are filtered ``` ``` flags = [not G.has_edge(u, v) for u, v in avail_uv] ``` ``` avail_uv = list(it.compress(avail_uv, flags)) ``` ``` avail_w = list(it.compress(avail_w, flags)) ``` ``` return avail_uv, avail_w ``` ```MetaEdge = namedtuple('MetaEdge', ('meta_uv', 'uv', 'w')) ``` ```def _lightest_meta_edges(mapping, avail_uv, avail_w): ``` ``` """Maps available edges in the original graph to edges in the metagraph. ``` ``` ``` ``` Parameters ``` ``` ---------- ``` ``` mapping : dict ``` ``` mapping produced by :func:`collapse`, that maps each node in the ``` ``` original graph to a node in the meta graph ``` ``` ``` ``` avail_uv : list ``` ``` list of edges ``` ``` ``` ``` avail_w : list ``` ``` list of edge weights ``` ``` ``` ``` Notes ``` ``` ----- ``` ``` Each node in the metagraph is a k-edge-connected component in the original ``` ``` graph. We don't care about any edge within the same k-edge-connected ``` ``` component, so we ignore self edges. We also are only intereseted in the ``` ``` minimum weight edge bridging each k-edge-connected component so, we group ``` ``` the edges by meta-edge and take the lightest in each group. ``` ``` ``` ``` Example ``` ``` ------- ``` ``` >>> # Each group represents a meta-node ``` ``` >>> groups = ([1, 2, 3], [4, 5], ) ``` ``` >>> mapping = {n: meta_n for meta_n, ns in enumerate(groups) for n in ns} ``` ``` >>> avail_uv = [(1, 2), (3, 6), (1, 4), (5, 2), (6, 1), (2, 6), (3, 1)] ``` ``` >>> avail_w = [ 20, 99, 20, 15, 50, 99, 20] ``` ``` >>> sorted(_lightest_meta_edges(mapping, avail_uv, avail_w)) ``` ``` [MetaEdge(meta_uv=(0, 1), uv=(5, 2), w=15), MetaEdge(meta_uv=(0, 2), uv=(6, 1), w=50)] ``` ``` """ ``` ``` grouped_wuv = defaultdict(list) ``` ``` for w, (u, v) in zip(avail_w, avail_uv): ``` ``` # Order the meta-edge so it can be used as a dict key ``` ``` meta_uv = _ordered(mapping[u], mapping[v]) ``` ``` # Group each available edge using the meta-edge as a key ``` ``` grouped_wuv[meta_uv].append((w, u, v)) ``` ``` # Now that all available edges are grouped, choose one per group ``` ``` for (mu, mv), choices_wuv in grouped_wuv.items(): ``` ``` # Ignore available edges within the same meta-node ``` ``` if mu != mv: ``` ``` # Choose the lightest available edge belonging to each meta-edge ``` ``` w, u, v = min(choices_wuv) ``` ``` yield MetaEdge((mu, mv), (u, v), w) ``` ```def unconstrained_one_edge_augmentation(G): ``` ``` """Finds the smallest set of edges to connect G. ``` ``` ``` ``` This is a variant of the unweighted MST problem. ``` ``` If G is not empty, a feasible solution always exists. ``` ``` ``` ``` Parameters ``` ``` ---------- ``` ``` G : NetworkX graph ``` ``` An undirected graph. ``` ``` ``` ``` Yields ``` ``` ------ ``` ``` edge : tuple ``` ``` Edges in the one-edge-augmentation of G ``` ``` ``` ``` See Also ``` ``` -------- ``` ``` :func:`one_edge_augmentation` ``` ``` :func:`k_edge_augmentation` ``` ``` ``` ``` Example ``` ``` ------- ``` ``` >>> G = nx.Graph([(1, 2), (2, 3), (4, 5)]) ``` ``` >>> G.add_nodes_from([6, 7, 8]) ``` ``` >>> sorted(unconstrained_one_edge_augmentation(G)) ``` ``` [(1, 4), (4, 6), (6, 7), (7, 8)] ``` ``` """ ``` ``` ccs1 = list(nx.connected_components(G)) ``` ``` C = collapse(G, ccs1) ``` ``` # When we are not constrained, we can just make a meta graph tree. ``` ``` meta_nodes = list(C.nodes()) ``` ``` # build a path in the metagraph ``` ``` meta_aug = list(zip(meta_nodes, meta_nodes[1:])) ``` ``` # map that path to the original graph ``` ``` inverse = defaultdict(list) ``` ``` for k, v in C.graph['mapping'].items(): ``` ``` inverse[v].append(k) ``` ``` for mu, mv in meta_aug: ``` ``` yield (inverse[mu], inverse[mv]) ``` ```def weighted_one_edge_augmentation(G, avail, weight=None, partial=False): ``` ``` """Finds the minimum weight set of edges to connect G if one exists. ``` ``` ``` ``` This is a variant of the weighted MST problem. ``` ``` ``` ``` Parameters ``` ``` ---------- ``` ``` G : NetworkX graph ``` ``` An undirected graph. ``` ``` ``` ``` avail : dict or a set of 2 or 3 tuples ``` ``` For more details, see :func:`k_edge_augmentation`. ``` ``` ``` ``` weight : string ``` ``` key to use to find weights if ``avail`` is a set of 3-tuples. ``` ``` For more details, see :func:`k_edge_augmentation`. ``` ``` ``` ``` partial : boolean ``` ``` If partial is True and no feasible k-edge-augmentation exists, then the ``` ``` augmenting edges minimize the number of connected components. ``` ``` ``` ``` Yields ``` ``` ------ ``` ``` edge : tuple ``` ``` Edges in the subset of avail chosen to connect G. ``` ``` ``` ``` See Also ``` ``` -------- ``` ``` :func:`one_edge_augmentation` ``` ``` :func:`k_edge_augmentation` ``` ``` ``` ``` Example ``` ``` ------- ``` ``` >>> G = nx.Graph([(1, 2), (2, 3), (4, 5)]) ``` ``` >>> G.add_nodes_from([6, 7, 8]) ``` ``` >>> # any edge not in avail has an implicit weight of infinity ``` ``` >>> avail = [(1, 3), (1, 5), (4, 7), (4, 8), (6, 1), (8, 1), (8, 2)] ``` ``` >>> sorted(weighted_one_edge_augmentation(G, avail)) ``` ``` [(1, 5), (4, 7), (6, 1), (8, 1)] ``` ``` >>> # find another solution by giving large weights to edges in the ``` ``` >>> # previous solution (note some of the old edges must be used) ``` ``` >>> avail = [(1, 3), (1, 5, 99), (4, 7, 9), (6, 1, 99), (8, 1, 99), (8, 2)] ``` ``` >>> sorted(weighted_one_edge_augmentation(G, avail)) ``` ``` [(1, 5), (4, 7), (6, 1), (8, 2)] ``` ``` """ ``` ``` avail_uv, avail_w = _unpack_available_edges(avail, weight=weight, G=G) ``` ``` # Collapse CCs in the original graph into nodes in a metagraph ``` ``` # Then find an MST of the metagraph instead of the original graph ``` ``` C = collapse(G, nx.connected_components(G)) ``` ``` mapping = C.graph['mapping'] ``` ``` # Assign each available edge to an edge in the metagraph ``` ``` candidate_mapping = _lightest_meta_edges(mapping, avail_uv, avail_w) ``` ``` # nx.set_edge_attributes(C, name='weight', values=0) ``` ``` C.add_edges_from( ``` ``` (mu, mv, {'weight': w, 'generator': uv}) ``` ``` for (mu, mv), uv, w in candidate_mapping ``` ``` ) ``` ``` # Find MST of the meta graph ``` ``` meta_mst = nx.minimum_spanning_tree(C) ``` ``` if not partial and not nx.is_connected(meta_mst): ``` ``` raise nx.NetworkXUnfeasible( ``` ``` 'Not possible to connect G with available edges') ``` ``` # Yield the edge that generated the meta-edge ``` ``` for mu, mv, d in meta_mst.edges(data=True): ``` ``` if 'generator' in d: ``` ``` edge = d['generator'] ``` ``` yield edge ``` ```def unconstrained_bridge_augmentation(G): ``` ``` """Finds an optimal 2-edge-augmentation of G using the fewest edges. ``` ``` ``` ``` This is an implementation of the algorithm detailed in _. ``` ``` The basic idea is to construct a meta-graph of bridge-ccs, connect leaf ``` ``` nodes of the trees to connect the entire graph, and finally connect the ``` ``` leafs of the tree in dfs-preorder to bridge connect the entire graph. ``` ``` ``` ``` Parameters ``` ``` ---------- ``` ``` G : NetworkX graph ``` ``` An undirected graph. ``` ``` ``` ``` Yields ``` ``` ------ ``` ``` edge : tuple ``` ``` Edges in the bridge augmentation of G ``` ``` ``` ``` Notes ``` ``` ----- ``` ``` Input: a graph G. ``` ``` First find the bridge components of G and collapse each bridge-cc into a ``` ``` node of a metagraph graph C, which is guaranteed to be a forest of trees. ``` ``` ``` ``` C contains p "leafs" --- nodes with exactly one incident edge. ``` ``` C contains q "isolated nodes" --- nodes with no incident edges. ``` ``` ``` ``` Theorem: If p + q > 1, then at least :math:`ceil(p / 2) + q` edges are ``` ``` needed to bridge connect C. This algorithm achieves this min number. ``` ``` ``` ``` The method first adds enough edges to make G into a tree and then pairs ``` ``` leafs in a simple fashion. ``` ``` ``` ``` Let n be the number of trees in C. Let v(i) be an isolated vertex in the ``` ``` i-th tree if one exists, otherwise it is a pair of distinct leafs nodes ``` ``` in the i-th tree. Alternating edges from these sets (i.e. adding edges ``` ``` A1 = [(v(i), v(i + 1)), v(i + 1), v(i + 2))...]) connects C ``` ``` into a tree T. This tree has p' = p + 2q - 2(n -1) leafs and no isolated ``` ``` vertices. A1 has n - 1 edges. The next step finds ceil(p' / 2) edges to ``` ``` biconnect any tree with p' leafs. ``` ``` ``` ``` Convert T into an arborescence T' by picking an arbitrary root node with ``` ``` degree >= 2 and directing all edges away from the root. Note the ``` ``` implementation implicitly constructs T'. ``` ``` ``` ``` The leafs of T are the nodes with no existing edges in T'. ``` ``` Order the leafs of T' by DFS prorder. Then break this list in half ``` ``` and add the zipped pairs to A2. ``` ``` ``` ``` The set A = A1 + A2 is the minimum augmentation in the metagraph. ``` ``` ``` ``` To convert this to edges in the original graph ``` ``` ``` ``` References ``` ``` ---------- ``` ``` ..  Eswaran, Kapali P., and R. Endre Tarjan. (1975) Augmentation problems. ``` ``` http://epubs.siam.org/doi/abs/10.1137/0205044 ``` ``` ``` ``` See Also ``` ``` -------- ``` ``` :func:`bridge_augmentation` ``` ``` :func:`k_edge_augmentation` ``` ``` ``` ``` Example ``` ``` ------- ``` ``` >>> G = nx.path_graph((1, 2, 3, 4, 5, 6, 7)) ``` ``` >>> sorted(unconstrained_bridge_augmentation(G)) ``` ``` [(1, 7)] ``` ``` >>> G = nx.path_graph((1, 2, 3, 2, 4, 5, 6, 7)) ``` ``` >>> sorted(unconstrained_bridge_augmentation(G)) ``` ``` [(1, 3), (3, 7)] ``` ``` >>> G = nx.Graph([(0, 1), (0, 2), (1, 2)]) ``` ``` >>> G.add_node(4) ``` ``` >>> sorted(unconstrained_bridge_augmentation(G)) ``` ``` [(1, 4), (4, 0)] ``` ``` """ ``` ``` # ----- ``` ``` # Mapping of terms from (Eswaran and Tarjan): ``` ``` # G = G_0 - the input graph ``` ``` # C = G_0' - the bridge condensation of G. (This is a forest of trees) ``` ``` # A1 = A_1 - the edges to connect the forest into a tree ``` ``` # leaf = pendant - a node with degree of 1 ``` ``` # alpha(v) = maps the node v in G to its meta-node in C ``` ``` # beta(x) = maps the meta-node x in C to any node in the bridge ``` ``` # component of G corresponding to x. ``` ``` # find the 2-edge-connected components of G ``` ``` bridge_ccs = list(nx.connectivity.bridge_components(G)) ``` ``` # condense G into an forest C ``` ``` C = collapse(G, bridge_ccs) ``` ``` # Choose pairs of distinct leaf nodes in each tree. If this is not ``` ``` # possible then make a pair using the single isolated node in the tree. ``` ``` vset1 = [ ``` ``` tuple(cc) * 2 # case1: an isolated node ``` ``` if len(cc) == 1 else ``` ``` sorted(cc, key=C.degree)[0:2] # case2: pair of leaf nodes ``` ``` for cc in nx.connected_components(C) ``` ``` ] ``` ``` if len(vset1) > 1: ``` ``` # Use this set to construct edges that connect C into a tree. ``` ``` nodes1 = [vs for vs in vset1] ``` ``` nodes2 = [vs for vs in vset1] ``` ``` A1 = list(zip(nodes1[1:], nodes2)) ``` ``` else: ``` ``` A1 = [] ``` ``` # Connect each tree in the forest to construct an arborescence ``` ``` T = C.copy() ``` ``` T.add_edges_from(A1) ``` ``` # If there are only two leaf nodes, we simply connect them. ``` ``` leafs = [n for n, d in T.degree() if d == 1] ``` ``` if len(leafs) == 1: ``` ``` A2 = [] ``` ``` if len(leafs) == 2: ``` ``` A2 = [tuple(leafs)] ``` ``` else: ``` ``` # Choose an arbitrary non-leaf root ``` ``` try: ``` ``` root = next(n for n, d in T.degree() if d > 1) ``` ``` except StopIteration: # no nodes found with degree > 1 ``` ``` return ``` ``` # order the leaves of C by (induced directed) preorder ``` ``` v2 = [n for n in nx.dfs_preorder_nodes(T, root) if T.degree(n) == 1] ``` ``` # connecting first half of the leafs in pre-order to the second ``` ``` # half will bridge connect the tree with the fewest edges. ``` ``` half = int(math.ceil(len(v2) / 2.0)) ``` ``` A2 = list(zip(v2[:half], v2[-half:])) ``` ``` # collect the edges used to augment the original forest ``` ``` aug_tree_edges = A1 + A2 ``` ``` # Construct the mapping (beta) from meta-nodes to regular nodes ``` ``` inverse = defaultdict(list) ``` ``` for k, v in C.graph['mapping'].items(): ``` ``` inverse[v].append(k) ``` ``` # sort so we choose minimum degree nodes first ``` ``` inverse = {mu: sorted(mapped, key=lambda u: (G.degree(u), u)) ``` ``` for mu, mapped in inverse.items()} ``` ``` # For each meta-edge, map back to an arbitrary pair in the original graph ``` ``` G2 = G.copy() ``` ``` for mu, mv in aug_tree_edges: ``` ``` # Find the first available edge that doesn't exist and return it ``` ``` for u, v in it.product(inverse[mu], inverse[mv]): ``` ``` if not G2.has_edge(u, v): ``` ``` G2.add_edge(u, v) ``` ``` yield u, v ``` ``` break ``` ```def weighted_bridge_augmentation(G, avail, weight=None): ``` ``` """Finds an approximate min-weight 2-edge-augmentation of G. ``` ``` ``` ``` This is an implementation of the approximation algorithm detailed in _. ``` ``` It chooses a set of edges from avail to add to G that renders it ``` ``` 2-edge-connected if such a subset exists. This is done by finding a ``` ``` minimum spanning arborescence of a specially constructed metagraph. ``` ``` ``` ``` Parameters ``` ``` ---------- ``` ``` G : NetworkX graph ``` ``` An undirected graph. ``` ``` ``` ``` avail : set of 2 or 3 tuples. ``` ``` candidate edges (with optional weights) to choose from ``` ``` ``` ``` weight : string ``` ``` key to use to find weights if avail is a set of 3-tuples where the ``` ``` third item in each tuple is a dictionary. ``` ``` ``` ``` Yields ``` ``` ------ ``` ``` edge : tuple ``` ``` Edges in the subset of avail chosen to bridge augment G. ``` ``` ``` ``` Notes ``` ``` ----- ``` ``` Finding a weighted 2-edge-augmentation is NP-hard. ``` ``` Any edge not in ``avail`` is considered to have a weight of infinity. ``` ``` The approximation factor is 2 if ``G`` is connected and 3 if it is not. ``` ``` Runs in :math:`O(m + n log(n))` time ``` ``` ``` ``` References ``` ``` ---------- ``` ``` ..  Khuller, Samir, and Ramakrishna Thurimella. (1993) Approximation ``` ``` algorithms for graph augmentation. ``` ``` http://www.sciencedirect.com/science/article/pii/S0196677483710102 ``` ``` ``` ``` See Also ``` ``` -------- ``` ``` :func:`bridge_augmentation` ``` ``` :func:`k_edge_augmentation` ``` ``` ``` ``` Example ``` ``` ------- ``` ``` >>> G = nx.path_graph((1, 2, 3, 4)) ``` ``` >>> # When the weights are equal, (1, 4) is the best ``` ``` >>> avail = [(1, 4, 1), (1, 3, 1), (2, 4, 1)] ``` ``` >>> sorted(weighted_bridge_augmentation(G, avail)) ``` ``` [(1, 4)] ``` ``` >>> # Giving (1, 4) a high weight makes the two edge solution the best. ``` ``` >>> avail = [(1, 4, 1000), (1, 3, 1), (2, 4, 1)] ``` ``` >>> sorted(weighted_bridge_augmentation(G, avail)) ``` ``` [(1, 3), (2, 4)] ``` ``` >>> #------ ``` ``` >>> G = nx.path_graph((1, 2, 3, 4)) ``` ``` >>> G.add_node(5) ``` ``` >>> avail = [(1, 5, 11), (2, 5, 10), (4, 3, 1), (4, 5, 1)] ``` ``` >>> sorted(weighted_bridge_augmentation(G, avail=avail)) ``` ``` [(1, 5), (4, 5)] ``` ``` >>> avail = [(1, 5, 11), (2, 5, 10), (4, 3, 1), (4, 5, 51)] ``` ``` >>> sorted(weighted_bridge_augmentation(G, avail=avail)) ``` ``` [(1, 5), (2, 5), (4, 5)] ``` ``` """ ``` ``` if weight is None: ``` ``` weight = 'weight' ``` ``` # If input G is not connected the approximation factor increases to 3 ``` ``` if not nx.is_connected(G): ``` ``` H = G.copy() ``` ``` connectors = list(one_edge_augmentation(H, avail=avail, weight=weight)) ``` ``` H.add_edges_from(connectors) ``` ``` for edge in connectors: ``` ``` yield edge ``` ``` else: ``` ``` connectors = [] ``` ``` H = G ``` ``` if len(avail) == 0: ``` ``` if nx.has_bridges(H): ``` ``` raise nx.NetworkXUnfeasible('no augmentation possible') ``` ``` avail_uv, avail_w = _unpack_available_edges(avail, weight=weight, G=H) ``` ``` # Collapse input into a metagraph. Meta nodes are bridge-ccs ``` ``` bridge_ccs = nx.connectivity.bridge_components(H) ``` ``` C = collapse(H, bridge_ccs) ``` ``` # Use the meta graph to shrink avail to a small feasible subset ``` ``` mapping = C.graph['mapping'] ``` ``` # Choose the minimum weight feasible edge in each group ``` ``` meta_to_wuv = { ``` ``` (mu, mv): (w, uv) ``` ``` for (mu, mv), uv, w in _lightest_meta_edges(mapping, avail_uv, avail_w) ``` ``` } ``` ``` # Mapping of terms from (Khuller and Thurimella): ``` ``` # C : G_0 = (V, E^0) ``` ``` # This is the metagraph where each node is a 2-edge-cc in G. ``` ``` # The edges in C represent bridges in the original graph. ``` ``` # (mu, mv) : E - E^0 # they group both avail and given edges in E ``` ``` # T : \Gamma ``` ``` # D : G^D = (V, E_D) ``` ``` # The paper uses ancestor because children point to parents, which is ``` ``` # contrary to networkx standards. So, we actually need to run ``` ``` # nx.least_common_ancestor on the reversed Tree. ``` ``` # Pick an arbitrary leaf from C as the root ``` ``` try: ``` ``` root = next(n for n, d in C.degree() if d == 1) ``` ``` except StopIteration: # no nodes found with degree == 1 ``` ``` return ``` ``` # Root C into a tree TR by directing all edges away from the root ``` ``` # Note in their paper T directs edges towards the root ``` ``` TR = nx.dfs_tree(C, root) ``` ``` # Add to D the directed edges of T and set their weight to zero ``` ``` # This indicates that it costs nothing to use edges that were given. ``` ``` D = nx.reverse(TR).copy() ``` ``` nx.set_edge_attributes(D, name='weight', values=0) ``` ``` # The LCA of mu and mv in T is the shared ancestor of mu and mv that is ``` ``` # located farthest from the root. ``` ``` lca_gen = nx.tree_all_pairs_lowest_common_ancestor( ``` ``` TR, root=root, pairs=meta_to_wuv.keys()) ``` ``` for (mu, mv), lca in lca_gen: ``` ``` w, uv = meta_to_wuv[(mu, mv)] ``` ``` if lca == mu: ``` ``` # If u is an ancestor of v in TR, then add edge u->v to D ``` ``` D.add_edge(lca, mv, weight=w, generator=uv) ``` ``` elif lca == mv: ``` ``` # If v is an ancestor of u in TR, then add edge v->u to D ``` ``` D.add_edge(lca, mu, weight=w, generator=uv) ``` ``` else: ``` ``` # If neither u nor v is a ancestor of the other in TR ``` ``` # let t = lca(TR, u, v) and add edges t->u and t->v ``` ``` # Track the original edge that GENERATED these edges. ``` ``` D.add_edge(lca, mu, weight=w, generator=uv) ``` ``` D.add_edge(lca, mv, weight=w, generator=uv) ``` ``` # Then compute a minimum rooted branching ``` ``` try: ``` ``` # Note the original edges must be directed towards to root for the ``` ``` # branching to give us a bridge-augmentation. ``` ``` A = _minimum_rooted_branching(D, root) ``` ``` except nx.NetworkXException: ``` ``` # If there is no branching then augmentation is not possible ``` ``` raise nx.NetworkXUnfeasible('no 2-edge-augmentation possible') ``` ``` # For each edge e, in the branching that did not belong to the directed ``` ``` # tree T, add the corresponding edge that **GENERATED** it (this is not ``` ``` # necesarilly e itself!) ``` ``` # ensure the third case does not generate edges twice ``` ``` bridge_connectors = set() ``` ``` for mu, mv in A.edges(): ``` ``` data = D.get_edge_data(mu, mv) ``` ``` if 'generator' in data: ``` ``` # Add the avail edge that generated the branching edge. ``` ``` edge = data['generator'] ``` ``` bridge_connectors.add(edge) ``` ``` for edge in bridge_connectors: ``` ``` yield edge ``` ```def _minimum_rooted_branching(D, root): ``` ``` """Helper function to compute a minimum rooted branching (aka rooted ``` ``` arborescence) ``` ``` ``` ``` Before the branching can be computed, the directed graph must be rooted by ``` ``` removing the predecessors of root. ``` ``` ``` ``` A branching / arborescence of rooted graph G is a subgraph that contains a ``` ``` directed path from the root to every other vertex. It is the directed ``` ``` analog of the minimum spanning tree problem. ``` ``` ``` ``` References ``` ``` ---------- ``` ```  Khuller, Samir (2002) Advanced Algorithms Lecture 24 Notes. ``` ``` https://www.cs.umd.edu/class/spring2011/cmsc651/lec07.pdf ``` ``` """ ``` ``` rooted = D.copy() ``` ``` # root the graph by removing all predecessors to `root`. ``` ``` rooted.remove_edges_from([(u, root) for u in D.predecessors(root)]) ``` ``` # Then compute the branching / arborescence. ``` ``` A = nx.minimum_spanning_arborescence(rooted) ``` ``` return A ``` ```def collapse(G, grouped_nodes): ``` ``` """Collapses each group of nodes into a single node. ``` ``` ``` ``` This is similar to condensation, but works on undirected graphs. ``` ``` ``` ``` Parameters ``` ``` ---------- ``` ``` G : NetworkX Graph ``` ``` ``` ``` grouped_nodes: list or generator ``` ``` Grouping of nodes to collapse. The grouping must be disjoint. ``` ``` If grouped_nodes are strongly_connected_components then this is ``` ``` equivalent to :func:`condensation`. ``` ``` ``` ``` Returns ``` ``` ------- ``` ``` C : NetworkX Graph ``` ``` The collapsed graph C of G with respect to the node grouping. The node ``` ``` labels are integers corresponding to the index of the component in the ``` ``` list of grouped_nodes. C has a graph attribute named 'mapping' with a ``` ``` dictionary mapping the original nodes to the nodes in C to which they ``` ``` belong. Each node in C also has a node attribute 'members' with the set ``` ``` of original nodes in G that form the group that the node in C ``` ``` represents. ``` ``` ``` ``` Examples ``` ``` -------- ``` ``` >>> # Collapses a graph using disjoint groups, but not necesarilly connected ``` ``` >>> G = nx.Graph([(1, 0), (2, 3), (3, 1), (3, 4), (4, 5), (5, 6), (5, 7)]) ``` ``` >>> G.add_node('A') ``` ``` >>> grouped_nodes = [{0, 1, 2, 3}, {5, 6, 7}] ``` ``` >>> C = collapse(G, grouped_nodes) ``` ``` >>> members = nx.get_node_attributes(C, 'members') ``` ``` >>> sorted(members.keys()) ``` ``` [0, 1, 2, 3] ``` ``` >>> member_values = set(map(frozenset, members.values())) ``` ``` >>> assert {0, 1, 2, 3} in member_values ``` ``` >>> assert {4} in member_values ``` ``` >>> assert {5, 6, 7} in member_values ``` ``` >>> assert {'A'} in member_values ``` ``` """ ``` ``` mapping = {} ``` ``` members = {} ``` ``` C = G.__class__() ``` ``` i = 0 # required if G is empty ``` ``` remaining = set(G.nodes()) ``` ``` for i, group in enumerate(grouped_nodes): ``` ``` group = set(group) ``` ``` assert remaining.issuperset(group), ( ``` ``` 'grouped nodes must exist in G and be disjoint') ``` ``` remaining.difference_update(group) ``` ``` members[i] = group ``` ``` mapping.update((n, i) for n in group) ``` ``` # remaining nodes are in their own group ``` ``` for i, node in enumerate(remaining, start=i + 1): ``` ``` group = set([node]) ``` ``` members[i] = group ``` ``` mapping.update((n, i) for n in group) ``` ``` number_of_groups = i + 1 ``` ``` C.add_nodes_from(range(number_of_groups)) ``` ``` C.add_edges_from((mapping[u], mapping[v]) for u, v in G.edges() ``` ``` if mapping[u] != mapping[v]) ``` ``` # Add a list of members (ie original nodes) to each node (ie scc) in C. ``` ``` nx.set_node_attributes(C, name='members', values=members) ``` ``` # Add mapping dict as graph attribute ``` ``` C.graph['mapping'] = mapping ``` ``` return C ``` ```def complement_edges(G): ``` ``` """Returns only the edges in the complement of G ``` ``` ``` ``` Parameters ``` ``` ---------- ``` ``` G : NetworkX Graph ``` ``` ``` ``` Yields ``` ``` ------ ``` ``` edge : tuple ``` ``` Edges in the complement of G ``` ``` ``` ``` Example ``` ``` ------- ``` ``` >>> G = nx.path_graph((1, 2, 3, 4)) ``` ``` >>> sorted(complement_edges(G)) ``` ``` [(1, 3), (1, 4), (2, 4)] ``` ``` >>> G = nx.path_graph((1, 2, 3, 4), nx.DiGraph()) ``` ``` >>> sorted(complement_edges(G)) ``` ``` [(1, 3), (1, 4), (2, 1), (2, 4), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)] ``` ``` >>> G = nx.complete_graph(1000) ``` ``` >>> sorted(complement_edges(G)) ``` ``` [] ``` ``` """ ``` ``` if G.is_directed(): ``` ``` for u, v in it.combinations(G.nodes(), 2): ``` ``` if v not in G.adj[u]: ``` ``` yield (u, v) ``` ``` if u not in G.adj[v]: ``` ``` yield (v, u) ``` ``` else: ``` ``` for u, v in it.combinations(G.nodes(), 2): ``` ``` if v not in G.adj[u]: ``` ``` yield (u, v) ``` ```if sys.version_info == 2: ``` ``` def _compat_shuffle(rng, input): ``` ``` """ ``` ``` python2 workaround so shuffle works the same as python3 ``` ``` ``` ``` References ``` ``` ---------- ``` ``` https://stackoverflow.com/questions/38943038/diff-shuffle-py2-py3 ``` ``` """ ``` ``` def _randbelow(n): ``` ``` "Return a random int in the range [0,n). Raises ValueError if n==0." ``` ``` getrandbits = rng.getrandbits ``` ``` k = n.bit_length() # don't use (n-1) here because n can be 1 ``` ``` r = getrandbits(k) # 0 <= r < 2**k ``` ``` while r >= n: ``` ``` r = getrandbits(k) ``` ``` return r ``` ``` for i in range(len(input) - 1, 0, -1): ``` ``` # pick an element in input[:i+1] with which to exchange input[i] ``` ``` j = _randbelow(i + 1) ``` ``` input[i], input[j] = input[j], input[i] ``` ```else: ``` ``` def _compat_shuffle(rng, input): ``` ``` """wrapper around rng.shuffle for python 2 compatibility reasons""" ``` ``` rng.shuffle(input) ``` ```@py_random_state(4) ``` ```@not_implemented_for('multigraph') ``` ```@not_implemented_for('directed') ``` ```def greedy_k_edge_augmentation(G, k, avail=None, weight=None, seed=None): ``` ``` """Greedy algorithm for finding a k-edge-augmentation ``` ``` ``` ``` Parameters ``` ``` ---------- ``` ``` G : NetworkX graph ``` ``` An undirected graph. ``` ``` ``` ``` k : integer ``` ``` Desired edge connectivity ``` ``` ``` ``` avail : dict or a set of 2 or 3 tuples ``` ``` For more details, see :func:`k_edge_augmentation`. ``` ``` ``` ``` weight : string ``` ``` key to use to find weights if ``avail`` is a set of 3-tuples. ``` ``` For more details, see :func:`k_edge_augmentation`. ``` ``` ``` ``` seed : integer, random_state, or None (default) ``` ``` Indicator of random number generation state. ``` ``` See :ref:`Randomness`. ``` ``` ``` ``` Yields ``` ``` ------ ``` ``` edge : tuple ``` ``` Edges in the greedy augmentation of G ``` ``` ``` ``` Notes ``` ``` ----- ``` ``` The algorithm is simple. Edges are incrementally added between parts of the ``` ``` graph that are not yet locally k-edge-connected. Then edges are from the ``` ``` augmenting set are pruned as long as local-edge-connectivity is not broken. ``` ``` ``` ``` This algorithm is greedy and does not provide optimality guarantees. It ``` ``` exists only to provide :func:`k_edge_augmentation` with the ability to ``` ``` generate a feasible solution for arbitrary k. ``` ``` ``` ``` See Also ``` ``` -------- ``` ``` :func:`k_edge_augmentation` ``` ``` ``` ``` Example ``` ``` ------- ``` ``` >>> G = nx.path_graph((1, 2, 3, 4, 5, 6, 7)) ``` ``` >>> sorted(greedy_k_edge_augmentation(G, k=2)) ``` ``` [(1, 7)] ``` ``` >>> sorted(greedy_k_edge_augmentation(G, k=1, avail=[])) ``` ``` [] ``` ``` >>> G = nx.path_graph((1, 2, 3, 4, 5, 6, 7)) ``` ``` >>> avail = {(u, v): 1 for (u, v) in complement_edges(G)} ``` ``` >>> # randomized pruning process can produce different solutions ``` ``` >>> sorted(greedy_k_edge_augmentation(G, k=4, avail=avail, seed=2)) ``` ``` [(1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (2, 4), (2, 6), (3, 7), (5, 7)] ``` ``` >>> sorted(greedy_k_edge_augmentation(G, k=4, avail=avail, seed=3)) ``` ``` [(1, 3), (1, 5), (1, 6), (2, 4), (2, 6), (3, 7), (4, 7), (5, 7)] ``` ``` """ ``` ``` # Result set ``` ``` aug_edges = [] ``` ``` done = is_k_edge_connected(G, k) ``` ``` if done: ``` ``` return ``` ``` if avail is None: ``` ``` # all edges are available ``` ``` avail_uv = list(complement_edges(G)) ``` ``` avail_w =  * len(avail_uv) ``` ``` else: ``` ``` # Get the unique set of unweighted edges ``` ``` avail_uv, avail_w = _unpack_available_edges(avail, weight=weight, G=G) ``` ``` # Greedy: order lightest edges. Use degree sum to tie-break ``` ``` tiebreaker = [sum(map(G.degree, uv)) for uv in avail_uv] ``` ``` avail_wduv = sorted(zip(avail_w, tiebreaker, avail_uv)) ``` ``` avail_uv = [uv for w, d, uv in avail_wduv] ``` ``` # Incrementally add edges in until we are k-connected ``` ``` H = G.copy() ``` ``` for (u, v) in avail_uv: ``` ``` done = False ``` ``` if not is_locally_k_edge_connected(H, u, v, k=k): ``` ``` # Only add edges in parts that are not yet locally k-edge-connected ``` ``` aug_edges.append((u, v)) ``` ``` H.add_edge(u, v) ``` ``` # Did adding this edge help? ``` ``` if H.degree(u) >= k and H.degree(v) >= k: ``` ``` done = is_k_edge_connected(H, k) ``` ``` if done: ``` ``` break ``` ``` # Check for feasibility ``` ``` if not done: ``` ``` raise nx.NetworkXUnfeasible( ``` ``` 'not able to k-edge-connect with available edges') ``` ``` # Randomized attempt to reduce the size of the solution ``` ``` _compat_shuffle(seed, aug_edges) ``` ``` for (u, v) in list(aug_edges): ``` ``` # Don't remove if we know it would break connectivity ``` ``` if H.degree(u) <= k or H.degree(v) <= k: ``` ``` continue ``` ``` H.remove_edge(u, v) ``` ``` aug_edges.remove((u, v)) ``` ``` if not is_k_edge_connected(H, k=k): ``` ``` # If removing this edge breaks feasibility, undo ``` ``` H.add_edge(u, v) ``` ``` aug_edges.append((u, v)) ``` ``` # Generate results ``` ``` for edge in aug_edges: ``` ``` yield edge ```