1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
#!/usr/bin/env python
from nose.tools import *
import networkx
class TestMST:
def setUp(self):
# example from Wikipedia: http://en.wikipedia.org/wiki/Kruskal's_algorithm
G=networkx.Graph()
edgelist = [(0,3,[('weight',5)]),
(0,1,[('weight',7)]),
(1,3,[('weight',9)]),
(1,2,[('weight',8)]),
(1,4,[('weight',7)]),
(3,4,[('weight',15)]),
(3,5,[('weight',6)]),
(2,4,[('weight',5)]),
(4,5,[('weight',8)]),
(4,6,[('weight',9)]),
(5,6,[('weight',11)])]
G.add_edges_from(edgelist)
self.G=G
tree_edgelist = [(0,1,{'weight':7}),
(0,3,{'weight':5}),
(3,5,{'weight':6}),
(1,4,{'weight':7}),
(4,2,{'weight':5}),
(4,6,{'weight':9})]
self.tree_edgelist=sorted(tuple(sorted((u,v,d)))
for u,v,d in tree_edgelist)
def test_kruskal_mst(self):
edgelist=sorted(networkx.kruskal_mst(self.G))
assert_equal(edgelist,self.tree_edgelist)
|
