Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (11.6 KB)

1
from nose import SkipTest
2
from nose.tools import *
3

    
4
import networkx as nx
5

    
6
try:
7
    import numpy as np
8
except:
9
    raise SkipTest('NumPy not available.')
10

    
11
from networkx.algorithms.tree import branchings
12
from networkx.algorithms.tree import recognition
13
from networkx.testing import *
14

    
15
#
16
# Explicitly discussed examples from Edmonds paper.
17
#
18

    
19
# Used in Figures A-F.
20
#
21
G_array = np.array([
22
    # 0   1   2   3   4   5   6   7   8
23
    [0,  0, 12,  0, 12,  0,  0,  0,  0],  # 0
24
    [4,  0,  0,  0,  0, 13,  0,  0,  0],  # 1
25
    [0, 17,  0, 21,  0, 12,  0,  0,  0],  # 2
26
    [5,  0,  0,  0, 17,  0, 18,  0,  0],  # 3
27
    [0,  0,  0,  0,  0,  0,  0, 12,  0],  # 4
28
    [0,  0,  0,  0,  0,  0, 14,  0, 12],  # 5
29
    [0,  0, 21,  0,  0,  0,  0,  0, 15],  # 6
30
    [0,  0,  0, 19,  0,  0, 15,  0,  0],  # 7
31
    [0,  0,  0,  0,  0,  0,  0, 18,  0],  # 8
32
], dtype=int)
33

    
34
# We convert to MultiDiGraph after using from_numpy_matrix
35
# https://github.com/networkx/networkx/pull/1305
36

    
37

    
38
def G1():
39
    G = nx.DiGraph()
40
    G = nx.from_numpy_matrix(G_array, create_using=G)
41
    G = nx.MultiDiGraph(G)
42
    return G
43

    
44

    
45
def G2():
46
    # Now we shift all the weights by -10.
47
    # Should not affect optimal arborescence, but does affect optimal branching.
48
    G = nx.DiGraph()
49
    Garr = G_array.copy()
50
    Garr[np.nonzero(Garr)] -= 10
51
    G = nx.from_numpy_matrix(Garr, create_using=G)
52
    G = nx.MultiDiGraph(G)
53
    return G
54

    
55

    
56
# An optimal branching for G1 that is also a spanning arborescence. So it is
57
# also an optimal spanning arborescence.
58
#
59
optimal_arborescence_1 = [
60
    (0, 2, 12), (2, 1, 17), (2, 3, 21), (1, 5, 13),
61
    (3, 4, 17), (3, 6, 18), (6, 8, 15), (8, 7, 18),
62
]
63

    
64
# For G2, the optimal branching of G1 (with shifted weights) is no longer
65
# an optimal branching, but it is still an optimal spanning arborescence
66
# (just with shifted weights). An optimal branching for G2 is similar to what
67
# appears in figure G (this is greedy_subopt_branching_1a below), but with the
68
# edge (3, 0, 5), which is now (3, 0, -5), removed. Thus, the optimal branching
69
# is not a spanning arborescence. The code finds optimal_branching_2a.
70
# An alternative and equivalent branching is optimal_branching_2b. We would
71
# need to modify the code to iterate through all equivalent optimal branchings.
72
#
73
# These are maximal branchings or arborescences.
74
optimal_branching_2a = [
75
    (5, 6,  4), (6, 2, 11), (6, 8,  5), (8, 7,  8),
76
    (2, 1,  7), (2, 3, 11), (3, 4,  7),
77
]
78
optimal_branching_2b = [
79
    (8, 7,  8), (7, 3,  9), (3, 4,  7), (3, 6,  8),
80
    (6, 2, 11), (2, 1,  7), (1, 5,  3),
81
]
82
optimal_arborescence_2 = [
83
    (0, 2,  2), (2, 1,  7), (2, 3, 11), (1, 5,  3),
84
    (3, 4,  7), (3, 6,  8), (6, 8,  5), (8, 7,  8),
85
]
86

    
87
# Two suboptimal maximal branchings on G1 obtained from a greedy algorithm.
88
# 1a matches what is shown in Figure G in Edmonds's paper.
89
greedy_subopt_branching_1a = [
90
    (5, 6, 14), (6, 2, 21), (6, 8, 15), (8, 7, 18),
91
    (2, 1, 17), (2, 3, 21), (3, 0,  5), (3, 4, 17),
92
]
93
greedy_subopt_branching_1b = [
94
    (8, 7, 18), (7, 6, 15), (6, 2, 21), (2, 1, 17),
95
    (2, 3, 21), (1, 5, 13), (3, 0,  5), (3, 4, 17),
96
]
97

    
98

    
99
def build_branching(edges):
100
    G = nx.DiGraph()
