ioftools / networkxMiCe / networkxmaster / networkx / algorithms / shortest_paths / generic.py @ 5cef0f13
History  View  Annotate  Download (17.1 KB)
1 
# * coding: utf8 *


2 
# Copyright (C) 20042019 by

3 
# Aric Hagberg <hagberg@lanl.gov>

4 
# Dan Schult <dschult@colgate.edu>

5 
# Pieter Swart <swart@lanl.gov>

6 
# All rights reserved.

7 
# BSD license.

8 
#

9 
# Authors: Aric Hagberg <aric.hagberg@gmail.com>

10 
# Sérgio Nery Simões <sergionery@gmail.com>

11 
"""

12 
Compute the shortest paths and path lengths between nodes in the graph.

13 

14 
These algorithms work with undirected and directed graphs.

15 

16 
"""

17 
from __future__ import division 
18  
19 
import networkx as nx 
20  
21 
__all__ = ['shortest_path', 'all_shortest_paths', 
22 
'shortest_path_length', 'average_shortest_path_length', 
23 
'has_path']

24  
25  
26 
def has_path(G, source, target): 
27 
"""Returns *True* if *G* has a path from *source* to *target*.

28 

29 
Parameters

30 


31 
G : NetworkX graph

32 

33 
source : node

34 
Starting node for path

35 

36 
target : node

37 
Ending node for path

38 
"""

39 
try:

40 
nx.shortest_path(G, source, target) 
41 
except nx.NetworkXNoPath:

42 
return False 
43 
return True 
44  
45  
46 
def shortest_path(G, source=None, target=None, weight=None, method='dijkstra'): 
47 
"""Compute shortest paths in the graph.

48 

49 
Parameters

50 


51 
G : NetworkX graph

52 

53 
source : node, optional

54 
Starting node for path. If not specified, compute shortest

55 
paths for each possible starting node.

56 

57 
target : node, optional

58 
Ending node for path. If not specified, compute shortest

59 
paths to all possible nodes.

60 

61 
weight : None or string, optional (default = None)

62 
If None, every edge has weight/distance/cost 1.

63 
If a string, use this edge attribute as the edge weight.

64 
Any edge attribute not present defaults to 1.

65 

66 
method : string, optional (default = 'dijkstra')

67 
The algorithm to use to compute the path.

68 
Supported options: 'dijkstra', 'bellmanford'.

69 
Other inputs produce a ValueError.

70 
If `weight` is None, unweighted graph methods are used, and this

71 
suggestion is ignored.

72 

73 
Returns

74 


75 
path: list or dictionary

76 
All returned paths include both the source and target in the path.

77 

78 
If the source and target are both specified, return a single list

79 
of nodes in a shortest path from the source to the target.

80 

81 
If only the source is specified, return a dictionary keyed by

82 
targets with a list of nodes in a shortest path from the source

83 
to one of the targets.

84 

85 
If only the target is specified, return a dictionary keyed by

86 
sources with a list of nodes in a shortest path from one of the

87 
sources to the target.

88 

89 
If neither the source nor target are specified return a dictionary

90 
of dictionaries with path[source][target]=[list of nodes in path].

91 

92 
Raises

93 


94 
NodeNotFound

95 
If `source` is not in `G`.

96 

97 
ValueError

98 
If `method` is not among the supported options.

99 

100 
Examples

101 


102 
>>> G = nx.path_graph(5)

103 
>>> print(nx.shortest_path(G, source=0, target=4))

104 
[0, 1, 2, 3, 4]

105 
>>> p = nx.shortest_path(G, source=0) # target not specified

106 
>>> p[4]

107 
[0, 1, 2, 3, 4]

108 
>>> p = nx.shortest_path(G, target=4) # source not specified

109 
>>> p[0]

110 
[0, 1, 2, 3, 4]

111 
>>> p = nx.shortest_path(G) # source, target not specified

112 
>>> p[0][4]

113 
[0, 1, 2, 3, 4]

114 

115 
Notes

116 


117 
There may be more than one shortest path between a source and target.

118 
This returns only one of them.

119 

120 
See Also

121 


122 
all_pairs_shortest_path()

123 
all_pairs_dijkstra_path()

124 
all_pairs_bellman_ford_path()

125 
single_source_shortest_path()

126 
single_source_dijkstra_path()

127 
single_source_bellman_ford_path()

128 
"""

129 
if method not in ('dijkstra', 'bellmanford'): 
130 
# so we don't need to check in each branch later

