Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / shortest_paths / generic.py @ 5cef0f13

History | View | Annotate | Download (17.1 KB)

1
# -*- coding: utf-8 -*-
2
#    Copyright (C) 2004-2019 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', 'bellman-ford'.
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', 'bellman-ford'):
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 == 'bellman-ford':
141
                paths = dict(nx.all_pairs_bellman_ford_path(G, weight=weight))
142
        else:
143
            # Find paths from all nodes co-accessible 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 == 'bellman-ford':
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 == 'bellman-ford':
165
                paths = nx.single_source_bellman_ford_path(G, source,
166
                                                           weight=weight)
167
        else:
168
            # Find shortest source-target 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 == 'bellman-ford':
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', 'bellman-ford'.
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', 'bellman-ford'):
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 == 'bellman-ford':
283
                paths = nx.all_pairs_bellman_ford_path_length(G, weight=weight)
284
        else:
285
            # Find paths from all nodes co-accessible 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 == 'bellman-ford':
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 == 'bellman-ford':
307
                path_length = nx.single_source_bellman_ford_path_length
308
                paths = path_length(G, source, weight=weight)
309
        else:
310
            # Find shortest source-target 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 == 'bellman-ford':
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(n-1)}
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', 'bellman-ford'.
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 all-pairs 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 == 'bellman-ford':
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', 'bellman-ford'.
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 == 'bellman-ford':
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