## iof-tools / networkxMiCe / networkx-master / networkx / algorithms / tests / test_matching.py @ 5cef0f13

History | View | Annotate | Download (14 KB)

1 | 5cef0f13 | tiamilani | from itertools import permutations |
---|---|---|---|

2 | import math |
||

3 | |||

4 | from nose.tools import assert_equal |
||

5 | from nose.tools import assert_false |
||

6 | from nose.tools import assert_true |
||

7 | import networkx as nx |
||

8 | from networkx.algorithms.matching import matching_dict_to_set |
||

9 | from networkx.testing import assert_edges_equal |
||

10 | |||

11 | |||

12 | class TestMaxWeightMatching(object): |
||

13 | ```
"""Unit tests for the
``` |
||

14 | ```
:func:`~networkx.algorithms.matching.max_weight_matching` function.
``` |
||

15 | ```
``` |
||

16 | ```
"""
``` |
||

17 | |||

18 | def test_trivial1(self): |
||

19 | ```
"""Empty graph"""
``` |
||

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

21 | ```
assert_equal(nx.max_weight_matching(G), set())
``` |
||

22 | |||

23 | def test_trivial2(self): |
||

24 | ```
"""Self loop"""
``` |
||

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

26 | G.add_edge(0, 0, weight=100) |
||

27 | ```
assert_equal(nx.max_weight_matching(G), set())
``` |
||

28 | |||

29 | def test_trivial3(self): |
||

30 | ```
"""Single edge"""
``` |
||

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

32 | G.add_edge(0, 1) |
||

33 | assert_edges_equal(nx.max_weight_matching(G), |
||

34 | matching_dict_to_set({0: 1, 1: 0})) |
||

35 | |||

36 | def test_trivial4(self): |
||

37 | ```
"""Small graph"""
``` |
||

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

39 | G.add_edge('one', 'two', weight=10) |
||

40 | G.add_edge('two', 'three', weight=11) |
||

41 | assert_edges_equal(nx.max_weight_matching(G), |
||

42 | matching_dict_to_set({'three': 'two', 'two': 'three'})) |
||

43 | |||

44 | def test_trivial5(self): |
||

45 | ```
"""Path"""
``` |
||

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

47 | G.add_edge(1, 2, weight=5) |
||

48 | G.add_edge(2, 3, weight=11) |
||

49 | G.add_edge(3, 4, weight=5) |
||

50 | assert_edges_equal(nx.max_weight_matching(G), |
||

51 | matching_dict_to_set({2: 3, 3: 2})) |
||

52 | ```
assert_edges_equal(nx.max_weight_matching(G, 1),
``` |
||

53 | matching_dict_to_set({1: 2, 2: 1, 3: 4, 4: 3})) |
||

54 | |||

55 | def test_trivial6(self): |
||

56 | ```
"""Small graph with arbitrary weight attribute"""
``` |
||

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

58 | G.add_edge('one', 'two', weight=10, abcd=11) |
||

59 | G.add_edge('two', 'three', weight=11, abcd=10) |
||

60 | ```
assert_edges_equal(nx.max_weight_matching(G, weight='abcd'),
``` |
||

61 | matching_dict_to_set({'one': 'two', 'two': 'one'})) |
||

62 | |||

63 | def test_floating_point_weights(self): |
||

64 | ```
"""Floating point weights"""
``` |
||

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

66 | G.add_edge(1, 2, weight=math.pi) |
||

67 | G.add_edge(2, 3, weight=math.exp(1)) |
||

68 | G.add_edge(1, 3, weight=3.0) |
||

69 | G.add_edge(1, 4, weight=math.sqrt(2.0)) |
||

70 | assert_edges_equal(nx.max_weight_matching(G), |
||

71 | matching_dict_to_set({1: 4, 2: 3, 3: 2, 4: 1})) |
||

72 | |||

73 | def test_negative_weights(self): |
||

74 | ```
"""Negative weights"""
``` |
||

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

76 | G.add_edge(1, 2, weight=2) |
||

77 | G.add_edge(1, 3, weight=-2) |
||

78 | G.add_edge(2, 3, weight=1) |
||

79 | G.add_edge(2, 4, weight=-1) |
||