131 
raise ValueError('method not supported: {}'.format(method)) 
132 
method = 'unweighted' if weight is None else method 
133 
if source is None: 
134 
if target is None: 
135 
# Find paths between all pairs.

136 
if method == 'unweighted': 
137 
paths = dict(nx.all_pairs_shortest_path(G))

138 
elif method == 'dijkstra': 
139 
paths = dict(nx.all_pairs_dijkstra_path(G, weight=weight))

140 
else: # method == 'bellmanford': 
141 
paths = dict(nx.all_pairs_bellman_ford_path(G, weight=weight))

142 
else:

143 
# Find paths from all nodes coaccessible to the target.

144 
with nx.utils.reversed(G):

145 
if method == 'unweighted': 
146 
paths = nx.single_source_shortest_path(G, target) 
147 
elif method == 'dijkstra': 
148 
paths = nx.single_source_dijkstra_path(G, target, 
149 
weight=weight) 
150 
else: # method == 'bellmanford': 
151 
paths = nx.single_source_bellman_ford_path(G, target, 
152 
weight=weight) 
153 
# Now flip the paths so they go from a source to the target.

154 
for target in paths: 
155 
paths[target] = list(reversed(paths[target])) 
156 
else:

157 
if target is None: 
158 
# Find paths to all nodes accessible from the source.

159 
if method == 'unweighted': 
160 
paths = nx.single_source_shortest_path(G, source) 
161 
elif method == 'dijkstra': 
162 
paths = nx.single_source_dijkstra_path(G, source, 
163 
weight=weight) 
164 
else: # method == 'bellmanford': 
165 
paths = nx.single_source_bellman_ford_path(G, source, 
166 
weight=weight) 
167 
else:

168 
# Find shortest sourcetarget path.

169 
if method == 'unweighted': 
170 
paths = nx.bidirectional_shortest_path(G, source, target) 
171 
elif method == 'dijkstra': 
172 
paths = nx.dijkstra_path(G, source, target, weight) 
173 
else: # method == 'bellmanford': 
174 
paths = nx.bellman_ford_path(G, source, target, weight) 
175 
return paths

176  
177  
178 
def shortest_path_length(G, 
179 
source=None,

180 
target=None,

181 
weight=None,

182 
method='dijkstra'):

183 
"""Compute shortest path lengths in the graph.

184 

185 
Parameters

186 


187 
G : NetworkX graph

188 

189 
source : node, optional

190 
Starting node for path.

191 
If not specified, compute shortest path lengths using all nodes as

192 
source nodes.

193 

194 
target : node, optional

195 
Ending node for path.

196 
If not specified, compute shortest path lengths using all nodes as

197 
target nodes.

198 

199 
weight : None or string, optional (default = None)

200 
If None, every edge has weight/distance/cost 1.

201 
If a string, use this edge attribute as the edge weight.

202 
Any edge attribute not present defaults to 1.

203 

204 
method : string, optional (default = 'dijkstra')

205 
The algorithm to use to compute the path length.

206 
Supported options: 'dijkstra', 'bellmanford'.

207 
Other inputs produce a ValueError.

208 
If `weight` is None, unweighted graph methods are used, and this

209 
suggestion is ignored.

210 

211 
Returns

212 


213 
length: int or iterator

214 
If the source and target are both specified, return the length of

215 
the shortest path from the source to the target.

216 

217 
If only the source is specified, return a dict keyed by target

218 
to the shortest path length from the source to that target.

219 

220 
If only the target is specified, return a dict keyed by source

221 
to the shortest path length from that source to the target.

222 

223 
If neither the source nor target are specified, return an iterator

224 
over (source, dictionary) where dictionary is keyed by target to

225 
shortest path length from source to that target.

226 

227 
Raises

228 


229 
NodeNotFound

230 
If `source` is not in `G`.

231 

232 
NetworkXNoPath

233 
If no path exists between source and target.

234 

235 
ValueError

236 
If `method` is not among the supported options.

237 

238 
Examples

239 


240 
>>> G = nx.path_graph(5)

241 
>>> nx.shortest_path_length(G, source=0, target=4)

242 
4

243 
>>> p = nx.shortest_path_length(G, source=0) # target not specified

244 
>>> p[4]

245 
4

246 
>>> p = nx.shortest_path_length(G, target=4) # source not specified

247 
>>> p[0]

248 
4

249 
>>> p = dict(nx.shortest_path_length(G)) # source,target not specified

250 
>>> p[0][4]

251 
4

252 

253 
Notes

254 


255 
The length of the path is always 1 less than the number of nodes involved

256 
in the path since the length measures the number of edges followed.

257 

258 
For digraphs this returns the shortest directed path length. To find path

259 
lengths in the reverse direction use G.reverse(copy=False) first to flip

260 
the edge orientation.

261 

262 
See Also

263 


264 
all_pairs_shortest_path_length()

265 
all_pairs_dijkstra_path_length()

266 
all_pairs_bellman_ford_path_length()

267 
single_source_shortest_path_length()

268 
single_source_dijkstra_path_length()

269 
single_source_bellman_ford_path_length()

270 
"""

