## iof-tools / networkxMiCe / networkx-master / networkx / linalg / tests / test_algebraic_connectivity.py @ 5cef0f13

History | View | Annotate | Download (11.4 KB)

1 | 5cef0f13 | tiamilani | from math import sqrt |
---|---|---|---|

2 | import networkx as nx |
||

3 | from nose import SkipTest |
||

4 | from nose.tools import * |
||

5 | |||

6 | ```
try:
``` |
||

7 | from scikits.sparse.cholmod import cholesky |
||

8 | _cholesky = cholesky |
||

9 | except ImportError: |
||

10 | ```
_cholesky = None
``` |
||

11 | |||

12 | if _cholesky is None: |
||

13 | methods = ('tracemin_pcg', 'tracemin_lu', 'lanczos', 'lobpcg') |
||

14 | ```
else:
``` |
||

15 | methods = ('tracemin_pcg', 'tracemin_chol', 'tracemin_lu', 'lanczos', 'lobpcg') |
||

16 | |||

17 | |||

18 | def check_eigenvector(A, l, x): |
||

19 | nx = numpy.linalg.norm(x) |
||

20 | ```
# Check zeroness.
``` |
||

21 | ```
assert_not_almost_equal(nx, 0)
``` |
||

22 | y = A * x |
||

23 | ny = numpy.linalg.norm(y) |
||

24 | ```
# Check collinearity.
``` |
||

25 | assert_almost_equal(numpy.dot(x, y), nx * ny) |
||

26 | ```
# Check eigenvalue.
``` |
||

27 | assert_almost_equal(ny, l * nx) |
||

28 | |||

29 | |||

30 | class TestAlgebraicConnectivity(object): |
||

31 | |||

32 | ```
numpy = 1
``` |
||

33 | |||

34 | ```
@classmethod
``` |
||

35 | def setupClass(cls): |
||

36 | ```
global numpy
``` |
||

37 | ```
try:
``` |
||

38 | import numpy.linalg |
||

39 | import scipy.sparse |
||

40 | except ImportError: |
||

41 | raise SkipTest('SciPy not available.') |
||

42 | |||

43 | def test_directed(self): |
||

44 | G = nx.DiGraph() |
||

45 | for method in self._methods: |
||

46 | assert_raises(nx.NetworkXNotImplemented, nx.algebraic_connectivity, |
||

47 | G, method=method) |
||

48 | assert_raises(nx.NetworkXNotImplemented, nx.fiedler_vector, G, |
||

49 | method=method) |
||

50 | |||

51 | def test_null_and_singleton(self): |
||

52 | G = nx.Graph() |
||

53 | for method in self._methods: |
||

54 | assert_raises(nx.NetworkXError, nx.algebraic_connectivity, G, |
||

55 | method=method) |
||

56 | assert_raises(nx.NetworkXError, nx.fiedler_vector, G, |
||

57 | method=method) |
||

58 | G.add_edge(0, 0) |
||

59 | for method in self._methods: |
||

60 | assert_raises(nx.NetworkXError, nx.algebraic_connectivity, G, |
||

61 | method=method) |
||

62 | assert_raises(nx.NetworkXError, nx.fiedler_vector, G, |
||

63 | method=method) |
||

64 | |||

65 | def test_disconnected(self): |
||

66 | G = nx.Graph() |
||

67 | G.add_nodes_from(range(2)) |
||

68 | for method in self._methods: |
||

69 | ```
assert_equal(nx.algebraic_connectivity(G), 0)
``` |
||

70 | assert_raises(nx.NetworkXError, nx.fiedler_vector, G, |
||

71 | method=method) |
||

72 | G.add_edge(0, 1, weight=0) |
||

73 | for method in self._methods: |
||

74 | ```
assert_equal(nx.algebraic_connectivity(G), 0)
``` |
||

75 | assert_raises(nx.NetworkXError, nx.fiedler_vector, G, |
||

76 | method=method) |
||

77 | |||

78 | def test_unrecognized_method(self): |
||

79 | ```
G = nx.path_graph(4)
``` |
||

