1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
|
"""
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
----------
.. [1] 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 = {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
----------
.. [1] 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 = {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
|
