| # -*- coding: utf-8 -*- |
| """ |
| Flow based connectivity algorithms |
| """ |
| import itertools |
| import networkx as nx |
| |
| __author__ = '\n'.join(['Jordi Torrents <jtorrents@milnou.net>']) |
| |
| __all__ = [ 'average_node_connectivity', |
| 'local_node_connectivity', |
| 'node_connectivity', |
| 'local_edge_connectivity', |
| 'edge_connectivity', |
| 'all_pairs_node_connectivity_matrix', |
| 'dominating_set', |
| ] |
| |
| def average_node_connectivity(G): |
| r"""Returns the average connectivity of a graph G. |
| |
| The average connectivity `\bar{\kappa}` of a graph G is the average |
| of local node connectivity over all pairs of nodes of G [1]_ . |
| |
| .. math:: |
| |
| \bar{\kappa}(G) = \frac{\sum_{u,v} \kappa_{G}(u,v)}{{n \choose 2}} |
| |
| Parameters |
| ---------- |
| |
| G : NetworkX graph |
| Undirected graph |
| |
| Returns |
| ------- |
| K : float |
| Average node connectivity |
| |
| See also |
| -------- |
| local_node_connectivity |
| node_connectivity |
| local_edge_connectivity |
| edge_connectivity |
| max_flow |
| ford_fulkerson |
| |
| References |
| ---------- |
| .. [1] Beineke, L., O. Oellermann, and R. Pippert (2002). The average |
| connectivity of a graph. Discrete mathematics 252(1-3), 31-45. |
| http://www.sciencedirect.com/science/article/pii/S0012365X01001807 |
| |
| """ |
| if G.is_directed(): |
| iter_func = itertools.permutations |
| else: |
| iter_func = itertools.combinations |
| |
| H, mapping = _aux_digraph_node_connectivity(G) |
| num = 0. |
| den = 0. |
| for u,v in iter_func(G, 2): |
| den += 1 |
| num += local_node_connectivity(G, u, v, aux_digraph=H, mapping=mapping) |
| |
| if den == 0: # Null Graph |
| return 0 |
| return num/den |
| |
| def _aux_digraph_node_connectivity(G): |
| r""" Creates a directed graph D from an undirected graph G to compute flow |
| based node connectivity. |
| |
| For an undirected graph G having `n` nodes and `m` edges we derive a |
| directed graph D with 2n nodes and 2m+n arcs by replacing each |
| original node `v` with two nodes `vA`,`vB` linked by an (internal) |
| arc in D. Then for each edge (u,v) in G we add two arcs (uB,vA) |
| and (vB,uA) in D. Finally we set the attribute capacity = 1 for each |
| arc in D [1]. |
| |
| For a directed graph having `n` nodes and `m` arcs we derive a |
| directed graph D with 2n nodes and m+n arcs by replacing each |
| original node `v` with two nodes `vA`,`vB` linked by an (internal) |
| arc `(vA,vB)` in D. Then for each arc (u,v) in G we add one arc (uB,vA) |
| in D. Finally we set the attribute capacity = 1 for each arc in D. |
| |
| References |
| ---------- |
| .. [1] Kammer, Frank and Hanjo Taubig. Graph Connectivity. in Brandes and |
| Erlebach, 'Network Analysis: Methodological Foundations', Lecture |
| Notes in Computer Science, Volume 3418, Springer-Verlag, 2005. |
| http://www.informatik.uni-augsburg.de/thi/personen/kammer/Graph_Connectivity.pdf |
| |
| """ |
| directed = G.is_directed() |
| |
| mapping = {} |
| D = nx.DiGraph() |
| for i,node in enumerate(G): |
| mapping[node] = i |
| D.add_node('%dA' % i,id=node) |
| D.add_node('%dB' % i,id=node) |
| D.add_edge('%dA' % i, '%dB' % i, capacity=1) |
| |
| edges = [] |
| for (source, target) in G.edges(): |
| edges.append(('%sB' % mapping[source], '%sA' % mapping[target])) |
| if not directed: |
| edges.append(('%sB' % mapping[target], '%sA' % mapping[source])) |
| |
| D.add_edges_from(edges, capacity=1) |
| return D, mapping |
| |
| def local_node_connectivity(G, s, t, aux_digraph=None, mapping=None): |
| r"""Computes local node connectivity for nodes s and t. |
| |
| Local node connectivity for two non adjacent nodes s and t is the |
| minimum number of nodes that must be removed (along with their incident |
| edges) to disconnect them. |
| |
| This is a flow based implementation of node connectivity. We compute the |
| maximum flow on an auxiliary digraph build from the original input |
| graph (see below for details). This is equal to the local node |
| connectivity because the value of a maximum s-t-flow is equal to the |
| capacity of a minimum s-t-cut (Ford and Fulkerson theorem) [1]_ . |
| |
| Parameters |
| ---------- |
| G : NetworkX graph |
| Undirected graph |
| |
| s : node |
| Source node |
| |
| t : node |
| Target node |
| |
| aux_digraph : NetworkX DiGraph (default=None) |
| Auxiliary digraph to compute flow based node connectivity. If None |
| the auxiliary digraph is build. |
| |
| mapping : dict (default=None) |
| Dictionary with a mapping of node names in G and in the auxiliary digraph. |
| |
| Returns |
| ------- |
| K : integer |
| local node connectivity for nodes s and t |
| |
| Examples |
| -------- |
| >>> # Platonic icosahedral graph has node connectivity 5 |
| >>> # for each non adjacent node pair |
| >>> G = nx.icosahedral_graph() |
| >>> nx.local_node_connectivity(G,0,6) |
| 5 |
| |
| Notes |
| ----- |
| This is a flow based implementation of node connectivity. We compute the |
| maximum flow using the Ford and Fulkerson algorithm on an auxiliary digraph |
| build from the original input graph: |
| |
| For an undirected graph G having `n` nodes and `m` edges we derive a |
| directed graph D with 2n nodes and 2m+n arcs by replacing each |
| original node `v` with two nodes `v_A`, `v_B` linked by an (internal) |
| arc in `D`. Then for each edge (`u`, `v`) in G we add two arcs |
| (`u_B`, `v_A`) and (`v_B`, `u_A`) in `D`. Finally we set the attribute |
| capacity = 1 for each arc in `D` [1]_ . |
| |
| For a directed graph G having `n` nodes and `m` arcs we derive a |
| directed graph `D` with `2n` nodes and `m+n` arcs by replacing each |
| original node `v` with two nodes `v_A`, `v_B` linked by an (internal) |
| arc `(v_A, v_B)` in D. Then for each arc `(u,v)` in G we add one arc |
| `(u_B,v_A)` in `D`. Finally we set the attribute capacity = 1 for |
| each arc in `D`. |
| |
| This is equal to the local node connectivity because the value of |
| a maximum s-t-flow is equal to the capacity of a minimum s-t-cut (Ford |
| and Fulkerson theorem). |
| |
| See also |
| -------- |
| node_connectivity |
| all_pairs_node_connectivity_matrix |
| local_edge_connectivity |
| edge_connectivity |
| max_flow |
| ford_fulkerson |
| |
| References |
| ---------- |
| .. [1] Kammer, Frank and Hanjo Taubig. Graph Connectivity. in Brandes and |
| Erlebach, 'Network Analysis: Methodological Foundations', Lecture |
| Notes in Computer Science, Volume 3418, Springer-Verlag, 2005. |
| http://www.informatik.uni-augsburg.de/thi/personen/kammer/Graph_Connectivity.pdf |
| |
| """ |
| if aux_digraph is None or mapping is None: |
| H, mapping = _aux_digraph_node_connectivity(G) |
| else: |
| H = aux_digraph |
| return nx.max_flow(H,'%sB' % mapping[s], '%sA' % mapping[t]) |
| |
| def node_connectivity(G, s=None, t=None): |
| r"""Returns node connectivity for a graph or digraph G. |
| |
| Node connectivity is equal to the minimum number of nodes that |
| must be removed to disconnect G or render it trivial. If source |
| and target nodes are provided, this function returns the local node |
| connectivity: the minimum number of nodes that must be removed to break |
| all paths from source to target in G. |
| |
| This is a flow based implementation. The algorithm is based in |
| solving a number of max-flow problems (ie local st-node connectivity, |
| see local_node_connectivity) to determine the capacity of the |
| minimum cut on an auxiliary directed network that corresponds to the |
| minimum node cut of G. It handles both directed and undirected graphs. |
| |
| Parameters |
| ---------- |
| G : NetworkX graph |
| Undirected graph |
| |
| s : node |
| Source node. Optional (default=None) |
| |
| t : node |
| Target node. Optional (default=None) |
| |
| Returns |
| ------- |
| K : integer |
| Node connectivity of G, or local node connectivity if source |
| and target were provided |
| |
| Examples |
| -------- |
| >>> # Platonic icosahedral graph is 5-node-connected |
| >>> G = nx.icosahedral_graph() |
| >>> nx.node_connectivity(G) |
| 5 |
| >>> nx.node_connectivity(G, 3, 7) |
| 5 |
| |
| Notes |
| ----- |
| This is a flow based implementation of node connectivity. The |
| algorithm works by solving `O((n-\delta-1+\delta(\delta-1)/2)` max-flow |
| problems on an auxiliary digraph. Where `\delta` is the minimum degree |
| of G. For details about the auxiliary digraph and the computation of |
| local node connectivity see local_node_connectivity. |
| |
| This implementation is based on algorithm 11 in [1]_. We use the Ford |
| and Fulkerson algorithm to compute max flow (see ford_fulkerson). |
| |
| See also |
| -------- |
| local_node_connectivity |
| all_pairs_node_connectivity_matrix |
| local_edge_connectivity |
| edge_connectivity |
| max_flow |
| ford_fulkerson |
| |
| References |
| ---------- |
| .. [1] Abdol-Hossein Esfahanian. Connectivity Algorithms. |
| http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf |
| |
| """ |
| # Local node connectivity |
| if s is not None and t is not None: |
| if s not in G: |
| raise nx.NetworkXError('node %s not in graph' % s) |
| if t not in G: |
| raise nx.NetworkXError('node %s not in graph' % t) |
| return local_node_connectivity(G, s, t) |
| # Global node connectivity |
| if G.is_directed(): |
| if not nx.is_weakly_connected(G): |
| return 0 |
| iter_func = itertools.permutations |
| # I think that it is necessary to consider both predecessors |
| # and successors for directed graphs |
| def neighbors(v): |
| return itertools.chain.from_iterable([G.predecessors_iter(v), |
| G.successors_iter(v)]) |
| else: |
| if not nx.is_connected(G): |
| return 0 |
| iter_func = itertools.combinations |
| neighbors = G.neighbors_iter |
| # Initial guess \kappa = n - 1 |
| K = G.order()-1 |
| deg = G.degree() |
| min_deg = min(deg.values()) |
| v = next(n for n,d in deg.items() if d==min_deg) |
| # Reuse the auxiliary digraph |
| H, mapping = _aux_digraph_node_connectivity(G) |
| # compute local node connectivity with all non-neighbors nodes |
| for w in set(G) - set(neighbors(v)) - set([v]): |
| K = min(K, local_node_connectivity(G, v, w, |
| aux_digraph=H, mapping=mapping)) |
| # Same for non adjacent pairs of neighbors of v |
| for x,y in iter_func(neighbors(v), 2): |
| if y in G[x]: continue |
| K = min(K, local_node_connectivity(G, x, y, |
| aux_digraph=H, mapping=mapping)) |
| return K |
| |
| def all_pairs_node_connectivity_matrix(G): |
| """Return a numpy 2d ndarray with node connectivity between all pairs |
| of nodes. |
| |
| Parameters |
| ---------- |
| G : NetworkX graph |
| Undirected graph |
| |
| Returns |
| ------- |
| K : 2d numpy ndarray |
| node connectivity between all pairs of nodes. |
| |
| See also |
| -------- |
| local_node_connectivity |
| node_connectivity |
| local_edge_connectivity |
| edge_connectivity |
| max_flow |
| ford_fulkerson |
| |
| """ |
| try: |
| import numpy |
| except ImportError: |
| raise ImportError(\ |
| "all_pairs_node_connectivity_matrix() requires NumPy") |
| |
| n = G.order() |
| M = numpy.zeros((n, n), dtype=int) |
| # Create auxiliary Digraph |
| D, mapping = _aux_digraph_node_connectivity(G) |
| |
| if G.is_directed(): |
| for u, v in itertools.permutations(G, 2): |
| K = local_node_connectivity(G, u, v, aux_digraph=D, mapping=mapping) |
| M[mapping[u],mapping[v]] = K |
| else: |
| for u, v in itertools.combinations(G, 2): |
| K = local_node_connectivity(G, u, v, aux_digraph=D, mapping=mapping) |
| M[mapping[u],mapping[v]] = M[mapping[v],mapping[u]] = K |
| |
| return M |
| |
| def _aux_digraph_edge_connectivity(G): |
| """Auxiliary digraph for computing flow based edge connectivity |
| |
| If the input graph is undirected, we replace each edge (u,v) with |
| two reciprocal arcs (u,v) and (v,u) and then we set the attribute |
| 'capacity' for each arc to 1. If the input graph is directed we simply |
| add the 'capacity' attribute. Part of algorithm 1 in [1]_ . |
| |
| References |
| ---------- |
| .. [1] Abdol-Hossein Esfahanian. Connectivity Algorithms. (this is a |
| chapter, look for the reference of the book). |
| http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf |
| """ |
| if G.is_directed(): |
| if nx.get_edge_attributes(G, 'capacity'): |
| return G |
| D = G.copy() |
| capacity = dict((e,1) for e in D.edges()) |
| nx.set_edge_attributes(D, 'capacity', capacity) |
| return D |
| else: |
| D = G.to_directed() |
| capacity = dict((e,1) for e in D.edges()) |
| nx.set_edge_attributes(D, 'capacity', capacity) |
| return D |
| |
| def local_edge_connectivity(G, u, v, aux_digraph=None): |
| r"""Returns local edge connectivity for nodes s and t in G. |
| |
| Local edge connectivity for two nodes s and t is the minimum number |
| of edges that must be removed to disconnect them. |
| |
| This is a flow based implementation of edge connectivity. We compute the |
| maximum flow on an auxiliary digraph build from the original |
| network (see below for details). This is equal to the local edge |
| connectivity because the value of a maximum s-t-flow is equal to the |
| capacity of a minimum s-t-cut (Ford and Fulkerson theorem) [1]_ . |
| |
| Parameters |
| ---------- |
| G : NetworkX graph |
| Undirected or directed graph |
| |
| s : node |
| Source node |
| |
| t : node |
| Target node |
| |
| aux_digraph : NetworkX DiGraph (default=None) |
| Auxiliary digraph to compute flow based edge connectivity. If None |
| the auxiliary digraph is build. |
| |
| Returns |
| ------- |
| K : integer |
| local edge connectivity for nodes s and t |
| |
| Examples |
| -------- |
| >>> # Platonic icosahedral graph has edge connectivity 5 |
| >>> # for each non adjacent node pair |
| >>> G = nx.icosahedral_graph() |
| >>> nx.local_edge_connectivity(G,0,6) |
| 5 |
| |
| Notes |
| ----- |
| This is a flow based implementation of edge connectivity. We compute the |
| maximum flow using the Ford and Fulkerson algorithm on an auxiliary digraph |
| build from the original graph: |
| |
| If the input graph is undirected, we replace each edge (u,v) with |
| two reciprocal arcs `(u,v)` and `(v,u)` and then we set the attribute |
| 'capacity' for each arc to 1. If the input graph is directed we simply |
| add the 'capacity' attribute. This is an implementation of algorithm 1 |
| in [1]_. |
| |
| The maximum flow in the auxiliary network is equal to the local edge |
| connectivity because the value of a maximum s-t-flow is equal to the |
| capacity of a minimum s-t-cut (Ford and Fulkerson theorem). |
| |
| See also |
| -------- |
| local_node_connectivity |
| node_connectivity |
| edge_connectivity |
| max_flow |
| ford_fulkerson |
| |
| References |
| ---------- |
| .. [1] Abdol-Hossein Esfahanian. Connectivity Algorithms. |
| http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf |
| |
| """ |
| if aux_digraph is None: |
| H = _aux_digraph_edge_connectivity(G) |
| else: |
| H = aux_digraph |
| return nx.max_flow(H, u, v) |
| |
| def edge_connectivity(G, s=None, t=None): |
| r"""Returns the edge connectivity of the graph or digraph G. |
| |
| The edge connectivity is equal to the minimum number of edges that |
| must be removed to disconnect G or render it trivial. If source |
| and target nodes are provided, this function returns the local edge |
| connectivity: the minimum number of edges that must be removed to |
| break all paths from source to target in G. |
| |
| This is a flow based implementation. The algorithm is based in solving |
| a number of max-flow problems (ie local st-edge connectivity, see |
| local_edge_connectivity) to determine the capacity of the minimum |
| cut on an auxiliary directed network that corresponds to the minimum |
| edge cut of G. It handles both directed and undirected graphs. |
| |
| Parameters |
| ---------- |
| G : NetworkX graph |
| Undirected or directed graph |
| |
| s : node |
| Source node. Optional (default=None) |
| |
| t : node |
| Target node. Optional (default=None) |
| |
| Returns |
| ------- |
| K : integer |
| Edge connectivity for G, or local edge connectivity if source |
| and target were provided |
| |
| Examples |
| -------- |
| >>> # Platonic icosahedral graph is 5-edge-connected |
| >>> G = nx.icosahedral_graph() |
| >>> nx.edge_connectivity(G) |
| 5 |
| |
| Notes |
| ----- |
| This is a flow based implementation of global edge connectivity. For |
| undirected graphs the algorithm works by finding a 'small' dominating |
| set of nodes of G (see algorithm 7 in [1]_ ) and computing local max flow |
| (see local_edge_connectivity) between an arbitrary node in the dominating |
| set and the rest of nodes in it. This is an implementation of |
| algorithm 6 in [1]_ . |
| |
| For directed graphs, the algorithm does n calls to the max flow function. |
| This is an implementation of algorithm 8 in [1]_ . We use the Ford and |
| Fulkerson algorithm to compute max flow (see ford_fulkerson). |
| |
| See also |
| -------- |
| local_node_connectivity |
| node_connectivity |
| local_edge_connectivity |
| max_flow |
| ford_fulkerson |
| |
| References |
| ---------- |
| .. [1] Abdol-Hossein Esfahanian. Connectivity Algorithms. |
| http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf |
| |
| """ |
| # Local edge connectivity |
| if s is not None and t is not None: |
| if s not in G: |
| raise nx.NetworkXError('node %s not in graph' % s) |
| if t not in G: |
| raise nx.NetworkXError('node %s not in graph' % t) |
| return local_edge_connectivity(G, s, t) |
| # Global edge connectivity |
| if G.is_directed(): |
| # Algorithm 8 in [1] |
| if not nx.is_weakly_connected(G): |
| return 0 |
| # initial value for lambda is min degree (\delta(G)) |
| L = min(G.degree().values()) |
| # reuse auxiliary digraph |
| H = _aux_digraph_edge_connectivity(G) |
| nodes = G.nodes() |
| n = len(nodes) |
| for i in range(n): |
| try: |
| L = min(L, local_edge_connectivity(G, nodes[i], |
| nodes[i+1], aux_digraph=H)) |
| except IndexError: # last node! |
| L = min(L, local_edge_connectivity(G, nodes[i], |
| nodes[0], aux_digraph=H)) |
| return L |
| else: # undirected |
| # Algorithm 6 in [1] |
| if not nx.is_connected(G): |
| return 0 |
| # initial value for lambda is min degree (\delta(G)) |
| L = min(G.degree().values()) |
| # reuse auxiliary digraph |
| H = _aux_digraph_edge_connectivity(G) |
| # A dominating set is \lambda-covering |
| # We need a dominating set with at least two nodes |
| for node in G: |
| D = dominating_set(G, start_with=node) |
| v = D.pop() |
| if D: break |
| else: |
| # in complete graphs the dominating sets will always be of one node |
| # thus we return min degree |
| return L |
| for w in D: |
| L = min(L, local_edge_connectivity(G, v, w, aux_digraph=H)) |
| return L |
| |
| def dominating_set(G, start_with=None): |
| # Algorithm 7 in [1] |
| all_nodes = set(G) |
| if start_with is None: |
| v = set(G).pop() # pick a node |
| else: |
| if start_with not in G: |
| raise nx.NetworkXError('node %s not in G' % start_with) |
| v = start_with |
| D = set([v]) |
| ND = set([nbr for nbr in G[v]]) |
| other = all_nodes - ND - D |
| while other: |
| w = other.pop() |
| D.add(w) |
| ND.update([nbr for nbr in G[w] if nbr not in D]) |
| other = all_nodes - ND - D |
| return D |
| |
| def is_dominating_set(G, nbunch): |
| # Proposed by Dan on the mailing list |
| allnodes=set(G) |
| testset=set(n for n in nbunch if n in G) |
| nbrs=set() |
| for n in testset: |
| nbrs.update(G[n]) |
| if nbrs - allnodes: # some nodes left--not dominating |
| return False |
| else: |
| return True |
| |