80 | G.add_edge(3, 4, weight=-6) |
||

81 | assert_edges_equal(nx.max_weight_matching(G), |
||

82 | matching_dict_to_set({1: 2, 2: 1})) |
||

83 | ```
assert_edges_equal(nx.max_weight_matching(G, 1),
``` |
||

84 | matching_dict_to_set({1: 3, 2: 4, 3: 1, 4: 2})) |
||

85 | |||

86 | def test_s_blossom(self): |
||

87 | ```
"""Create S-blossom and use it for augmentation:"""
``` |
||

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

89 | G.add_weighted_edges_from([(1, 2, 8), (1, 3, 9), |
||

90 | (2, 3, 10), (3, 4, 7)]) |
||

91 | assert_edges_equal(nx.max_weight_matching(G), |
||

92 | matching_dict_to_set({1: 2, 2: 1, 3: 4, 4: 3})) |
||

93 | |||

94 | G.add_weighted_edges_from([(1, 6, 5), (4, 5, 6)]) |
||

95 | assert_edges_equal(nx.max_weight_matching(G), |
||

96 | matching_dict_to_set({1: 6, 2: 3, 3: 2, 4: 5, 5: 4, 6: 1})) |
||

97 | |||

98 | def test_s_t_blossom(self): |
||

99 | ```
"""Create S-blossom, relabel as T-blossom, use for augmentation:"""
``` |
||

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

101 | G.add_weighted_edges_from([(1, 2, 9), (1, 3, 8), (2, 3, 10), |
||

102 | (1, 4, 5), (4, 5, 4), (1, 6, 3)]) |
||

103 | assert_edges_equal(nx.max_weight_matching(G), |
||

104 | matching_dict_to_set({1: 6, 2: 3, 3: 2, 4: 5, 5: 4, 6: 1})) |
||

105 | G.add_edge(4, 5, weight=3) |
||

106 | G.add_edge(1, 6, weight=4) |
||

107 | assert_edges_equal(nx.max_weight_matching(G), |
||

108 | matching_dict_to_set({1: 6, 2: 3, 3: 2, 4: 5, 5: 4, 6: 1})) |
||

109 | G.remove_edge(1, 6) |
||

110 | G.add_edge(3, 6, weight=4) |
||

111 | assert_edges_equal(nx.max_weight_matching(G), |
||

112 | matching_dict_to_set({1: 2, 2: 1, 3: 6, 4: 5, 5: 4, 6: 3})) |
||

113 | |||

114 | def test_nested_s_blossom(self): |
||

115 | ```
"""Create nested S-blossom, use for augmentation:"""
``` |
||

116 | |||

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

118 | G.add_weighted_edges_from([(1, 2, 9), (1, 3, 9), (2, 3, 10), |
||

119 | (2, 4, 8), (3, 5, 8), (4, 5, 10), |
||

120 | (5, 6, 6)]) |
||

121 | assert_equal(nx.max_weight_matching(G), |
||

122 | matching_dict_to_set({1: 3, 2: 4, 3: 1, 4: 2, 5: 6, 6: 5})) |
||

123 | |||

124 | def test_nested_s_blossom_relabel(self): |
||

125 | ```
"""Create S-blossom, relabel as S, include in nested S-blossom:"""
``` |
||

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

127 | G.add_weighted_edges_from([(1, 2, 10), (1, 7, 10), (2, 3, 12), |
||

128 | (3, 4, 20), (3, 5, 20), (4, 5, 25), |
||

129 | (5, 6, 10), (6, 7, 10), (7, 8, 8)]) |
||

130 | assert_edges_equal(nx.max_weight_matching(G), |
||

131 | matching_dict_to_set({1: 2, 2: 1, 3: 4, 4: 3, 5: 6, 6: 5, 7: 8, 8: 7})) |
||

132 | |||

133 | def test_nested_s_blossom_expand(self): |
||

134 | ```
"""Create nested S-blossom, augment, expand recursively:"""
``` |
||

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

136 | G.add_weighted_edges_from([(1, 2, 8), (1, 3, 8), (2, 3, 10), |
||

137 | (2, 4, 12), (3, 5, 12), (4, 5, 14), |
||

138 | (4, 6, 12), (5, 7, 12), (6, 7, 14), |
||

139 | (7, 8, 12)]) |
||

