← Back to branch summary

~ubuntu-branches/ubuntu/wily/python-networkx/wily

« back to all changes in this revision

Viewing changes to networkx/tests/shortest_path.txt

  • Committer: Bazaar Package Importer
  • Author(s): Cyril Brulebois
  • Date: 2008-03-02 01:06:32 UTC
  • mfrom: (1.2.1 upstream) (3.1.3 hardy)
  • Revision ID: james.westby@ubuntu.com-20080302010632-1lp6qe1orf59jl8b
http://bugs.debian.org/468721
* debian/control:
   + Replace python-setuptools with python-pkg-resources in the
     “Recommends:” since pkg_resources is now available in this
     separate package, thanks Matthias Klose (Closes: #468721).
* debian/copyright:
   + Use “© $years $name” instead of invalid “$name, $years” and
     “(C) $years, $name”, thanks to lintian.

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