101
    for u, v, weight in edges:
102
        G.add_edge(u, v, weight=weight)
103
    return G
104

    
105

    
106
def sorted_edges(G, attr='weight', default=1):
107
    edges = [(u, v, data.get(attr, default)) for (u, v, data) in G.edges(data=True)]
108
    edges = sorted(edges, key=lambda x: (x[2], x[1], x[0]))
109
    return edges
110

    
111

    
112
def assert_equal_branchings(G1, G2, attr='weight', default=1):
113
    edges1 = list(G1.edges(data=True))
114
    edges2 = list(G2.edges(data=True))
115
    assert_equal(len(edges1), len(edges2))
116

    
117
    # Grab the weights only.
118
    e1 = sorted_edges(G1, attr, default)
119
    e2 = sorted_edges(G2, attr, default)
120

    
121
    # If we have an exception, let's see the edges.
122
    print(e1)
123
    print(e2)
124
    print
125

    
126
    for a, b in zip(e1, e2):
127
        assert_equal(a[:2], b[:2])
128
        np.testing.assert_almost_equal(a[2], b[2])
129

    
130

    
131
################
132

    
133
def test_optimal_branching1():
134
    G = build_branching(optimal_arborescence_1)
135
    assert_true(recognition.is_arborescence(G), True)
136
    assert_equal(branchings.branching_weight(G),  131)
137

    
138

    
139
def test_optimal_branching2a():
140
    G = build_branching(optimal_branching_2a)
141
    assert_true(recognition.is_arborescence(G), True)
142
    assert_equal(branchings.branching_weight(G),  53)
143

    
144

    
145
def test_optimal_branching2b():
146
    G = build_branching(optimal_branching_2b)
147
    assert_true(recognition.is_arborescence(G), True)
148
    assert_equal(branchings.branching_weight(G),  53)
149

    
150

    
151
def test_optimal_arborescence2():
152
    G = build_branching(optimal_arborescence_2)
153
    assert_true(recognition.is_arborescence(G), True)
154
    assert_equal(branchings.branching_weight(G),  51)
155

    
156

    
157
def test_greedy_suboptimal_branching1a():
158
    G = build_branching(greedy_subopt_branching_1a)
159
    assert_true(recognition.is_arborescence(G), True)
160
    assert_equal(branchings.branching_weight(G), 128)
161

    
162

    
163
def test_greedy_suboptimal_branching1b():
164
    G = build_branching(greedy_subopt_branching_1b)
165
    assert_true(recognition.is_arborescence(G), True)
166
    assert_equal(branchings.branching_weight(G), 127)
167

    
168

    
169
def test_greedy_max1():
170
    # Standard test.
171
    #
172
    G = G1()
173
    B = branchings.greedy_branching(G)
174
    # There are only two possible greedy branchings. The sorting is such
175
    # that it should equal the second suboptimal branching: 1b.
176
    B_ = build_branching(greedy_subopt_branching_1b)
177
    assert_equal_branchings(B, B_)
178

    
179

    
180
def test_greedy_max2():
181
    # Different default weight.
182
    #
183
    G = G1()
184
    del G[1][0][0]['weight']
185
    B = branchings.greedy_branching(G, default=6)
186
    # Chosen so that edge (3,0,5) is not selected and (1,0,6) is instead.
187

    
188
    edges = [
189
        (1, 0, 6), (1, 5, 13), (7, 6, 15), (2, 1, 17),
190
        (3, 4, 17), (8, 7, 18), (2, 3, 21), (6, 2, 21),
191
    ]
192
    B_ = build_branching(edges)
193
    assert_equal_branchings(B, B_)
