Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (14 KB)

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