1 #!/usr/bin/env python 2 from nose.tools import * 3 import networkx as nx 4 5 class TestWeightedPath: 6 7 def setUp(self): 8 from networkx import convert_node_labels_to_integers as cnlti 9 self.grid=cnlti(nx.grid_2d_graph(4,4),first_label=1,ordering="sorted") 10 self.cycle=nx.cycle_graph(7) 11 self.directed_cycle=nx.cycle_graph(7,create_using=nx.DiGraph()) 12 self.XG=nx.DiGraph() 13 self.XG.add_weighted_edges_from([('s','u',10) ,('s','x',5) , 14 ('u','v',1) ,('u','x',2) , 15 ('v','y',1) ,('x','u',3) , 16 ('x','v',5) ,('x','y',2) , 17 ('y','s',7) ,('y','v',6)]) 18 self.MXG=nx.MultiDiGraph(self.XG) 19 self.MXG.add_edge('s','u',weight=15) 20 self.XG2=nx.DiGraph() 21 self.XG2.add_weighted_edges_from([[1,4,1],[4,5,1], 22 [5,6,1],[6,3,1], 23 [1,3,50],[1,2,100],[2,3,100]]) 24 25 self.XG3=nx.Graph() 26 self.XG3.add_weighted_edges_from([ [0,1,2],[1,2,12], 27 [2,3,1],[3,4,5], 28 [4,5,1],[5,0,10] ]) 29 30 self.XG4=nx.Graph() 31 self.XG4.add_weighted_edges_from([ [0,1,2],[1,2,2], 32 [2,3,1],[3,4,1], 33 [4,5,1],[5,6,1], 34 [6,7,1],[7,0,1] ]) 35 self.MXG4=nx.MultiGraph(self.XG4) 36 self.MXG4.add_edge(0,1,weight=3) 37 self.G=nx.DiGraph() # no weights 38 self.G.add_edges_from([('s','u'), ('s','x'), 39 ('u','v'), ('u','x'), 40 ('v','y'), ('x','u'), 41 ('x','v'), ('x','y'), 42 ('y','s'), ('y','v')]) 43 44 def test_dijkstra(self): 45 (D,P)= nx.single_source_dijkstra(self.XG,'s') 46 assert_equal(P['v'], ['s', 'x', 'u', 'v']) 47 assert_equal(D['v'],9) 48 49 assert_equal(nx.single_source_dijkstra_path(self.XG,'s')['v'], 50 ['s', 'x', 'u', 'v']) 51 assert_equal(nx.single_source_dijkstra_path_length(self.XG,'s')['v'],9) 52 53 assert_equal(nx.single_source_dijkstra(self.XG,'s')[1]['v'], 54 ['s', 'x', 'u', 'v']) 55 56 assert_equal(nx.single_source_dijkstra_path(self.MXG,'s')['v'], 57 ['s', 'x', 'u', 'v']) 58 59 GG=self.XG.to_undirected() 60 # make sure we get lower weight 61 # to_undirected might choose either edge with weight 2 or weight 3 62 GG['u']['x']['weight']=2 63 (D,P)= nx.single_source_dijkstra(GG,'s') 64 assert_equal(P['v'] , ['s', 'x', 'u', 'v']) 65 assert_equal(D['v'],8) # uses lower weight of 2 on u<->x edge 66 assert_equal(nx.dijkstra_path(GG,'s','v'), ['s', 'x', 'u', 'v']) 67 assert_equal(nx.dijkstra_path_length(GG,'s','v'),8) 68 69 assert_equal(nx.dijkstra_path(self.XG2,1,3), [1, 4, 5, 6, 3]) 70 assert_equal(nx.dijkstra_path(self.XG3,0,3), [0, 1, 2, 3]) 71 assert_equal(nx.dijkstra_path_length(self.XG3,0,3),15) 72 assert_equal(nx.dijkstra_path(self.XG4,0,2), [0, 1, 2]) 73 assert_equal(nx.dijkstra_path_length(self.XG4,0,2), 4) 74 assert_equal(nx.dijkstra_path(self.MXG4,0,2), [0, 1, 2]) 75 assert_equal(nx.single_source_dijkstra(self.G,'s','v')[1]['v'], 76 ['s', 'u', 'v']) 77 assert_equal(nx.single_source_dijkstra(self.G,'s')[1]['v'], 78 ['s', 'u', 'v']) 79 80 assert_equal(nx.dijkstra_path(self.G,'s','v'), ['s', 'u', 'v']) 81 assert_equal(nx.dijkstra_path_length(self.G,'s','v'), 2) 82 83 # NetworkXError: node s not reachable from moon 84 assert_raises(nx.NetworkXNoPath,nx.dijkstra_path,self.G,'s','moon') 85 assert_raises(nx.NetworkXNoPath,nx.dijkstra_path_length,self.G,'s','moon') 86 87 assert_equal(nx.dijkstra_path(self.cycle,0,3),[0, 1, 2, 3]) 88 assert_equal(nx.dijkstra_path(self.cycle,0,4), [0, 6, 5, 4]) 89 90 assert_equal(nx.single_source_dijkstra(self.cycle,0,0),({0:0}, {0:[0]}) ) 91 92 def test_bidirectional_dijkstra(self): 93 assert_equal(nx.bidirectional_dijkstra(self.XG, 's', 'v'), 94 (9, ['s', 'x', 'u', 'v'])) 95 (dist,path) = nx.bidirectional_dijkstra(self.G,'s','v') 96 assert_equal(dist,2) 97 # skip this test, correct path could also be ['s','u','v'] 98 # assert_equal(nx.bidirectional_dijkstra(self.G,'s','v'), 99 # (2, ['s', 'x', 'v'])) 100 assert_equal(nx.bidirectional_dijkstra(self.cycle,0,3), 101 (3, [0, 1, 2, 3])) 102 assert_equal(nx.bidirectional_dijkstra(self.cycle,0,4), 103 (3, [0, 6, 5, 4])) 104 assert_equal(nx.bidirectional_dijkstra(self.XG3,0,3), 105 (15, [0, 1, 2, 3])) 106 assert_equal(nx.bidirectional_dijkstra(self.XG4,0,2), 107 (4, [0, 1, 2])) 108 109 # need more tests here 110 assert_equal(nx.dijkstra_path(self.XG,'s','v'), 111 nx.single_source_dijkstra_path(self.XG,'s')['v']) 112 113 114 @raises(nx.NetworkXNoPath) 115 def test_bidirectional_dijkstra_no_path(self): 116 G = nx.Graph() 117 G.add_path([1,2,3]) 118 G.add_path([4,5,6]) 119 path = nx.bidirectional_dijkstra(G,1,6) 120 121 def test_dijkstra_predecessor(self): 122 G=nx.path_graph(4) 123 assert_equal(nx.dijkstra_predecessor_and_distance(G,0), 124 ({0: [], 1: [0], 2: [1], 3: [2]}, {0: 0, 1: 1, 2: 2, 3: 3})) 125 G=nx.grid_2d_graph(2,2) 126 pred,dist=nx.dijkstra_predecessor_and_distance(G,(0,0)) 127 assert_equal(sorted(pred.items()), 128 [((0, 0), []), ((0, 1), [(0, 0)]), 129 ((1, 0), [(0, 0)]), ((1, 1), [(0, 1), (1, 0)])]) 130 assert_equal(sorted(dist.items()), 131 [((0, 0), 0), ((0, 1), 1), ((1, 0), 1), ((1, 1), 2)]) 132 133 XG=nx.DiGraph() 134 XG.add_weighted_edges_from([('s','u',10) ,('s','x',5) , 135 ('u','v',1) ,('u','x',2) , 136 ('v','y',1) ,('x','u',3) , 137 ('x','v',5) ,('x','y',2) , 138 ('y','s',7) ,('y','v',6)]) 139 (P,D)= nx.dijkstra_predecessor_and_distance(XG,'s') 140 assert_equal(P['v'],['u']) 141 assert_equal(D['v'],9) 142 (P,D)= nx.dijkstra_predecessor_and_distance(XG,'s',cutoff=8) 143 assert_false('v' in D) 144 145 def test_single_source_dijkstra_path_length(self): 146 pl = nx.single_source_dijkstra_path_length 147 assert_equal(pl(self.MXG4,0)[2], 4) 148 spl = pl(self.MXG4,0,cutoff=2) 149 assert_false(2 in spl) 150 151 def test_bidirectional_dijkstra_multigraph(self): 152 G = nx.MultiGraph() 153 G.add_edge('a', 'b', weight=10) 154 G.add_edge('a', 'b', weight=100) 155 dp= nx.bidirectional_dijkstra(G, 'a', 'b') 156 assert_equal(dp,(10, ['a', 'b'])) 157 158 159 def test_dijkstra_pred_distance_multigraph(self): 160 G = nx.MultiGraph() 161 G.add_edge('a', 'b', key='short',foo=5, weight=100) 162 G.add_edge('a', 'b', key='long',bar=1, weight=110) 163 p,d= nx.dijkstra_predecessor_and_distance(G, 'a') 164 assert_equal(p,{'a': [], 'b': ['a']}) 165 assert_equal(d,{'a': 0, 'b': 100}) 166 167 def test_negative_edge_cycle(self): 168 G = nx.cycle_graph(5, create_using = nx.DiGraph()) 169 assert_equal(nx.negative_edge_cycle(G), False) 170 G.add_edge(8, 9, weight = -7) 171 G.add_edge(9, 8, weight = 3) 172 assert_equal(nx.negative_edge_cycle(G), True) 173 assert_raises(ValueError,nx.single_source_dijkstra_path_length,G,8) 174 assert_raises(ValueError,nx.single_source_dijkstra,G,8) 175 assert_raises(ValueError,nx.dijkstra_predecessor_and_distance,G,8) 176 G.add_edge(9,10) 177 assert_raises(ValueError,nx.bidirectional_dijkstra,G,8,10) 178 179 def test_bellman_ford(self): 180 # single node graph 181 G = nx.DiGraph() 182 G.add_node(0) 183 assert_equal(nx.bellman_ford(G, 0), ({0: None}, {0: 0})) 184 assert_raises(KeyError, nx.bellman_ford, G, 1) 185 186 # negative weight cycle 187 G = nx.cycle_graph(5, create_using = nx.DiGraph()) 188 G.add_edge(1, 2, weight = -7) 189 for i in range(5): 190 assert_raises(nx.NetworkXUnbounded, nx.bellman_ford, G, i) 191 G = nx.cycle_graph(5) # undirected Graph 192 G.add_edge(1, 2, weight = -3) 193 for i in range(5): 194 assert_raises(nx.NetworkXUnbounded, nx.bellman_ford, G, i) 195 # no negative cycle but negative weight 196 G = nx.cycle_graph(5, create_using = nx.DiGraph()) 197 G.add_edge(1, 2, weight = -3) 198 assert_equal(nx.bellman_ford(G, 0), 199 ({0: None, 1: 0, 2: 1, 3: 2, 4: 3}, 200 {0: 0, 1: 1, 2: -2, 3: -1, 4: 0})) 201 202 # not connected 203 G = nx.complete_graph(6) 204 G.add_edge(10, 11) 205 G.add_edge(10, 12) 206 assert_equal(nx.bellman_ford(G, 0), 207 ({0: None, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0}, 208 {0: 0, 1: 1, 2: 1, 3: 1, 4: 1, 5: 1})) 209 210 # not connected, with a component not containing the source that 211 # contains a negative cost cycle. 212 G = nx.complete_graph(6) 213 G.add_edges_from([('A', 'B', {'load': 3}), 214 ('B', 'C', {'load': -10}), 215 ('C', 'A', {'load': 2})]) 216 assert_equal(nx.bellman_ford(G, 0, weight = 'load'), 217 ({0: None, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0}, 218 {0: 0, 1: 1, 2: 1, 3: 1, 4: 1, 5: 1})) 219 220 # multigraph 221 P, D = nx.bellman_ford(self.MXG,'s') 222 assert_equal(P['v'], 'u') 223 assert_equal(D['v'], 9) 224 P, D = nx.bellman_ford(self.MXG4, 0) 225 assert_equal(P[2], 1) 226 assert_equal(D[2], 4) 227 228 # other tests 229 (P,D)= nx.bellman_ford(self.XG,'s') 230 assert_equal(P['v'], 'u') 231 assert_equal(D['v'], 9) 232 233 G=nx.path_graph(4) 234 assert_equal(nx.bellman_ford(G,0), 235 ({0: None, 1: 0, 2: 1, 3: 2}, {0: 0, 1: 1, 2: 2, 3: 3})) 236 assert_equal(nx.bellman_ford(G, 3), 237 ({0: 1, 1: 2, 2: 3, 3: None}, {0: 3, 1: 2, 2: 1, 3: 0})) 238 239 G=nx.grid_2d_graph(2,2) 240 pred,dist=nx.bellman_ford(G,(0,0)) 241 assert_equal(sorted(pred.items()), 242 [((0, 0), None), ((0, 1), (0, 0)), 243 ((1, 0), (0, 0)), ((1, 1), (0, 1))]) 244 assert_equal(sorted(dist.items()), 245 [((0, 0), 0), ((0, 1), 1), ((1, 0), 1), ((1, 1), 2)]) 246 247
