Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/hybrid.py: 9%

1""" 

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

3graphs. 

4 

5""" 

6import copy 

7 

8import networkx as nx 

9 

10__all__ = ["kl_connected_subgraph", "is_kl_connected"] 

11 

12 

13@nx._dispatch 

14def kl_connected_subgraph(G, k, l, low_memory=False, same_as_graph=False): 

15 """Returns the maximum locally `(k, l)`-connected subgraph of `G`. 

16 

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

18 graph there are at least `l` edge-disjoint paths of length at most `k` 

19 joining `u` to `v`. 

20 

21 Parameters 

22 ---------- 

23 G : NetworkX graph 

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

25 subgraph. 

26 

27 k : integer 

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

29 connectivity requirement. 

30 

31 l : integer 

32 The number of edge-disjoint paths. A higher number means a stricter 

33 connectivity requirement. 

34 

35 low_memory : bool 

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

37 more time but less memory. 

38 

39 same_as_graph : bool 

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

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

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

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

44 graph `G`). 

45 

46 Returns 

47 ------- 

48 NetworkX graph or two-tuple 

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

50 two-tuple as described above. Otherwise, it returns only the maximum 

51 locally `(k, l)`-connected subgraph. 

52 

53 See also 

54 -------- 

55 is_kl_connected 

56 

57 References 

58 ---------- 

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

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

61 2004. 89--104. 

62 

63 """ 

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

65 

66 graphOK = True 

67 deleted_some = True # hack to start off the while loop 

68 while deleted_some: 

69 deleted_some = False 

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

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

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

73 # `RuntimeError: dictionary changed size during iteration` 

74 for edge in list(H.edges()): 

75 (u, v) = edge 

76 # Get copy of graph needed for this search 

77 if low_memory: 

78 verts = {u, v} 

79 for i in range(k): 

80 for w in verts.copy(): 

81 verts.update(G[w]) 

82 G2 = G.subgraph(verts).copy() 

83 else: 

84 G2 = copy.deepcopy(G) 

85 ### 

86 path = [u, v] 

87 cnt = 0 

88 accept = 0 

89 while path: 

90 cnt += 1 # Found a path 

91 if cnt >= l: 

92 accept = 1 

93 break 

94 # record edges along this graph 

95 prev = u 

96 for w in path: 

97 if prev != w: 

98 G2.remove_edge(prev, w) 

99 prev = w 

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

101 try: 

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

103 except nx.NetworkXNoPath: 

104 path = False 

105 # No Other Paths 

106 if accept == 0: 

107 H.remove_edge(u, v) 

108 deleted_some = True 

109 if graphOK: 

110 graphOK = False 

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

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

113 if same_as_graph: 

114 return (H, graphOK) 

115 return H 

116 

117 

118@nx._dispatch 

119def is_kl_connected(G, k, l, low_memory=False): 

120 """Returns True if and only if `G` is locally `(k, l)`-connected. 

121 

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

123 graph there are at least `l` edge-disjoint paths of length at most `k` 

124 joining `u` to `v`. 

125 

126 Parameters 

127 ---------- 

128 G : NetworkX graph 

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

130 

131 k : integer 

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

133 connectivity requirement. 

134 

135 l : integer 

136 The number of edge-disjoint paths. A higher number means a stricter 

137 connectivity requirement. 

138 

139 low_memory : bool 

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

141 more time but less memory. 

142 

143 Returns 

144 ------- 

145 bool 

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

147 

148 See also 

149 -------- 

150 kl_connected_subgraph 

151 

152 References 

153 ---------- 

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

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

156 2004. 89--104. 

157 

158 """ 

159 graphOK = True 

160 for edge in G.edges(): 

161 (u, v) = edge 

162 # Get copy of graph needed for this search 

163 if low_memory: 

164 verts = {u, v} 

165 for i in range(k): 

166 [verts.update(G.neighbors(w)) for w in verts.copy()] 

167 G2 = G.subgraph(verts) 

168 else: 

169 G2 = copy.deepcopy(G) 

170 ### 

171 path = [u, v] 

172 cnt = 0 

173 accept = 0 

174 while path: 

175 cnt += 1 # Found a path 

176 if cnt >= l: 

177 accept = 1 

178 break 

179 # record edges along this graph 

180 prev = u 

181 for w in path: 

182 if w != prev: 

183 G2.remove_edge(prev, w) 

184 prev = w 

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

186 try: 

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

188 except nx.NetworkXNoPath: 

189 path = False 

190 # No Other Paths 

191 if accept == 0: 

192 graphOK = False 

193 break 

194 # return status 

195 return graphOK