194

    
195

    
196
def test_greedy_max3():
197
    # All equal weights.
198
    #
199
    G = G1()
200
    B = branchings.greedy_branching(G, attr=None)
201

    
202
    # This is mostly arbitrary...the output was generated by running the algo.
203
    edges = [
204
        (2, 1, 1), (3, 0, 1), (3, 4, 1), (5, 8, 1),
205
        (6, 2, 1), (7, 3, 1), (7, 6, 1), (8, 7, 1),
206
    ]
207
    B_ = build_branching(edges)
208
    assert_equal_branchings(B, B_, default=1)
209

    
210

    
211
def test_greedy_min():
212
    G = G1()
213
    B = branchings.greedy_branching(G, kind='min')
214

    
215
    edges = [
216
        (1, 0, 4), (0, 2, 12), (0, 4, 12), (2, 5, 12),
217
        (4, 7, 12), (5, 8, 12), (5, 6, 14), (7, 3, 19)
218
    ]
219
    B_ = build_branching(edges)
220
    assert_equal_branchings(B, B_)
221

    
222

    
223
def test_edmonds1_maxbranch():
224
    G = G1()
225
    x = branchings.maximum_branching(G)
226
    x_ = build_branching(optimal_arborescence_1)
227
    assert_equal_branchings(x, x_)
228

    
229

    
230
def test_edmonds1_maxarbor():
231
    G = G1()
232
    x = branchings.maximum_spanning_arborescence(G)
233
    x_ = build_branching(optimal_arborescence_1)
234
    assert_equal_branchings(x, x_)
235

    
236

    
237
def test_edmonds2_maxbranch():
238
    G = G2()
239
    x = branchings.maximum_branching(G)
240
    x_ = build_branching(optimal_branching_2a)
241
    assert_equal_branchings(x, x_)
242

    
243

    
244
def test_edmonds2_maxarbor():
245
    G = G2()
246
    x = branchings.maximum_spanning_arborescence(G)
247
    x_ = build_branching(optimal_arborescence_2)
248
    assert_equal_branchings(x, x_)
249

    
250

    
251
def test_edmonds2_minarbor():
252
    G = G1()
253
    x = branchings.minimum_spanning_arborescence(G)
254
    # This was obtained from algorithm. Need to verify it independently.
255
    # Branch weight is: 96
256
    edges = [
257
        (3, 0, 5), (0, 2, 12), (0, 4, 12), (2, 5, 12),
258
        (4, 7, 12), (5, 8, 12), (5, 6, 14), (2, 1, 17)
259
    ]
260
    x_ = build_branching(edges)
261
    assert_equal_branchings(x, x_)
262

    
263

    
264
def test_edmonds3_minbranch1():
265
    G = G1()
266
    x = branchings.minimum_branching(G)
267
    edges = []
268
    x_ = build_branching(edges)
269
    assert_equal_branchings(x, x_)
270

    
271

    
272
def test_edmonds3_minbranch2():
273
    G = G1()
274
    G.add_edge(8, 9, weight=-10)
275
    x = branchings.minimum_branching(G)
276
    edges = [(8, 9, -10)]
277
    x_ = build_branching(edges)
278
    assert_equal_branchings(x, x_)
279

    
280
# Need more tests
281

    
282

    
283
def test_mst():
284
    # Make sure we get the same results for undirected graphs.
285
    # Example from: https://en.wikipedia.org/wiki/Kruskal's_algorithm
286
    G = nx.Graph()
287
    edgelist = [(0, 3, [('weight', 5)]),
288
                (0, 1, [('weight', 7)]),
289
                (1, 3, [('weight', 9)]),
290
                (1, 2, [('weight', 8)]),
291
                (1, 4, [('weight', 7)]),
292
                (3, 4, [('weight', 15)]),
293
                (3, 5, [('weight', 6)]),
294
                (2, 4, [('weight', 5)]),
295
                (4, 5, [('weight', 8)]),
296
                (4, 6, [('weight', 9)]),
297
                (5, 6, [('weight', 11)])]
298
    G.add_edges_from(edgelist)
299
    G = G.to_directed()
300
    x = branchings.minimum_spanning_arborescence(G)