80 | assert_raises(nx.NetworkXError, nx.algebraic_connectivity, G, |
||

81 | ```
method='unknown')
``` |
||

82 | ```
assert_raises(nx.NetworkXError, nx.fiedler_vector, G, method='unknown')
``` |
||

83 | |||

84 | def test_two_nodes(self): |
||

85 | G = nx.Graph() |
||

86 | G.add_edge(0, 1, weight=1) |
||

87 | A = nx.laplacian_matrix(G) |
||

88 | for method in self._methods: |
||

89 | assert_almost_equal(nx.algebraic_connectivity( |
||

90 | G, tol=1e-12, method=method), 2) |
||

91 | ```
x = nx.fiedler_vector(G, tol=1e-12, method=method)
``` |
||

92 | ```
check_eigenvector(A, 2, x)
``` |
||

93 | G = nx.MultiGraph() |
||

94 | G.add_edge(0, 0, spam=1e8) |
||

95 | G.add_edge(0, 1, spam=1) |
||

96 | G.add_edge(0, 1, spam=-2) |
||

97 | A = -3 * nx.laplacian_matrix(G, weight='spam') |
||

98 | for method in self._methods: |
||

99 | assert_almost_equal(nx.algebraic_connectivity( |
||

100 | G, weight='spam', tol=1e-12, method=method), 6) |
||

101 | x = nx.fiedler_vector(G, weight='spam', tol=1e-12, method=method) |
||

102 | ```
check_eigenvector(A, 6, x)
``` |
||

103 | |||

104 | def test_abbreviation_of_method(self): |
||

105 | ```
G = nx.path_graph(8)
``` |
||

106 | A = nx.laplacian_matrix(G) |
||

107 | sigma = 2 - sqrt(2 + sqrt(2)) |
||

108 | ac = nx.algebraic_connectivity(G, tol=1e-12, method='tracemin') |
||

109 | assert_almost_equal(ac, sigma) |
||

110 | x = nx.fiedler_vector(G, tol=1e-12, method='tracemin') |
||

111 | check_eigenvector(A, sigma, x) |
||

112 | |||

113 | def test_path(self): |
||

114 | ```
G = nx.path_graph(8)
``` |
||

115 | A = nx.laplacian_matrix(G) |
||

116 | sigma = 2 - sqrt(2 + sqrt(2)) |
||

117 | for method in self._methods: |
||

118 | ```
ac = nx.algebraic_connectivity(G, tol=1e-12, method=method)
``` |
||

119 | assert_almost_equal(ac, sigma) |
||

120 | ```
x = nx.fiedler_vector(G, tol=1e-12, method=method)
``` |
||

121 | check_eigenvector(A, sigma, x) |
||

122 | |||

123 | def test_problematic_graph_issue_2381(self): |
||

124 | ```
G = nx.path_graph(4)
``` |
||

125 | G.add_edges_from([(4, 2), (5, 1)]) |
||

126 | A = nx.laplacian_matrix(G) |
||

127 | ```
sigma = 0.438447187191
``` |
||

128 | for method in self._methods: |
||

129 | ```
ac = nx.algebraic_connectivity(G, tol=1e-12, method=method)
``` |
||

130 | assert_almost_equal(ac, sigma) |
||

131 | ```
x = nx.fiedler_vector(G, tol=1e-12, method=method)
``` |
||

132 | check_eigenvector(A, sigma, x) |
||

133 | |||

134 | def test_cycle(self): |
||

135 | ```
G = nx.cycle_graph(8)
``` |
||

136 | A = nx.laplacian_matrix(G) |
||

137 | sigma = 2 - sqrt(2) |
||

138 | for method in self._methods: |
||

139 | ```
ac = nx.algebraic_connectivity(G, tol=1e-12, method=method)
``` |
||

140 | assert_almost_equal(ac, sigma) |
||

141 | ```
x = nx.fiedler_vector(G, tol=1e-12, method=method)
``` |
||

142 | check_eigenvector(A, sigma, x) |
||

143 | |||

144 | def test_seed_argument(self): |
||

145 | ```
G = nx.cycle_graph(8)
``` |
||

146 | A = nx.laplacian_matrix(G) |
||

147 | sigma = 2 - sqrt(2) |
||

148 | for method in self._methods: |
||

149 | ac = nx.algebraic_connectivity(G, tol=1e-12, method=method, seed=1) |
||

150 | assert_almost_equal(ac, sigma) |
||

151 | x = nx.fiedler_vector(G, tol=1e-12, method=method, seed=1) |
||

152 | check_eigenvector(A, sigma, x) |
||

153 | |||

154 | def test_buckminsterfullerene(self): |
||

155 | G = nx.Graph( |
||

156 | [(1, 10), (1, 41), (1, 59), (2, 12), (2, 42), (2, 60), (3, 6), |
||

157 | (3, 43), (3, 57), (4, 8), (4, 44), (4, 58), (5, 13), (5, 56), |
||

158 | (5, 57), (6, 10), (6, 31), (7, 14), (7, 56), (7, 58), (8, 12), |
||

159 | (8, 32), (9, 23), (9, 53), (9, 59), (10, 15), (11, 24), (11, 53), |
||

160 | (11, 60), (12, 16), (13, 14), (13, 25), (14, 26), (15, 27), |
||

161 | (15, 49), (16, 28), (16, 50), (17, 18), (17, 19), (17, 54), |
||

162 | (18, 20), (18, 55), (19, 23), (19, 41), (20, 24), (20, 42), |
||

163 | (21, 31), (21, 33), (21, 57), (22, 32), (22, 34), (22, 58), |
||

164 | (23, 24), (25, 35), (25, 43), (26, 36), (26, 44), (27, 51), |
||

165 | (27, 59), (28, 52), (28, 60), (29, 33), (29, 34), (29, 56), |
||

166 | (30, 51), (30, 52), (30, 53), (31, 47), (32, 48), (33, 45), |
||

167 | (34, 46), (35, 36), (35, 37), (36, 38), (37, 39), (37, 49), |
||

168 | (38, 40), (38, 50), (39, 40), (39, 51), (40, 52), (41, 47), |
||

169 | (42, 48), (43, 49), (44, 50), (45, 46), (45, 54), (46, 55), |
||

170 | (47, 54), (48, 55)]) |
||

171 | for normalized in (False, True): |
||

172 | if not normalized: |
||

173 | A = nx.laplacian_matrix(G) |
||

174 | ```
sigma = 0.2434017461399311
``` |
||

175 | ```
else:
``` |
||

176 | A = nx.normalized_laplacian_matrix(G) |
||

177 | ```
sigma = 0.08113391537997749
``` |
||

178 | for method in methods: |
||

179 | ```
try:
``` |
||

180 | assert_almost_equal(nx.algebraic_connectivity( |
||

181 | ```
G, normalized=normalized, tol=1e-12, method=method),
``` |
||

182 | sigma) |
||

183 | ```
x = nx.fiedler_vector(G, normalized=normalized, tol=1e-12,
``` |
||

184 | method=method) |
||

185 | check_eigenvector(A, sigma, x) |
||

186 | except nx.NetworkXError as e: |
||

187 | if e.args not in (('Cholesky solver unavailable.',), |
||

188 | ```
('LU solver unavailable.',)):
``` |
||

189 | ```
raise
``` |
||

190 | |||

191 | _methods = methods |
||

192 | |||

193 | |||

194 | class TestSpectralOrdering(object): |
||

195 | |||

196 | ```
numpy = 1
``` |
||

197 | |||

198 | ```
@classmethod
``` |
||

199 | def setupClass(cls): |
||

200 | ```
global numpy
``` |
||

201 | ```
try:
``` |
||

202 | import numpy.linalg |
||

203 | import scipy.sparse |
||

204 | except ImportError: |
||

205 | raise SkipTest('SciPy not available.') |
||

206 | |||

207 | def test_nullgraph(self): |
||

208 | for graph in (nx.Graph, nx.DiGraph, nx.MultiGraph, nx.MultiDiGraph): |
||

209 | G = graph() |
||

210 | assert_raises(nx.NetworkXError, nx.spectral_ordering, G) |
||

211 | |||

212 | def test_singleton(self): |
||

213 | for graph in (nx.Graph, nx.DiGraph, nx.MultiGraph, nx.MultiDiGraph): |
||

214 | G = graph() |
||

215 | ```
G.add_node('x')
``` |
||

216 | ```
assert_equal(nx.spectral_ordering(G), ['x'])
``` |
||

217 | G.add_edge('x', 'x', weight=33) |
||

218 | G.add_edge('x', 'x', weight=33) |
||

219 | ```
assert_equal(nx.spectral_ordering(G), ['x'])
``` |
||

220 | |||

221 | def test_unrecognized_method(self): |
||

222 | ```
G = nx.path_graph(4)
``` |
||

223 | assert_raises(nx.NetworkXError, nx.spectral_ordering, G, |
||

224 | ```
method='unknown')
``` |
||

225 | |||

226 | def test_three_nodes(self): |
||

227 | G = nx.Graph() |
||

228 | G.add_weighted_edges_from([(1, 2, 1), (1, 3, 2), (2, 3, 1)], |
||

229 | ```
weight='spam')
``` |
||

230 | for method in self._methods: |
||

231 | ```
order = nx.spectral_ordering(G, weight='spam', method=method)
``` |
||

232 | assert_equal(set(order), set(G)) |
||

233 | ok_(set([1, 3]) in (set(order[:-1]), set(order[1:]))) |
||

234 | G = nx.MultiDiGraph() |
||

235 | G.add_weighted_edges_from([(1, 2, 1), (1, 3, 2), (2, 3, 1), (2, 3, 2)]) |
||

236 | for method in self._methods: |
||

237 | order = nx.spectral_ordering(G, method=method) |
||

238 | assert_equal(set(order), set(G)) |
||

239 | ok_(set([2, 3]) in (set(order[:-1]), set(order[1:]))) |
||

240 | |||

241 | def test_path(self): |
||

242 | ```
# based on setupClass numpy is installed if we get here
``` |
||

243 | from numpy.random import shuffle |
||

244 | path = list(range(10)) |
||

245 | shuffle(path) |
||

246 | G = nx.Graph() |
||

247 | nx.add_path(G, path) |
||

248 | for method in self._methods: |
||

249 | order = nx.spectral_ordering(G, method=method) |
||

250 | ok_(order in [path, list(reversed(path))]) |
||

251 | |||

252 | def test_seed_argument(self): |
||

253 | ```
# based on setupClass numpy is installed if we get here
``` |
||

254 | from numpy.random import shuffle |
||

255 | path = list(range(10)) |
||

256 | shuffle(path) |
||

257 | G = nx.Graph() |
||

258 | nx.add_path(G, path) |
||

259 | for method in self._methods: |
||

260 | ```
order = nx.spectral_ordering(G, method=method, seed=1)
``` |
||

261 | ok_(order in [path, list(reversed(path))]) |
||

262 | |||

263 | def test_disconnected(self): |
||

264 | G = nx.Graph() |
||

265 | nx.add_path(G, range(0, 10, 2)) |
||

266 | nx.add_path(G, range(1, 10, 2)) |
||

267 | for method in self._methods: |
||

268 | order = nx.spectral_ordering(G, method=method) |
||

269 | assert_equal(set(order), set(G)) |
||

270 | seqs = [list(range(0, 10, 2)), list(range(8, -1, -2)), |
||

271 | list(range(1, 10, 2)), list(range(9, -1, -2))] |
||

272 | ok_(order[:5] in seqs) |
||

273 | ok_(order[5:] in seqs) |
||

274 | |||

275 | def test_cycle(self): |
||

276 | path = list(range(10)) |
||

277 | G = nx.Graph() |
||

278 | ```
nx.add_path(G, path, weight=5)
``` |
||

279 | G.add_edge(path[-1], path[0], weight=1) |
||

280 | A = nx.laplacian_matrix(G).todense() |
||

281 | for normalized in (False, True): |
||

282 | for method in methods: |
||

283 | ```
try:
``` |
||

284 | order = nx.spectral_ordering(G, normalized=normalized, |
||

285 | method=method) |
||

286 | except nx.NetworkXError as e: |
||

287 | if e.args not in (('Cholesky solver unavailable.',), |
||

288 | ```
('LU solver unavailable.',)):
``` |
||

289 | ```
raise
``` |
||

290 | ```
else:
``` |
||

291 | if not normalized: |
||

292 | ok_(order in [[1, 2, 0, 3, 4, 5, 6, 9, 7, 8], |
||

293 | [8, 7, 9, 6, 5, 4, 3, 0, 2, 1]]) |
||

294 | ```
else:
``` |
||

295 | ok_(order in [[1, 2, 3, 0, 4, 5, 9, 6, 7, 8], |
||

296 | [8, 7, 6, 9, 5, 4, 0, 3, 2, 1]]) |
||

297 | |||

298 | _methods = methods |