Statistics
| Branch: | Revision:

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))