140 | assert_edges_equal(nx.max_weight_matching(G), |
||

141 | matching_dict_to_set({1: 2, 2: 1, 3: 5, 4: 6, 5: 3, 6: 4, 7: 8, 8: 7})) |
||

142 | |||

143 | def test_s_blossom_relabel_expand(self): |
||

144 | ```
"""Create S-blossom, relabel as T, expand:"""
``` |
||

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

146 | G.add_weighted_edges_from([(1, 2, 23), (1, 5, 22), (1, 6, 15), |
||

147 | (2, 3, 25), (3, 4, 22), (4, 5, 25), |
||

148 | (4, 8, 14), (5, 7, 13)]) |
||

149 | assert_edges_equal(nx.max_weight_matching(G), |
||

150 | matching_dict_to_set({1: 6, 2: 3, 3: 2, 4: 8, 5: 7, 6: 1, 7: 5, 8: 4})) |
||

151 | |||

152 | def test_nested_s_blossom_relabel_expand(self): |
||

153 | ```
"""Create nested S-blossom, relabel as T, expand:"""
``` |
||

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

155 | G.add_weighted_edges_from([(1, 2, 19), (1, 3, 20), (1, 8, 8), |
||

156 | (2, 3, 25), (2, 4, 18), (3, 5, 18), |
||

157 | (4, 5, 13), (4, 7, 7), (5, 6, 7)]) |
||

158 | assert_edges_equal(nx.max_weight_matching(G), |
||

159 | matching_dict_to_set({1: 8, 2: 3, 3: 2, 4: 7, 5: 6, 6: 5, 7: 4, 8: 1})) |
||

160 | |||

161 | def test_nasty_blossom1(self): |
||

162 | ```
"""Create blossom, relabel as T in more than one way, expand,
``` |
||

163 | ```
augment:
``` |
||

164 | ```
"""
``` |
||

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

166 | G.add_weighted_edges_from([(1, 2, 45), (1, 5, 45), (2, 3, 50), |
||

167 | (3, 4, 45), (4, 5, 50), (1, 6, 30), |
||

168 | (3, 9, 35), (4, 8, 35), (5, 7, 26), |
||

169 | (9, 10, 5)]) |
||

170 | assert_edges_equal(nx.max_weight_matching(G), |
||

171 | matching_dict_to_set({1: 6, 2: 3, 3: 2, 4: 8, 5: 7, |
||

172 | 6: 1, 7: 5, 8: 4, 9: 10, 10: 9})) |
||

173 | |||

174 | def test_nasty_blossom2(self): |
||

175 | ```
"""Again but slightly different:"""
``` |
||

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

177 | G.add_weighted_edges_from([(1, 2, 45), (1, 5, 45), (2, 3, 50), |
||

178 | (3, 4, 45), (4, 5, 50), (1, 6, 30), |
||

179 | (3, 9, 35), (4, 8, 26), (5, 7, 40), |
||

180 | (9, 10, 5)]) |
||

181 | assert_edges_equal(nx.max_weight_matching(G), |
||

182 | matching_dict_to_set({1: 6, 2: 3, 3: 2, 4: 8, 5: 7, |
||

183 | 6: 1, 7: 5, 8: 4, 9: 10, 10: 9})) |
||

184 | |||

185 | def test_nasty_blossom_least_slack(self): |
||

186 | ```
"""Create blossom, relabel as T, expand such that a new
``` |
||

187 | ```
least-slack S-to-free dge is produced, augment:
``` |
||

188 | ```
"""
``` |
||

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

190 | G.add_weighted_edges_from([(1, 2, 45), (1, 5, 45), (2, 3, 50), |
||

191 | (3, 4, 45), (4, 5, 50), (1, 6, 30), |
||

192 | (3, 9, 35), (4, 8, 28), (5, 7, 26), |
||

193 | (9, 10, 5)]) |
||

194 | assert_edges_equal(nx.max_weight_matching(G), |
||

195 | matching_dict_to_set({1: 6, 2: 3, 3: 2, 4: 8, 5: 7, |
||

196 | 6: 1, 7: 5, 8: 4, 9: 10, 10: 9})) |
||

