Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (6.59 KB)

1
# -*- coding: utf-8 -*-
2
"""Floyd-Warshall algorithm for shortest paths.
3
"""
4
#    Copyright (C) 2004-2019 by
5
#    Aric Hagberg <hagberg@lanl.gov>
6
#    Dan Schult <dschult@colgate.edu>
7
#    Pieter Swart <swart@lanl.gov>
8
#    All rights reserved.
9
#    BSD license.
10
#
11
# Authors: Aric Hagberg <aric.hagberg@gmail.com>
12
#          Miguel Sozinho Ramalho <m.ramalho@fe.up.pt>
13
import networkx as nx
14

    
15
__all__ = ['floyd_warshall',
16
           'floyd_warshall_predecessor_and_distance',
17
           'reconstruct_path',
18
           'floyd_warshall_numpy']
19

    
20

    
21
def floyd_warshall_numpy(G, nodelist=None, weight='weight'):
22
    """Find all-pairs shortest path lengths using Floyd's algorithm.
23

24
    Parameters
25
    ----------
26
    G : NetworkX graph
27

28
    nodelist : list, optional
29
       The rows and columns are ordered by the nodes in nodelist.
30
       If nodelist is None then the ordering is produced by G.nodes().
31

32
    weight: string, optional (default= 'weight')
33
       Edge data key corresponding to the edge weight.
34

35
    Returns
36
    -------
37
    distance : NumPy matrix
38
        A matrix of shortest path distances between nodes.
39
        If there is no path between to nodes the corresponding matrix entry
40
        will be Inf.
41

42
    Notes
43
    ------
44
    Floyd's algorithm is appropriate for finding shortest paths in
45
    dense graphs or graphs with negative weights when Dijkstra's
46
    algorithm fails.  This algorithm can still fail if there are
47
    negative cycles.  It has running time $O(n^3)$ with running space of $O(n^2)$.
48
    """
49
    try:
50
        import numpy as np
51
    except ImportError:
52
        raise ImportError(
53
            "to_numpy_matrix() requires numpy: http://scipy.org/ ")
54

    
55
    # To handle cases when an edge has weight=0, we must make sure that
56
    # nonedges are not given the value 0 as well.
57
    A = nx.to_numpy_matrix(G, nodelist=nodelist, multigraph_weight=min,
58
                           weight=weight, nonedge=np.inf)
59
    n, m = A.shape
60
    I = np.identity(n)
61
    A[I == 1] = 0  # diagonal elements should be zero
62
    for i in range(n):
63
        A = np.minimum(A, A[i, :] + A[:, i])
64
    return A
65

    
66

    
67
def floyd_warshall_predecessor_and_distance(G, weight='weight'):
68
    """Find all-pairs shortest path lengths using Floyd's algorithm.
69

70
    Parameters
71
    ----------
72
    G : NetworkX graph
73

74
    weight: string, optional (default= 'weight')
75
       Edge data key corresponding to the edge weight.
76

77
    Returns
78
    -------
79
    predecessor,distance : dictionaries
80
       Dictionaries, keyed by source and target, of predecessors and distances
81
       in the shortest path.
82

83
    Examples
84
    --------
85
    >>> G = nx.DiGraph()
86
    >>> G.add_weighted_edges_from([('s', 'u', 10), ('s', 'x', 5),
87
    ...     ('u', 'v', 1), ('u', 'x', 2), ('v', 'y', 1), ('x', 'u', 3),
88
    ...     ('x', 'v', 5), ('x', 'y', 2), ('y', 's', 7), ('y', 'v', 6)])
89
    >>> predecessors, _ = nx.floyd_warshall_predecessor_and_distance(G)
90
    >>> print(nx.reconstruct_path('s', 'v', predecessors))
91
    ['s', 'x', 'u', 'v']
92

93
    Notes
94
    ------
95
    Floyd's algorithm is appropriate for finding shortest paths
96
    in dense graphs or graphs with negative weights when Dijkstra's algorithm
97
    fails.  This algorithm can still fail if there are negative cycles.
98
    It has running time $O(n^3)$ with running space of $O(n^2)$.
99

100
    See Also
101
    --------
102
    floyd_warshall
103
    floyd_warshall_numpy
104
    all_pairs_shortest_path
105
    all_pairs_shortest_path_length
106
    """