271 
if method not in ('dijkstra', 'bellmanford'): 
272 
# so we don't need to check in each branch later

273 
raise ValueError('method not supported: {}'.format(method)) 
274 
method = 'unweighted' if weight is None else method 
275 
if source is None: 
276 
if target is None: 
277 
# Find paths between all pairs.

278 
if method == 'unweighted': 
279 
paths = nx.all_pairs_shortest_path_length(G) 
280 
elif method == 'dijkstra': 
281 
paths = nx.all_pairs_dijkstra_path_length(G, weight=weight) 
282 
else: # method == 'bellmanford': 
283 
paths = nx.all_pairs_bellman_ford_path_length(G, weight=weight) 
284 
else:

285 
# Find paths from all nodes coaccessible to the target.

286 
with nx.utils.reversed(G):

287 
if method == 'unweighted': 
288 
# We need to exhaust the iterator as Graph needs

289 
# to be reversed.

290 
path_length = nx.single_source_shortest_path_length 
291 
paths = path_length(G, target) 
292 
elif method == 'dijkstra': 
293 
path_length = nx.single_source_dijkstra_path_length 
294 
paths = path_length(G, target, weight=weight) 
295 
else: # method == 'bellmanford': 
296 
path_length = nx.single_source_bellman_ford_path_length 
297 
paths = path_length(G, target, weight=weight) 
298 
else:

299 
if target is None: 
300 
# Find paths to all nodes accessible from the source.

301 
if method == 'unweighted': 
302 
paths = nx.single_source_shortest_path_length(G, source) 
303 
elif method == 'dijkstra': 
304 
path_length = nx.single_source_dijkstra_path_length 
305 
paths = path_length(G, source, weight=weight) 
306 
else: # method == 'bellmanford': 
307 
path_length = nx.single_source_bellman_ford_path_length 
308 
paths = path_length(G, source, weight=weight) 
309 
else:

310 
# Find shortest sourcetarget path.

311 
if method == 'unweighted': 
312 
p = nx.bidirectional_shortest_path(G, source, target) 
313 
paths = len(p)  1 
314 
elif method == 'dijkstra': 
315 
paths = nx.dijkstra_path_length(G, source, target, weight) 
316 
else: # method == 'bellmanford': 
317 
paths = nx.bellman_ford_path_length(G, source, target, weight) 
318 
return paths

319  
320  
321 
def average_shortest_path_length(G, weight=None, method='dijkstra'): 
322 
r"""Returns the average shortest path length.

323 

324 
The average shortest path length is

325 

326 
.. math::

327 

328 
a =\sum_{s,t \in V} \frac{d(s, t)}{n(n1)}

329 

330 
where `V` is the set of nodes in `G`,

331 
`d(s, t)` is the shortest path from `s` to `t`,

332 
and `n` is the number of nodes in `G`.

333 

334 
Parameters

335 


336 
G : NetworkX graph

337 

338 
weight : None or string, optional (default = None)

339 
If None, every edge has weight/distance/cost 1.

340 
If a string, use this edge attribute as the edge weight.

341 
Any edge attribute not present defaults to 1.

342 

343 
method : string, optional (default = 'dijkstra')

344 
The algorithm to use to compute the path lengths.

345 
Supported options: 'dijkstra', 'bellmanford'.

346 
Other inputs produce a ValueError.

347 
If `weight` is None, unweighted graph methods are used, and this

348 
suggestion is ignored.

349 

350 
Raises

351 


352 
NetworkXPointlessConcept

353 
If `G` is the null graph (that is, the graph on zero nodes).

354 

355 
NetworkXError

356 
If `G` is not connected (or not weakly connected, in the case

357 
of a directed graph).

358 

359 
ValueError

360 
If `method` is not among the supported options.

361 

362 
Examples

363 


364 
>>> G = nx.path_graph(5)

365 
>>> nx.average_shortest_path_length(G)

366 
2.0

367 

368 
For disconnected graphs, you can compute the average shortest path

369 
length for each component

370 

371 
>>> G = nx.Graph([(1, 2), (3, 4)])

372 
>>> for C in nx.connected_component_subgraphs(G):

373 
... print(nx.average_shortest_path_length(C))

374 
1.0

375 
1.0

376 

377 
"""