197 | |||

198 | def test_nasty_blossom_augmenting(self): |
||

199 | ```
"""Create nested blossom, relabel as T in more than one way"""
``` |
||

200 | ```
# expand outer blossom such that inner blossom ends up on an
``` |
||

201 | ```
# augmenting path:
``` |
||

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

203 | G.add_weighted_edges_from([(1, 2, 45), (1, 7, 45), (2, 3, 50), |
||

204 | (3, 4, 45), (4, 5, 95), (4, 6, 94), |
||

205 | (5, 6, 94), (6, 7, 50), (1, 8, 30), |
||

206 | (3, 11, 35), (5, 9, 36), (7, 10, 26), |
||

207 | (11, 12, 5)]) |
||

208 | assert_edges_equal(nx.max_weight_matching(G), |
||

209 | matching_dict_to_set({1: 8, 2: 3, 3: 2, 4: 6, 5: 9, 6: 4, |
||

210 | 7: 10, 8: 1, 9: 5, 10: 7, 11: 12, 12: 11})) |
||

211 | |||

212 | def test_nasty_blossom_expand_recursively(self): |
||

213 | ```
"""Create nested S-blossom, relabel as S, expand recursively:"""
``` |
||

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

215 | G.add_weighted_edges_from([(1, 2, 40), (1, 3, 40), (2, 3, 60), |
||

216 | (2, 4, 55), (3, 5, 55), (4, 5, 50), |
||

217 | (1, 8, 15), (5, 7, 30), (7, 6, 10), |
||

218 | (8, 10, 10), (4, 9, 30)]) |
||

219 | assert_edges_equal(nx.max_weight_matching(G), |
||

220 | matching_dict_to_set({1: 2, 2: 1, 3: 5, 4: 9, 5: 3, |
||

221 | 6: 7, 7: 6, 8: 10, 9: 4, 10: 8})) |
||

222 | |||

223 | |||

224 | class TestIsMatching(object): |
||

225 | ```
"""Unit tests for the
``` |
||

226 | ```
:func:`~networkx.algorithms.matching.is_matching` function.
``` |
||

227 | ```
``` |
||

228 | ```
"""
``` |
||

229 | |||

230 | def test_dict(self): |
||

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

232 | assert_true(nx.is_matching(G, {0: 1, 1: 0, 2: 3, 3: 2})) |
||

233 | |||

234 | def test_empty_matching(self): |
||

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

236 | ```
assert_true(nx.is_matching(G, set()))
``` |
||

237 | |||

238 | def test_single_edge(self): |
||

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

240 | assert_true(nx.is_matching(G, {(1, 2)})) |
||

241 | |||

242 | def test_edge_order(self): |
||

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

244 | assert_true(nx.is_matching(G, {(0, 1), (2, 3)})) |
||

245 | assert_true(nx.is_matching(G, {(1, 0), (2, 3)})) |
||

246 | assert_true(nx.is_matching(G, {(0, 1), (3, 2)})) |
||

247 | assert_true(nx.is_matching(G, {(1, 0), (3, 2)})) |
||

248 | |||

249 | def test_valid(self): |
||

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

251 | assert_true(nx.is_matching(G, {(0, 1), (2, 3)})) |
||

252 | |||

253 | def test_invalid(self): |
||

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

255 | assert_false(nx.is_matching(G, {(0, 1), (1, 2), (2, 3)})) |
||

256 | |||

257 | |||

258 | class TestIsMaximalMatching(object): |
||

259 | ```
"""Unit tests for the
``` |
||

260 | ```
:func:`~networkx.algorithms.matching.is_maximal_matching` function.
``` |
||

261 | ```
``` |
||

262 | ```
"""
``` |
||

263 | |||

264 | def test_dict(self): |
||

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

266 | assert_true(nx.is_maximal_matching(G, {0: 1, 1: 0, 2: 3, 3: 2})) |
||

267 | |||

268 | def test_valid(self): |
||

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

270 | assert_true(nx.is_maximal_matching(G, {(0, 1), (2, 3)})) |
||

271 | |||

272 | def test_not_matching(self): |
||

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