107
    from collections import defaultdict
108
    # dictionary-of-dictionaries representation for dist and pred
109
    # use some defaultdict magick here
110
    # for dist the default is the floating point inf value
111
    dist = defaultdict(lambda: defaultdict(lambda: float('inf')))
112
    for u in G:
113
        dist[u][u] = 0
114
    pred = defaultdict(dict)
115
    # initialize path distance dictionary to be the adjacency matrix
116
    # also set the distance to self to 0 (zero diagonal)
117
    undirected = not G.is_directed()
118
    for u, v, d in G.edges(data=True):
119
        e_weight = d.get(weight, 1.0)
120
        dist[u][v] = min(e_weight, dist[u][v])
121
        pred[u][v] = u
122
        if undirected:
123
            dist[v][u] = min(e_weight, dist[v][u])
124
            pred[v][u] = v
125
    for w in G:
126
        for u in G:
127
            for v in G:
128
                if dist[u][v] > dist[u][w] + dist[w][v]:
129
                    dist[u][v] = dist[u][w] + dist[w][v]
130
                    pred[u][v] = pred[w][v]
131
    return dict(pred), dict(dist)
132

    
133

    
134
def reconstruct_path(source, target, predecessors):
135
    """Reconstruct a path from source to target using the predecessors
136
    dict as returned by floyd_warshall_predecessor_and_distance
137

138
    Parameters
139
    ----------
140
    source : node
141
       Starting node for path
142

143
    target : node
144
       Ending node for path
145

146
    predecessors: dictionary
147
       Dictionary, keyed by source and target, of predecessors in the
148
       shortest path, as returned by floyd_warshall_predecessor_and_distance
149

150
    Returns
151
    -------
152
    path : list
153
       A list of nodes containing the shortest path from source to target
154

155
       If source and target are the same, an empty list is returned
156

157
    Notes
158
    ------
159
    This function is meant to give more applicability to the
160
    floyd_warshall_predecessor_and_distance function
161

162
    See Also
163
    --------
164
    floyd_warshall_predecessor_and_distance
165
    """
166
    if source == target:
167
        return []
168
    prev = predecessors[source]
169
    curr = prev[target]
170
    path = [target, curr]
171
    while curr != source:
172
        curr = prev[curr]
173
        path.append(curr)
174
    return list(reversed(path))
175

    
176

    
177
def floyd_warshall(G, weight='weight'):
178
    """Find all-pairs shortest path lengths using Floyd's algorithm.
179

180
    Parameters
181
    ----------
182
    G : NetworkX graph
183

184
    weight: string, optional (default= 'weight')
185
       Edge data key corresponding to the edge weight.
186

187

188
    Returns
189
    -------
190
    distance : dict
191
       A dictionary,  keyed by source and target, of shortest paths distances
192
       between nodes.
193

194
    Notes
195
    ------
196
    Floyd's algorithm is appropriate for finding shortest paths
197
    in dense graphs or graphs with negative weights when Dijkstra's algorithm
198
    fails.  This algorithm can still fail if there are negative cycles.
199
    It has running time $O(n^3)$ with running space of $O(n^2)$.
200

201
    See Also
202
    --------
203
    floyd_warshall_predecessor_and_distance
204
    floyd_warshall_numpy
205
    all_pairs_shortest_path
206
    all_pairs_shortest_path_length
207
    """
208
    # could make this its own function to reduce memory costs
209
    return floyd_warshall_predecessor_and_distance(G, weight=weight)[1]
210

    
211
# fixture for nose tests
212

    
213

    
214
def setup_module(module):
215
    from nose import SkipTest
216
    try:
217
        import numpy
218
    except:
219
        raise SkipTest("NumPy not available")