ioftools / networkxMiCe / networkxmaster / networkx / algorithms / hybrid.py @ 5cef0f13
History  View  Annotate  Download (6.29 KB)
1 
# * coding: utf8 *


2 
# Copyright (C) 20042019 by

3 
# Aric Hagberg <hagberg@lanl.gov>

4 
# Dan Schult <dschult@colgate.edu>

5 
# Pieter Swart <swart@lanl.gov>

6 
# All rights reserved.

7 
# BSD license.

8 
#

9 
# Authors: Aric Hagberg (hagberg@lanl.gov) and Dan Schult (dschult@colgate.edu)

10 
#

11 
"""

12 
Provides functions for finding and testing for locally `(k, l)`connected

13 
graphs.

14 

15 
"""

16 
import copy 
17 
import networkx as nx 
18  
19 
__all__ = ['kl_connected_subgraph', 'is_kl_connected'] 
20  
21  
22 
def kl_connected_subgraph(G, k, l, low_memory=False, same_as_graph=False): 
23 
"""Returns the maximum locally `(k, l)`connected subgraph of `G`.

24 

25 
A graph is locally `(k, l)`connected if for each edge `(u, v)` in the

26 
graph there are at least `l` edgedisjoint paths of length at most `k`

27 
joining `u` to `v`.

28 

29 
Parameters

30 


31 
G : NetworkX graph

32 
The graph in which to find a maximum locally `(k, l)`connected

33 
subgraph.

34 

35 
k : integer

36 
The maximum length of paths to consider. A higher number means a looser

37 
connectivity requirement.

38 

39 
l : integer

40 
The number of edgedisjoint paths. A higher number means a stricter

41 
connectivity requirement.

42 

43 
low_memory : bool

44 
If this is True, this function uses an algorithm that uses slightly

45 
more time but less memory.

46 

47 
same_as_graph : bool

48 
If True then return a tuple of the form `(H, is_same)`,

49 
where `H` is the maximum locally `(k, l)`connected subgraph and

50 
`is_same` is a Boolean representing whether `G` is locally `(k,

51 
l)`connected (and hence, whether `H` is simply a copy of the input

52 
graph `G`).

53 

54 
Returns

55 


56 
NetworkX graph or twotuple

57 
If `same_as_graph` is True, then this function returns a

58 
twotuple as described above. Otherwise, it returns only the maximum

59 
locally `(k, l)`connected subgraph.

60 

61 
See also

62 


63 
is_kl_connected

64 

65 
References

66 


67 
.. [1]: Chung, Fan and Linyuan Lu. "The Small World Phenomenon in Hybrid

68 
Power Law Graphs." *Complex Networks*. Springer Berlin Heidelberg,

69 
2004. 89104.

70 

71 
"""

72 
H = copy.deepcopy(G) # subgraph we construct by removing from G

73  
74 
graphOK = True

75 
deleted_some = True # hack to start off the while loop 
76 
while deleted_some:

77 
deleted_some = False

78 
# We use `for edge in list(H.edges()):` instead of

79 
# `for edge in H.edges():` because we edit the graph `H` in

80 
# the loop. Hence using an iterator will result in

81 
# `RuntimeError: dictionary changed size during iteration`

82 
for edge in list(H.edges()): 
83 
(u, v) = edge 
84 
# Get copy of graph needed for this search

85 
if low_memory:

86 
verts = set([u, v])

87 
for i in range(k): 
88 
for w in verts.copy(): 
89 
verts.update(G[w]) 
90 
G2 = G.subgraph(verts).copy() 
91 
else:

92 
G2 = copy.deepcopy(G) 
93 
###

94 
path = [u, v] 
95 
cnt = 0

96 
accept = 0

97 
while path:

98 
cnt += 1 # Found a path 
99 
if cnt >= l:

100 
accept = 1

101 
break

102 
# record edges along this graph

103 
prev = u 
104 
for w in path: 
105 
if prev != w:

106 
G2.remove_edge(prev, w) 
107 
prev = w 
108 
# path = shortest_path(G2, u, v, k) # ??? should "Cutoff" be k+1?

109 
try:

110 
path = nx.shortest_path(G2, u, v) # ??? should "Cutoff" be k+1?

111 
except nx.NetworkXNoPath:

112 
path = False

113 
# No Other Paths

114 
if accept == 0: 
115 
H.remove_edge(u, v) 
116 
deleted_some = True

117 
if graphOK:

118 
graphOK = False

119 
# We looked through all edges and removed none of them.

120 
# So, H is the maximal (k,l)connected subgraph of G

121 
if same_as_graph:

122 
return (H, graphOK)

123 
return H

124  
125  
126 
def is_kl_connected(G, k, l, low_memory=False): 
127 
"""Returns True if and only if `G` is locally `(k, l)`connected.

128 

129 
A graph is locally `(k, l)`connected if for each edge `(u, v)` in the

130 
graph there are at least `l` edgedisjoint paths of length at most `k`

131 
joining `u` to `v`.

132 

133 
Parameters

134 


135 
G : NetworkX graph

136 
The graph to test for local `(k, l)`connectedness.

137 

138 
k : integer

139 
The maximum length of paths to consider. A higher number means a looser

140 
connectivity requirement.

141 

142 
l : integer

143 
The number of edgedisjoint paths. A higher number means a stricter

144 
connectivity requirement.

145 

146 
low_memory : bool

147 
If this is True, this function uses an algorithm that uses slightly

148 
more time but less memory.

149 

150 
Returns

151 


152 
bool

153 
Whether the graph is locally `(k, l)`connected subgraph.

154 

155 
See also

156 


157 
kl_connected_subgraph

158 

159 
References

160 


161 
.. [1]: Chung, Fan and Linyuan Lu. "The Small World Phenomenon in Hybrid

162 
Power Law Graphs." *Complex Networks*. Springer Berlin Heidelberg,

163 
2004. 89104.

164 

165 
"""

166 
graphOK = True

167 
for edge in G.edges(): 
168 
(u, v) = edge 
169 
# Get copy of graph needed for this search

170 
if low_memory:

171 
verts = set([u, v])

172 
for i in range(k): 
173 
[verts.update(G.neighbors(w)) for w in verts.copy()] 
174 
G2 = G.subgraph(verts) 
175 
else:

176 
G2 = copy.deepcopy(G) 
177 
###

178 
path = [u, v] 
179 
cnt = 0

180 
accept = 0

181 
while path:

182 
cnt += 1 # Found a path 
183 
if cnt >= l:

184 
accept = 1

185 
break

186 
# record edges along this graph

187 
prev = u 
188 
for w in path: 
189 
if w != prev:

190 
G2.remove_edge(prev, w) 
191 
prev = w 
192 
# path = shortest_path(G2, u, v, k) # ??? should "Cutoff" be k+1?

193 
try:

194 
path = nx.shortest_path(G2, u, v) # ??? should "Cutoff" be k+1?

195 
except nx.NetworkXNoPath:

196 
path = False

197 
# No Other Paths

198 
if accept == 0: 
199 
graphOK = False

200 
break

201 
# return status

202 
return graphOK
