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"""
2Provides functions for finding and testing for locally `(k, l)`-connected
3graphs.
5"""
7import copy
9import networkx as nx
11__all__ = ["kl_connected_subgraph", "is_kl_connected"]
14@nx._dispatchable(returns_graph=True)
15def kl_connected_subgraph(G, k, l, low_memory=False, same_as_graph=False):
16 """Returns the maximum locally `(k, l)`-connected subgraph of `G`.
18 A graph is locally `(k, l)`-connected if for each edge `(u, v)` in the
19 graph there are at least `l` edge-disjoint paths of length at most `k`
20 joining `u` to `v`.
22 Parameters
23 ----------
24 G : NetworkX graph
25 The graph in which to find a maximum locally `(k, l)`-connected
26 subgraph.
28 k : integer
29 The maximum length of paths to consider. A higher number means a looser
30 connectivity requirement.
32 l : integer
33 The number of edge-disjoint paths. A higher number means a stricter
34 connectivity requirement.
36 low_memory : bool
37 If this is True, this function uses an algorithm that uses slightly
38 more time but less memory.
40 same_as_graph : bool
41 If True then return a tuple of the form `(H, is_same)`,
42 where `H` is the maximum locally `(k, l)`-connected subgraph and
43 `is_same` is a Boolean representing whether `G` is locally `(k,
44 l)`-connected (and hence, whether `H` is simply a copy of the input
45 graph `G`).
47 Returns
48 -------
49 NetworkX graph or two-tuple
50 If `same_as_graph` is True, then this function returns a
51 two-tuple as described above. Otherwise, it returns only the maximum
52 locally `(k, l)`-connected subgraph.
54 See also
55 --------
56 is_kl_connected
58 References
59 ----------
60 .. [1] Chung, Fan and Linyuan Lu. "The Small World Phenomenon in Hybrid
61 Power Law Graphs." *Complex Networks*. Springer Berlin Heidelberg,
62 2004. 89--104.
64 """
65 H = copy.deepcopy(G) # subgraph we construct by removing from G
67 graphOK = True
68 deleted_some = True # hack to start off the while loop
69 while deleted_some:
70 deleted_some = False
71 # We use `for edge in list(H.edges()):` instead of
72 # `for edge in H.edges():` because we edit the graph `H` in
73 # the loop. Hence using an iterator will result in
74 # `RuntimeError: dictionary changed size during iteration`
75 for edge in list(H.edges()):
76 (u, v) = edge
77 # Get copy of graph needed for this search
78 if low_memory:
79 verts = {u, v}
80 for i in range(k):
81 for w in verts.copy():
82 verts.update(G[w])
83 G2 = G.subgraph(verts).copy()
84 else:
85 G2 = copy.deepcopy(G)
86 ###
87 path = [u, v]
88 cnt = 0
89 accept = 0
90 while path:
91 cnt += 1 # Found a path
92 if cnt >= l:
93 accept = 1
94 break
95 # record edges along this graph
96 prev = u
97 for w in path:
98 if prev != w:
99 G2.remove_edge(prev, w)
100 prev = w
101 # path = shortest_path(G2, u, v, k) # ??? should "Cutoff" be k+1?
102 try:
103 path = nx.shortest_path(G2, u, v) # ??? should "Cutoff" be k+1?
104 except nx.NetworkXNoPath:
105 path = False
106 # No Other Paths
107 if accept == 0:
108 H.remove_edge(u, v)
109 deleted_some = True
110 if graphOK:
111 graphOK = False
112 # We looked through all edges and removed none of them.
113 # So, H is the maximal (k,l)-connected subgraph of G
114 if same_as_graph:
115 return (H, graphOK)
116 return H
119@nx._dispatchable
120def is_kl_connected(G, k, l, low_memory=False):
121 """Returns True if and only if `G` is locally `(k, l)`-connected.
123 A graph is locally `(k, l)`-connected if for each edge `(u, v)` in the
124 graph there are at least `l` edge-disjoint paths of length at most `k`
125 joining `u` to `v`.
127 Parameters
128 ----------
129 G : NetworkX graph
130 The graph to test for local `(k, l)`-connectedness.
132 k : integer
133 The maximum length of paths to consider. A higher number means a looser
134 connectivity requirement.
136 l : integer
137 The number of edge-disjoint paths. A higher number means a stricter
138 connectivity requirement.
140 low_memory : bool
141 If this is True, this function uses an algorithm that uses slightly
142 more time but less memory.
144 Returns
145 -------
146 bool
147 Whether the graph is locally `(k, l)`-connected subgraph.
149 See also
150 --------
151 kl_connected_subgraph
153 References
154 ----------
155 .. [1] Chung, Fan and Linyuan Lu. "The Small World Phenomenon in Hybrid
156 Power Law Graphs." *Complex Networks*. Springer Berlin Heidelberg,
157 2004. 89--104.
159 """
160 graphOK = True
161 for edge in G.edges():
162 (u, v) = edge
163 # Get copy of graph needed for this search
164 if low_memory:
165 verts = {u, v}
166 for i in range(k):
167 [verts.update(G.neighbors(w)) for w in verts.copy()]
168 G2 = G.subgraph(verts)
169 else:
170 G2 = copy.deepcopy(G)
171 ###
172 path = [u, v]
173 cnt = 0
174 accept = 0
175 while path:
176 cnt += 1 # Found a path
177 if cnt >= l:
178 accept = 1
179 break
180 # record edges along this graph
181 prev = u
182 for w in path:
183 if w != prev:
184 G2.remove_edge(prev, w)
185 prev = w
186 # path = shortest_path(G2, u, v, k) # ??? should "Cutoff" be k+1?
187 try:
188 path = nx.shortest_path(G2, u, v) # ??? should "Cutoff" be k+1?
189 except nx.NetworkXNoPath:
190 path = False
191 # No Other Paths
192 if accept == 0:
193 graphOK = False
194 break
195 # return status
196 return graphOK