Statistics
| Branch: | Revision:

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

 1 ```# -*- coding: utf-8 -*- ``` ```# Copyright (C) 2004-2019 by ``` ```# Aric Hagberg ``` ```# Dan Schult ``` ```# Pieter Swart ``` ```# All rights reserved. ``` ```# BSD license. ``` ```# ``` ```# Authors: Aric Hagberg (hagberg@lanl.gov) and Dan Schult (dschult@colgate.edu) ``` ```# ``` ```""" ``` ```Provides functions for finding and testing for locally `(k, l)`-connected ``` ```graphs. ``` ``` ``` ```""" ``` ```import copy ``` ```import networkx as nx ``` ```__all__ = ['kl_connected_subgraph', 'is_kl_connected'] ``` ```def kl_connected_subgraph(G, k, l, low_memory=False, same_as_graph=False): ``` ``` """Returns the maximum locally `(k, l)`-connected subgraph of `G`. ``` ``` ``` ``` A graph is locally `(k, l)`-connected if for each edge `(u, v)` in the ``` ``` graph there are at least `l` edge-disjoint paths of length at most `k` ``` ``` joining `u` to `v`. ``` ``` ``` ``` Parameters ``` ``` ---------- ``` ``` G : NetworkX graph ``` ``` The graph in which to find a maximum locally `(k, l)`-connected ``` ``` subgraph. ``` ``` ``` ``` k : integer ``` ``` The maximum length of paths to consider. A higher number means a looser ``` ``` connectivity requirement. ``` ``` ``` ``` l : integer ``` ``` The number of edge-disjoint paths. A higher number means a stricter ``` ``` connectivity requirement. ``` ``` ``` ``` low_memory : bool ``` ``` If this is True, this function uses an algorithm that uses slightly ``` ``` more time but less memory. ``` ``` ``` ``` same_as_graph : bool ``` ``` If True then return a tuple of the form `(H, is_same)`, ``` ``` where `H` is the maximum locally `(k, l)`-connected subgraph and ``` ``` `is_same` is a Boolean representing whether `G` is locally `(k, ``` ``` l)`-connected (and hence, whether `H` is simply a copy of the input ``` ``` graph `G`). ``` ``` ``` ``` Returns ``` ``` ------- ``` ``` NetworkX graph or two-tuple ``` ``` If `same_as_graph` is True, then this function returns a ``` ``` two-tuple as described above. Otherwise, it returns only the maximum ``` ``` locally `(k, l)`-connected subgraph. ``` ``` ``` ``` See also ``` ``` -------- ``` ``` is_kl_connected ``` ``` ``` ``` References ``` ``` ---------- ``` ``` .. : Chung, Fan and Linyuan Lu. "The Small World Phenomenon in Hybrid ``` ``` Power Law Graphs." *Complex Networks*. Springer Berlin Heidelberg, ``` ``` 2004. 89--104. ``` ``` ``` ``` """ ``` ``` H = copy.deepcopy(G) # subgraph we construct by removing from G ``` ``` graphOK = True ``` ``` deleted_some = True # hack to start off the while loop ``` ``` while deleted_some: ``` ``` deleted_some = False ``` ``` # We use `for edge in list(H.edges()):` instead of ``` ``` # `for edge in H.edges():` because we edit the graph `H` in ``` ``` # the loop. Hence using an iterator will result in ``` ``` # `RuntimeError: dictionary changed size during iteration` ``` ``` for edge in list(H.edges()): ``` ``` (u, v) = edge ``` ``` # Get copy of graph needed for this search ``` ``` if low_memory: ``` ``` verts = set([u, v]) ``` ``` for i in range(k): ``` ``` for w in verts.copy(): ``` ``` verts.update(G[w]) ``` ``` G2 = G.subgraph(verts).copy() ``` ``` else: ``` ``` G2 = copy.deepcopy(G) ``` ``` ### ``` ``` path = [u, v] ``` ``` cnt = 0 ``` ``` accept = 0 ``` ``` while path: ``` ``` cnt += 1 # Found a path ``` ``` if cnt >= l: ``` ``` accept = 1 ``` ``` break ``` ``` # record edges along this graph ``` ``` prev = u ``` ``` for w in path: ``` ``` if prev != w: ``` ``` G2.remove_edge(prev, w) ``` ``` prev = w ``` ```# path = shortest_path(G2, u, v, k) # ??? should "Cutoff" be k+1? ``` ``` try: ``` ``` path = nx.shortest_path(G2, u, v) # ??? should "Cutoff" be k+1? ``` ``` except nx.NetworkXNoPath: ``` ``` path = False ``` ``` # No Other Paths ``` ``` if accept == 0: ``` ``` H.remove_edge(u, v) ``` ``` deleted_some = True ``` ``` if graphOK: ``` ``` graphOK = False ``` ``` # We looked through all edges and removed none of them. ``` ``` # So, H is the maximal (k,l)-connected subgraph of G ``` ``` if same_as_graph: ``` ``` return (H, graphOK) ``` ``` return H ``` ```def is_kl_connected(G, k, l, low_memory=False): ``` ``` """Returns True if and only if `G` is locally `(k, l)`-connected. ``` ``` ``` ``` A graph is locally `(k, l)`-connected if for each edge `(u, v)` in the ``` ``` graph there are at least `l` edge-disjoint paths of length at most `k` ``` ``` joining `u` to `v`. ``` ``` ``` ``` Parameters ``` ``` ---------- ``` ``` G : NetworkX graph ``` ``` The graph to test for local `(k, l)`-connectedness. ``` ``` ``` ``` k : integer ``` ``` The maximum length of paths to consider. A higher number means a looser ``` ``` connectivity requirement. ``` ``` ``` ``` l : integer ``` ``` The number of edge-disjoint paths. A higher number means a stricter ``` ``` connectivity requirement. ``` ``` ``` ``` low_memory : bool ``` ``` If this is True, this function uses an algorithm that uses slightly ``` ``` more time but less memory. ``` ``` ``` ``` Returns ``` ``` ------- ``` ``` bool ``` ``` Whether the graph is locally `(k, l)`-connected subgraph. ``` ``` ``` ``` See also ``` ``` -------- ``` ``` kl_connected_subgraph ``` ``` ``` ``` References ``` ``` ---------- ``` ``` .. : Chung, Fan and Linyuan Lu. "The Small World Phenomenon in Hybrid ``` ``` Power Law Graphs." *Complex Networks*. Springer Berlin Heidelberg, ``` ``` 2004. 89--104. ``` ``` ``` ``` """ ``` ``` graphOK = True ``` ``` for edge in G.edges(): ``` ``` (u, v) = edge ``` ``` # Get copy of graph needed for this search ``` ``` if low_memory: ``` ``` verts = set([u, v]) ``` ``` for i in range(k): ``` ``` [verts.update(G.neighbors(w)) for w in verts.copy()] ``` ``` G2 = G.subgraph(verts) ``` ``` else: ``` ``` G2 = copy.deepcopy(G) ``` ``` ### ``` ``` path = [u, v] ``` ``` cnt = 0 ``` ``` accept = 0 ``` ``` while path: ``` ``` cnt += 1 # Found a path ``` ``` if cnt >= l: ``` ``` accept = 1 ``` ``` break ``` ``` # record edges along this graph ``` ``` prev = u ``` ``` for w in path: ``` ``` if w != prev: ``` ``` G2.remove_edge(prev, w) ``` ``` prev = w ``` ```# path = shortest_path(G2, u, v, k) # ??? should "Cutoff" be k+1? ``` ``` try: ``` ``` path = nx.shortest_path(G2, u, v) # ??? should "Cutoff" be k+1? ``` ``` except nx.NetworkXNoPath: ``` ``` path = False ``` ``` # No Other Paths ``` ``` if accept == 0: ``` ``` graphOK = False ``` ``` break ``` ``` # return status ``` ``` return graphOK ```