378 
method = 'unweighted' if weight is None else method 
379 
n = len(G)

380 
# For the special case of the null graph, raise an exception, since

381 
# there are no paths in the null graph.

382 
if n == 0: 
383 
msg = ('the null graph has no paths, thus there is no average'

384 
'shortest path length')

385 
raise nx.NetworkXPointlessConcept(msg)

386 
# For the special case of the trivial graph, return zero immediately.

387 
if n == 1: 
388 
return 0 
389 
# Shortest path length is undefined if the graph is disconnected.

390 
if G.is_directed() and not nx.is_weakly_connected(G): 
391 
raise nx.NetworkXError("Graph is not weakly connected.") 
392 
if not G.is_directed() and not nx.is_connected(G): 
393 
raise nx.NetworkXError("Graph is not connected.") 
394 
# Compute allpairs shortest paths.

395  
396 
def path_length(v): 
397 
if method == 'unweighted': 
398 
return nx.single_source_shortest_path_length(G, v)

399 
elif method == 'dijkstra': 
400 
return nx.single_source_dijkstra_path_length(G, v, weight=weight)

401 
elif method == 'bellmanford': 
402 
return nx.single_source_bellman_ford_path_length(G, v,

403 
weight=weight) 
404 
else:

405 
raise ValueError('method not supported: {}'.format(method)) 
406 
# Sum the distances for each (ordered) pair of source and target node.

407 
s = sum(l for u in G for l in path_length(u).values()) 
408 
return s / (n * (n  1)) 
409  
410  
411 
def all_shortest_paths(G, source, target, weight=None, method='dijkstra'): 
412 
"""Compute all shortest paths in the graph.

413 

414 
Parameters

415 


416 
G : NetworkX graph

417 

418 
source : node

419 
Starting node for path.

420 

421 
target : node

422 
Ending node for path.

423 

424 
weight : None or string, optional (default = None)

425 
If None, every edge has weight/distance/cost 1.

426 
If a string, use this edge attribute as the edge weight.

427 
Any edge attribute not present defaults to 1.

428 

429 
method : string, optional (default = 'dijkstra')

430 
The algorithm to use to compute the path lengths.

431 
Supported options: 'dijkstra', 'bellmanford'.

432 
Other inputs produce a ValueError.

433 
If `weight` is None, unweighted graph methods are used, and this

434 
suggestion is ignored.

435 

436 
Returns

437 


438 
paths : generator of lists

439 
A generator of all paths between source and target.

440 

441 
Raises

442 


443 
ValueError

444 
If `method` is not among the supported options.

445 

446 
NetworkXNoPath

447 
If `target` cannot be reached from `source`.

448 

449 
Examples

450 


451 
>>> G = nx.Graph()

452 
>>> nx.add_path(G, [0, 1, 2])

453 
>>> nx.add_path(G, [0, 10, 2])

454 
>>> print([p for p in nx.all_shortest_paths(G, source=0, target=2)])

455 
[[0, 1, 2], [0, 10, 2]]

456 

457 
Notes

458 


459 
There may be many shortest paths between the source and target.

460 

461 
See Also

462 


463 
shortest_path()

464 
single_source_shortest_path()

465 
all_pairs_shortest_path()

466 
"""

467 
method = 'unweighted' if weight is None else method 
468 
if method == 'unweighted': 
469 
pred = nx.predecessor(G, source) 
470 
elif method == 'dijkstra': 
471 
pred, dist = nx.dijkstra_predecessor_and_distance(G, source, 
472 
weight=weight) 
473 
elif method == 'bellmanford': 
474 
pred, dist = nx.bellman_ford_predecessor_and_distance(G, source, 
475 
weight=weight) 
476 
else:

477 
raise ValueError('method not supported: {}'.format(method)) 
478  
479 
if target not in pred: 
480 
raise nx.NetworkXNoPath('Target {} cannot be reached' 
481 
'from Source {}'.format(target, source))

482  
483 
stack = [[target, 0]]

484 
top = 0

485 
while top >= 0: 
486 
node, i = stack[top] 
487 
if node == source:

488 
yield [p for p, n in reversed(stack[:top + 1])] 
489 
if len(pred[node]) > i: 
490 
top += 1

491 
if top == len(stack): 
492 
stack.append([pred[node][i], 0])

493 
else:

494 
stack[top] = [pred[node][i], 0]

495 
else:

496 
stack[top  1][1] += 1 
497 
top = 1