301

    
302
    edges = [(set([0, 1]), 7), (set([0, 3]), 5), (set([3, 5]), 6),
303
             (set([1, 4]), 7), (set([4, 2]), 5), (set([4, 6]), 9)]
304

    
305
    assert_equal(x.number_of_edges(), len(edges))
306
    for u, v, d in x.edges(data=True):
307
        assert_true((set([u, v]), d['weight']) in edges)
308

    
309

    
310
def test_mixed_nodetypes():
311
    # Smoke test to make sure no TypeError is raised for mixed node types.
312
    G = nx.Graph()
313
    edgelist = [(0, 3, [('weight', 5)]),
314
                (0, '1', [('weight', 5)])]
315
    G.add_edges_from(edgelist)
316
    G = G.to_directed()
317
    x = branchings.minimum_spanning_arborescence(G)
318

    
319

    
320
def test_edmonds1_minbranch():
321
    # Using -G_array and min should give the same as optimal_arborescence_1,
322
    # but with all edges negative.
323
    edges = [(u, v, -w) for (u, v, w) in optimal_arborescence_1]
324

    
325
    G = nx.DiGraph()
326
    G = nx.from_numpy_matrix(-G_array, create_using=G)
327

    
328
    # Quickly make sure max branching is empty.
329
    x = branchings.maximum_branching(G)
330
    x_ = build_branching([])
331
    assert_equal_branchings(x, x_)
332

    
333
    # Now test the min branching.
334
    x = branchings.minimum_branching(G)
335
    x_ = build_branching(edges)
336
    assert_equal_branchings(x, x_)
337

    
338

    
339
def test_edge_attribute_preservation_normal_graph():
340
    # Test that edge attributes are preserved when finding an optimum graph
341
    # using the Edmonds class for normal graphs.
342
    G = nx.Graph()
343

    
344
    edgelist = [(0, 1, [('weight', 5), ('otherattr', 1), ('otherattr2', 3)]),
345
                (0, 2, [('weight', 5), ('otherattr', 2), ('otherattr2', 2)]),
346
                (1, 2, [('weight', 6), ('otherattr', 3), ('otherattr2', 1)])]
347
    G.add_edges_from(edgelist)
348

    
349
    ed = branchings.Edmonds(G)
350
    B = ed.find_optimum('weight', preserve_attrs=True, seed=1)
351

    
352
    assert_equal(B[0][1]['otherattr'], 1)
353
    assert_equal(B[0][1]['otherattr2'], 3)
354

    
355

    
356
def test_edge_attribute_preservation_multigraph():
357

    
358
    # Test that edge attributes are preserved when finding an optimum graph
359
    # using the Edmonds class for multigraphs.
360
    G = nx.MultiGraph()
361

    
362
    edgelist = [(0, 1, [('weight', 5), ('otherattr', 1), ('otherattr2', 3)]),
363
                (0, 2, [('weight', 5), ('otherattr', 2), ('otherattr2', 2)]),
364
                (1, 2, [('weight', 6), ('otherattr', 3), ('otherattr2', 1)])]
365
    G.add_edges_from(edgelist * 2)  # Make sure we have duplicate edge paths
366

    
367
    ed = branchings.Edmonds(G)
368
    B = ed.find_optimum('weight', preserve_attrs=True)
369

    
370
    assert_equal(B[0][1][0]['otherattr'], 1)
371
    assert_equal(B[0][1][0]['otherattr2'], 3)
372

    
373

    
374
def test_edge_attribute_discard():
375
    # Test that edge attributes are discarded if we do not specify to keep them
376
    G = nx.Graph()
377

    
378
    edgelist = [(0, 1, [('weight', 5), ('otherattr', 1), ('otherattr2', 3)]),
379
                (0, 2, [('weight', 5), ('otherattr', 2), ('otherattr2', 2)]),
380
                (1, 2, [('weight', 6), ('otherattr', 3), ('otherattr2', 1)])]
381
    G.add_edges_from(edgelist)
382

    
383
    ed = branchings.Edmonds(G)
384
    B = ed.find_optimum('weight', preserve_attrs=False)
385

    
386
    edge_dict = B[0][1]
387
    with assert_raises(KeyError):
388
        _ = edge_dict['otherattr']