← Back to branch summary

~ubuntu-branches/ubuntu/saucy/python-networkx/saucy

« back to all changes in this revision

Viewing changes to networkx/tests/shortest_path.txt

  • Committer: Bazaar Package Importer
  • Author(s): Cyril Brulebois
  • Date: 2009-02-28 13:36:24 UTC
  • mfrom: (1.2.2 upstream)
  • Revision ID: james.westby@ubuntu.com-20090228133624-9l5rwi1ftlzc7b0l
http://bugs.debian.org/517065
* Upload to unstable now that lenny is released (yay).
* Fix FTBFS with python-support 0.90.3: no longer rely on its internal
  behaviour, and xnow set tests/test.py executable right after “setup.py
  install” (Closes: #517065).
* Drop executable bits from bz2 files.
* Update Vcs-* fields: move from DPMT's svn to collab-maint's git.
* Remote DPMT from Uploaders, following Piotr Ożarowski's request.

Show diffs side-by-side

added added

removed removed

Lines of Context:
networkx/tests/shortest_path.txt
1
 
shortest_path
2
 
==============
3
 
 
4
 
>>> import networkx as NX
5
 
>>> from networkx.operators import convert_node_labels_to_integers as cnlti
6
 
>>> G=cnlti(NX.grid_2d_graph(4,4),first_label=1,ordering="sorted")
7
 
 
8
 
    .. image:: paths_G.png
9
 
 
10
 
>>> H=NX.cycle_graph(7)
11
 
>>> DH=NX.cycle_graph(7,create_using=NX.DiGraph())
12
 
 
13
 
Paths and path lengths
14
 
----------------------
15
 
 
16
 
>>> NX.shortest_path_length(G,1,16)
17
 
6
18
 
>>> sp=NX.single_source_shortest_path_length(G,1)
19
 
>>> sp[16]
20
 
6
21
 
>>> NX.shortest_path(G,1,12)
22
 
[1, 2, 3, 4, 8, 12]
23
 
 
24
 
>>> NX.bidirectional_shortest_path(G,1,12)
25
 
[1, 2, 3, 4, 8, 12]
26
 
 
27
 
>>> sp=NX.single_source_shortest_path(G,1)
28
 
>>> sp[12] 
29
 
[1, 2, 3, 4, 8, 12]
30
 
 
31
 
>>> NX.shortest_path(H,0,3)
32
 
[0, 1, 2, 3]
33
 
>>> NX.shortest_path(H,0,4)
34
 
[0, 6, 5, 4]
35
 
>>> NX.bidirectional_shortest_path(H,0,3)
36
 
[0, 1, 2, 3]
37
 
>>> NX.bidirectional_shortest_path(H,0,4)
38
 
[0, 6, 5, 4]
39
 
 
40
 
>>> NX.shortest_path(DH,0,3)
41
 
[0, 1, 2, 3]
42
 
>>> NX.shortest_path(DH,0,4)
43
 
[0, 1, 2, 3, 4]
44
 
>>> NX.bidirectional_shortest_path(DH,0,3)
45
 
[0, 1, 2, 3]
46
 
>>> NX.bidirectional_shortest_path(DH,0,4)
47
 
[0, 1, 2, 3, 4]
48
 
 
49
 
 
50
 
 
51
 
 
52
 
Dijkstra
53
 
--------
54
 
 
55
 
>>> XG=NX.XDiGraph()
56
 
>>> XG.add_edges_from([('s','u',10) ,('s','x',5) ,('u','v',1) ,('u','x',2) ,('v','y',1) ,('x','u',3) ,('x','v',5) ,('x','y',2) ,('y','s',7) ,('y','v',6)])
57
 
>>> (D,P)= NX.single_source_dijkstra(XG,'s')
58
 
>>> P['v']
59
 
['s', 'x', 'u', 'v']
60
 
>>> D['v']
61
 
9
62
 
>>> NX.single_source_dijkstra_path(XG,'s')['v']
63
 
['s', 'x', 'u', 'v']
64
 
>>> NX.single_source_dijkstra_path_length(XG,'s')['v']
65
 
9
66
 
 
67
 
>>> NX.single_source_dijkstra(XG,'s')[1]['v'] 
68
 
['s', 'x', 'u', 'v']
69
 
 
70
 
>>> GG=XG.to_undirected()
71
 
>>> (D,P)= NX.single_source_dijkstra(GG,'s')
72
 
>>> P['v'] 
73
 
['s', 'x', 'u', 'v']
74
 
>>> D['v']     # uses lower weight of 2 on u<->x edge
75
 
8
76
 
 
77
 
>>> NX.dijkstra_path(GG,'s','v')
78
 
['s', 'x', 'u', 'v']
79
 
>>> NX.dijkstra_path_length(GG,'s','v')
80
 
8
81
 
 
82
 
>>> XG2=NX.XDiGraph()
83
 
>>> XG2.add_edges_from([[1,4,1],[4,5,1],[5,6,1],[6,3,1],[1,3,50],[1,2,100],[2,3,100]])
84
 
>>> NX.dijkstra_path(XG2,1,3)
85
 
[1, 4, 5, 6, 3]
86
 
 
87
 
>>> XG3=NX.XGraph()
88
 
>>> XG3.add_edges_from([ [0,1,2],[1,2,12],[2,3,1],[3,4,5],[4,5,1],[5,0,10] ])
89
 
>>> NX.dijkstra_path(XG3,0,3)
90
 
[0, 1, 2, 3]
91
 
>>> NX.dijkstra_path_length(XG3,0,3)
92
 
15
93
 
>>> XG4=NX.XGraph()
94
 
>>> XG4.add_edges_from([ [0,1,2],[1,2,2],[2,3,1],[3,4,1],[4,5,1],[5,6,1],[6,7,1],[7,0,1] ])
95
 
>>> NX.dijkstra_path(XG4,0,2)
96
 
[0, 1, 2]
97
 
>>> NX.dijkstra_path_length(XG4,0,2)
98
 
4
99
 
 
100
 
>>> G=NX.DiGraph()  # no weights
101
 
>>> G.add_edges_from([('s','u'), ('s','x'), ('u','v'), ('u','x'), ('v','y'), ('x','u'), ('x','v'), ('x','y'), ('y','s'), ('y','v')])
102
 
>>> NX.single_source_dijkstra(G,'s','v')[1]['v'] 
103
 
['s', 'u', 'v']
104
 
>>> NX.single_source_dijkstra(G,'s')[1]['v'] 
105
 
['s', 'u', 'v']
106
 
 
107
 
>>> NX.dijkstra_path(G,'s','v')
108
 
['s', 'u', 'v']
109
 
>>> NX.dijkstra_path_length(G,'s','v')
110
 
2
111
 
 
112
 
 
113
 
>>> NX.dijkstra_path(G,'s','moon')
114
 
Traceback (most recent call last):
115
 
...
116
 
NetworkXError: node s not reachable from moon
117
 
 
118
 
 
119
 
>>> NX.dijkstra_path_length(G,'s','moon')
120
 
Traceback (most recent call last):
121
 
...
122
 
NetworkXError: node s not reachable from moon
123
 
 
124
 
>>> NX.dijkstra_path(H,0,3)
125
 
[0, 1, 2, 3]
126
 
 
127
 
>>> NX.dijkstra_path(H,0,4)
128
 
[0, 6, 5, 4]
129
 
 
130
 
Bidirectional Dijkstra
131
 
----------------------
132
 
 
133
 
>>> NX.bidirectional_dijkstra(XG, 's', 'v')
134
 
(9, ['s', 'x', 'u', 'v'])
135
 
>>> NX.bidirectional_dijkstra(GG,'s','v')
136
 
(8, ['s', 'y', 'v'])
137
 
>>> NX.bidirectional_dijkstra(G,'s','v')
138
 
(2, ['s', 'x', 'v'])
139
 
>>> NX.bidirectional_dijkstra(H,0,3)
140
 
(3, [0, 1, 2, 3])
141
 
>>> NX.bidirectional_dijkstra(H,0,4)
142
 
(3, [0, 6, 5, 4])
143
 
>>> NX.bidirectional_dijkstra(XG3,0,3)
144
 
(15, [0, 1, 2, 3])
145
 
>>> NX.bidirectional_dijkstra(XG4,0,2)
146
 
(4, [0, 1, 2])
147
 
 
148
 
# need more tests here
149
 
>>> NX.dijkstra_path(XG,'s','v')==NX.single_source_dijkstra_path(XG,'s')['v']
150
 
True
151
 
 
152
 
Floyd-Warshall all pair shortest path
153
 
-------------------------------------
154
 
 
155
 
>>> dist, path = NX.floyd_warshall(XG)
156
 
>>> dist['s']['v']
157
 
9
158
 
>>> path['s']['v']
159
 
'u'
160
 
 
161
 
>>> dist
162
 
{'y': {'y': 0, 'x': 12, 's': 7, 'u': 15, 'v': 6}, 'x': {'y': 2, 'x': 0, 's': 9, 'u': 3, 'v': 4}, 's': {'y': 7, 'x': 5, 's': 0, 'u': 8, 'v': 9}, 'u': {'y': 2, 'x': 2, 's': 9, 'u': 0, 'v': 1}, 'v': {'y': 1, 'x': 13, 's': 8, 'u': 16, 'v': 0}}
163
 
 
164
 
>>> dist, path = NX.floyd_warshall(GG)
165
 
>>> dist['s']['v']
166
 
8
167
 
>>> path['s']['v']
168
 
'y'
169
 
>>> dist, path = NX.floyd_warshall(G)
170
 
>>> dist['s']['v']
171
 
2
172
 
>>> path['s']['v']
173
 
'x'
174
 
 
175
 
 
176
 
>>> dist, path = NX.floyd_warshall(H)
177
 
>>> dist[0][3]
178
 
3
179
 
>>> path[0][3]
180
 
2
181
 
 
182
 
>>> dist[0][4]
183
 
3
184
 
 
185
 
>>> XG3=NX.XGraph()
186
 
>>> XG3.add_edges_from([ [0,1,2],[1,2,12],[2,3,1],[3,4,5],[4,5,1],[5,0,10] ])
187
 
>>> dist, path = NX.floyd_warshall(XG3)
188
 
>>> dist[0][3]
189
 
15
190
 
>>> path[0][3]
191
 
2
192
 
 
193
 
>>> XG4=NX.XGraph()
194
 
>>> XG4.add_edges_from([ [0,1,2],[1,2,2],[2,3,1],[3,4,1],[4,5,1],[5,6,1],[6,7,1],[7,0,1] ])
195
 
>>> dist, path = NX.floyd_warshall(XG4)
196
 
>>> dist[0][2]
197
 
4
198
 
>>> path[0][2]
199
 
1
200
 
 
201
 
 
202
 
 
203
 
Predecessor
204
 
-----------
205
 
 
206
 
>>> G=NX.path_graph(4)
207
 
>>> NX.predecessor(G,0)
208
 
{0: [], 1: [0], 2: [1], 3: [2]}
209
 
>>> NX.predecessor(G,0,3)
210
 
[2]
211
 
>>> G=NX.grid_2d_graph(2,2)
212
 
>>> sorted(NX.predecessor(G,(0,0)).items())
213
 
[((0, 0), []), ((0, 1), [(0, 0)]), ((1, 0), [(0, 0)]), ((1, 1), [(0, 1), (1, 0)])]
214
 
 
215
 
Dijkstra Predecessor
216
 
--------------------
217
 
 
218
 
>>> G=NX.path_graph(4)
219
 
>>> NX.dijkstra_predecessor_and_distance(G,0)
220
 
({0: [], 1: [0], 2: [1], 3: [2]}, {0: 0, 1: 1, 2: 2, 3: 3})
221
 
>>> G=NX.grid_2d_graph(2,2)
222
 
>>> pred,dist=NX.dijkstra_predecessor_and_distance(G,(0,0))
223
 
>>> sorted(pred.items())
224
 
[((0, 0), []), ((0, 1), [(0, 0)]), ((1, 0), [(0, 0)]), ((1, 1), [(0, 1), (1, 0)])]
225
 
>>> sorted(dist.items())
226
 
[((0, 0), 0), ((0, 1), 1), ((1, 0), 1), ((1, 1), 2)]
227
 
 
228
 
>>> XG=NX.XDiGraph()
229
 
>>> XG.add_edges_from([('s','u',10) ,('s','x',5) ,('u','v',1) ,('u','x',2) ,('v','y',1) ,('x','u',3) ,('x','v',5) ,('x','y',2) ,('y','s',7) ,('y','v',6)])
230
 
>>> (P,D)= NX.dijkstra_predecessor_and_distance(XG,'s')
231
 
>>> P['v']
232
 
['u']
233
 
>>> D['v']
234
 
9
235
 
 
236