274 | assert_false(nx.is_maximal_matching(G, {(0, 1), (1, 2), (2, 3)})) |
||

275 | |||

276 | def test_not_maximal(self): |
||

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

278 | assert_false(nx.is_maximal_matching(G, {(0, 1)})) |
||

279 | |||

280 | |||

281 | class TestIsPerfectMatching(object): |
||

282 | ```
"""Unit tests for the
``` |
||

283 | ```
:func:`~networkx.algorithms.matching.is_perfect_matching` function.
``` |
||

284 | ```
``` |
||

285 | ```
"""
``` |
||

286 | |||

287 | def test_dict(self): |
||

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

289 | assert_true(nx.is_perfect_matching(G, {0: 1, 1: 0, 2: 3, 3: 2})) |
||

290 | |||

291 | def test_valid(self): |
||

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

293 | assert_true(nx.is_perfect_matching(G, {(0, 1), (2, 3)})) |
||

294 | |||

295 | def test_valid_not_path(self): |
||

296 | ```
G = nx.cycle_graph(4)
``` |
||

297 | G.add_edge(0, 4) |
||

298 | G.add_edge(1, 4) |
||

299 | G.add_edge(5, 2) |
||

300 | |||

301 | assert_true(nx.is_perfect_matching(G, {(1, 4), (0, 3), (5, 2)})) |
||

302 | |||

303 | def test_not_matching(self): |
||

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

305 | assert_false(nx.is_perfect_matching(G, {(0, 1), (1, 2), (2, 3)})) |
||

306 | |||

307 | def test_maximal_but_not_perfect(self): |
||

308 | ```
G = nx.cycle_graph(4)
``` |
||

309 | G.add_edge(0, 4) |
||

310 | G.add_edge(1, 4) |
||

311 | |||

312 | assert_false(nx.is_perfect_matching(G, {(1, 4), (0, 3)})) |
||

313 | |||

314 | |||

315 | class TestMaximalMatching(object): |
||

316 | ```
"""Unit tests for the
``` |
||

317 | ```
:func:`~networkx.algorithms.matching.maximal_matching`.
``` |
||

318 | ```
``` |
||

319 | ```
"""
``` |
||

320 | |||

321 | def test_valid_matching(self): |
||

322 | edges = [(1, 2), (1, 5), (2, 3), (2, 5), (3, 4), (3, 6), (5, 6)] |
||

323 | G = nx.Graph(edges) |
||

324 | matching = nx.maximal_matching(G) |
||

325 | assert_true(nx.is_maximal_matching(G, matching)) |
||

326 | |||

327 | def test_single_edge_matching(self): |
||

328 | ```
# In the star graph, any maximal matching has just one edge.
``` |
||

329 | ```
G = nx.star_graph(5)
``` |
||

330 | matching = nx.maximal_matching(G) |
||

331 | assert_equal(1, len(matching)) |
||

332 | assert_true(nx.is_maximal_matching(G, matching)) |
||

333 | |||

334 | def test_self_loops(self): |
||

335 | ```
# Create the path graph with two self-loops.
``` |
||

336 | ```
G = nx.path_graph(3)
``` |
||

337 | G.add_edges_from([(0, 0), (1, 1)]) |
||

338 | matching = nx.maximal_matching(G) |
||

339 | assert_equal(len(matching), 1) |
||

340 | ```
# The matching should never include self-loops.
``` |
||

341 | assert_false(any(u == v for u, v in matching)) |
||

342 | assert_true(nx.is_maximal_matching(G, matching)) |
||

343 | |||

344 | def test_ordering(self): |
||

345 | ```
"""Tests that a maximal matching is computed correctly
``` |
||

346 | ```
regardless of the order in which nodes are added to the graph.
``` |
||

347 | ```
``` |
||

348 | ```
"""
``` |
||

349 | for nodes in permutations(range(3)): |
||

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

351 | G.add_nodes_from(nodes) |
||

352 | G.add_edges_from([(0, 1), (0, 2)]) |
||

353 | matching = nx.maximal_matching(G) |
||

354 | assert_equal(len(matching), 1) |
||

355 | assert_true(nx.is_maximal_matching(G, matching)) |