ioftools / networkxMiCe / networkxmaster / networkx / algorithms / shortest_paths / tests / test_dense.py @ 5cef0f13
History  View  Annotate  Download (5.53 KB)
1 
#!/usr/bin/env python


2 
from nose.tools import * 
3 
import networkx as nx 
4  
5  
6 
class TestFloyd: 
7 
def setUp(self): 
8 
pass

9  
10 
def test_floyd_warshall_predecessor_and_distance(self): 
11 
XG = nx.DiGraph() 
12 
XG.add_weighted_edges_from([('s', 'u', 10), ('s', 'x', 5), 
13 
('u', 'v', 1), ('u', 'x', 2), 
14 
('v', 'y', 1), ('x', 'u', 3), 
15 
('x', 'v', 5), ('x', 'y', 2), 
16 
('y', 's', 7), ('y', 'v', 6)]) 
17 
path, dist = nx.floyd_warshall_predecessor_and_distance(XG) 
18 
assert_equal(dist['s']['v'], 9) 
19 
assert_equal(path['s']['v'], 'u') 
20 
assert_equal(dist, 
21 
{'y': {'y': 0, 'x': 12, 's': 7, 'u': 15, 'v': 6}, 
22 
'x': {'y': 2, 'x': 0, 's': 9, 'u': 3, 'v': 4}, 
23 
's': {'y': 7, 'x': 5, 's': 0, 'u': 8, 'v': 9}, 
24 
'u': {'y': 2, 'x': 2, 's': 9, 'u': 0, 'v': 1}, 
25 
'v': {'y': 1, 'x': 13, 's': 8, 'u': 16, 'v': 0}}) 
26  
27 
GG = XG.to_undirected() 
28 
# make sure we get lower weight

29 
# to_undirected might choose either edge with weight 2 or weight 3

30 
GG['u']['x']['weight'] = 2 
31 
path, dist = nx.floyd_warshall_predecessor_and_distance(GG) 
32 
assert_equal(dist['s']['v'], 8) 
33 
# skip this test, could be alternate path suv

34 
# assert_equal(path['s']['v'],'y')

35  
36 
G = nx.DiGraph() # no weights

37 
G.add_edges_from([('s', 'u'), ('s', 'x'), 
38 
('u', 'v'), ('u', 'x'), 
39 
('v', 'y'), ('x', 'u'), 
40 
('x', 'v'), ('x', 'y'), 
41 
('y', 's'), ('y', 'v')]) 
42 
path, dist = nx.floyd_warshall_predecessor_and_distance(G) 
43 
assert_equal(dist['s']['v'], 2) 
44 
# skip this test, could be alternate path suv

45 
# assert_equal(path['s']['v'],'x')

46  
47 
# alternate interface

48 
dist = nx.floyd_warshall(G) 
49 
assert_equal(dist['s']['v'], 2) 
50  
51 
@raises(KeyError) 
52 
def test_reconstruct_path(self): 
53 
XG = nx.DiGraph() 
54 
XG.add_weighted_edges_from([('s', 'u', 10), ('s', 'x', 5), 
55 
('u', 'v', 1), ('u', 'x', 2), 
56 
('v', 'y', 1), ('x', 'u', 3), 
57 
('x', 'v', 5), ('x', 'y', 2), 
58 
('y', 's', 7), ('y', 'v', 6)]) 
59 
predecessors, _ = nx.floyd_warshall_predecessor_and_distance(XG) 
60  
61 
path = nx.reconstruct_path('s', 'v', predecessors) 
62 
assert_equal(path, ['s', 'x', 'u', 'v']) 
63  
64 
path = nx.reconstruct_path('s', 's', predecessors) 
65 
assert_equal(path, []) 
66  
67 
# this part raises the keyError

68 
nx.reconstruct_path('1', '2', predecessors) 
69  
70 
def test_cycle(self): 
71 
path, dist = nx.floyd_warshall_predecessor_and_distance( 
72 
nx.cycle_graph(7))

73 
assert_equal(dist[0][3], 3) 
74 
assert_equal(path[0][3], 2) 
75 
assert_equal(dist[0][4], 3) 
76  
77 
def test_weighted(self): 
78 
XG3 = nx.Graph() 
79 
XG3.add_weighted_edges_from([[0, 1, 2], [1, 2, 12], [2, 3, 1], 
80 
[3, 4, 5], [4, 5, 1], [5, 0, 10]]) 
81 
path, dist = nx.floyd_warshall_predecessor_and_distance(XG3) 
82 
assert_equal(dist[0][3], 15) 
83 
assert_equal(path[0][3], 2) 
84  
85 
def test_weighted2(self): 
86 
XG4 = nx.Graph() 
87 
XG4.add_weighted_edges_from([[0, 1, 2], [1, 2, 2], [2, 3, 1], 
88 
[3, 4, 1], [4, 5, 1], [5, 6, 1], 
89 
[6, 7, 1], [7, 0, 1]]) 
90 
path, dist = nx.floyd_warshall_predecessor_and_distance(XG4) 
91 
assert_equal(dist[0][2], 4) 
92 
assert_equal(path[0][2], 1) 
93  
94 
def test_weight_parameter(self): 
95 
XG4 = nx.Graph() 
96 
XG4.add_edges_from([(0, 1, {'heavy': 2}), (1, 2, {'heavy': 2}), 
97 
(2, 3, {'heavy': 1}), (3, 4, {'heavy': 1}), 
98 
(4, 5, {'heavy': 1}), (5, 6, {'heavy': 1}), 
99 
(6, 7, {'heavy': 1}), (7, 0, {'heavy': 1})]) 
100 
path, dist = nx.floyd_warshall_predecessor_and_distance(XG4, 
101 
weight='heavy')

102 
assert_equal(dist[0][2], 4) 
103 
assert_equal(path[0][2], 1) 
104  
105 
def test_zero_distance(self): 
106 
XG = nx.DiGraph() 
107 
XG.add_weighted_edges_from([('s', 'u', 10), ('s', 'x', 5), 
108 
('u', 'v', 1), ('u', 'x', 2), 
109 
('v', 'y', 1), ('x', 'u', 3), 
110 
('x', 'v', 5), ('x', 'y', 2), 
111 
('y', 's', 7), ('y', 'v', 6)]) 
112 
path, dist = nx.floyd_warshall_predecessor_and_distance(XG) 
113  
114 
for u in XG: 
115 
assert_equal(dist[u][u], 0)

116  
117 
GG = XG.to_undirected() 
118 
# make sure we get lower weight

119 
# to_undirected might choose either edge with weight 2 or weight 3

120 
GG['u']['x']['weight'] = 2 
121 
path, dist = nx.floyd_warshall_predecessor_and_distance(GG) 
122  
123 
for u in GG: 
124 
dist[u][u] = 0

125  
126 
def test_zero_weight(self): 
127 
G = nx.DiGraph() 
128 
edges = [(1, 2, 2), (2, 3, 4), (1, 5, 1), 
129 
(5, 4, 0), (4, 3, 5), (2, 5, 7)] 
130 
G.add_weighted_edges_from(edges) 
131 
dist = nx.floyd_warshall(G) 
132 
assert_equal(dist[1][3], 14) 
133  
134 
G = nx.MultiDiGraph() 
135 
edges.append((2, 5, 7)) 
136 
G.add_weighted_edges_from(edges) 
137 
dist = nx.floyd_warshall(G) 
138 
assert_equal(dist[1][3], 14) 