Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/shortest_paths/dense.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 """Floyd-Warshall algorithm for shortest paths. | |
2 """ | |
3 import networkx as nx | |
4 | |
5 __all__ = [ | |
6 "floyd_warshall", | |
7 "floyd_warshall_predecessor_and_distance", | |
8 "reconstruct_path", | |
9 "floyd_warshall_numpy", | |
10 ] | |
11 | |
12 | |
13 def floyd_warshall_numpy(G, nodelist=None, weight="weight"): | |
14 """Find all-pairs shortest path lengths using Floyd's algorithm. | |
15 | |
16 Parameters | |
17 ---------- | |
18 G : NetworkX graph | |
19 | |
20 nodelist : list, optional | |
21 The rows and columns are ordered by the nodes in nodelist. | |
22 If nodelist is None then the ordering is produced by G.nodes(). | |
23 | |
24 weight: string, optional (default= 'weight') | |
25 Edge data key corresponding to the edge weight. | |
26 | |
27 Returns | |
28 ------- | |
29 distance : NumPy matrix | |
30 A matrix of shortest path distances between nodes. | |
31 If there is no path between to nodes the corresponding matrix entry | |
32 will be Inf. | |
33 | |
34 Notes | |
35 ------ | |
36 Floyd's algorithm is appropriate for finding shortest paths in | |
37 dense graphs or graphs with negative weights when Dijkstra's | |
38 algorithm fails. This algorithm can still fail if there are negative | |
39 cycles. It has running time $O(n^3)$ with running space of $O(n^2)$. | |
40 """ | |
41 try: | |
42 import numpy as np | |
43 except ImportError as e: | |
44 raise ImportError("to_numpy_array() requires numpy: http://numpy.org/ ") from e | |
45 | |
46 # To handle cases when an edge has weight=0, we must make sure that | |
47 # nonedges are not given the value 0 as well. | |
48 A = nx.to_numpy_array( | |
49 G, nodelist=nodelist, multigraph_weight=min, weight=weight, nonedge=np.inf | |
50 ) | |
51 n, m = A.shape | |
52 np.fill_diagonal(A, 0) # diagonal elements should be zero | |
53 for i in range(n): | |
54 # The second term has the same shape as A due to broadcasting | |
55 A = np.minimum(A, A[i, :][np.newaxis, :] + A[:, i][:, np.newaxis]) | |
56 return A | |
57 | |
58 | |
59 def floyd_warshall_predecessor_and_distance(G, weight="weight"): | |
60 """Find all-pairs shortest path lengths using Floyd's algorithm. | |
61 | |
62 Parameters | |
63 ---------- | |
64 G : NetworkX graph | |
65 | |
66 weight: string, optional (default= 'weight') | |
67 Edge data key corresponding to the edge weight. | |
68 | |
69 Returns | |
70 ------- | |
71 predecessor,distance : dictionaries | |
72 Dictionaries, keyed by source and target, of predecessors and distances | |
73 in the shortest path. | |
74 | |
75 Examples | |
76 -------- | |
77 >>> G = nx.DiGraph() | |
78 >>> G.add_weighted_edges_from( | |
79 ... [ | |
80 ... ("s", "u", 10), | |
81 ... ("s", "x", 5), | |
82 ... ("u", "v", 1), | |
83 ... ("u", "x", 2), | |
84 ... ("v", "y", 1), | |
85 ... ("x", "u", 3), | |
86 ... ("x", "v", 5), | |
87 ... ("x", "y", 2), | |
88 ... ("y", "s", 7), | |
89 ... ("y", "v", 6), | |
90 ... ] | |
91 ... ) | |
92 >>> predecessors, _ = nx.floyd_warshall_predecessor_and_distance(G) | |
93 >>> print(nx.reconstruct_path("s", "v", predecessors)) | |
94 ['s', 'x', 'u', 'v'] | |
95 | |
96 Notes | |
97 ------ | |
98 Floyd's algorithm is appropriate for finding shortest paths | |
99 in dense graphs or graphs with negative weights when Dijkstra's algorithm | |
100 fails. This algorithm can still fail if there are negative cycles. | |
101 It has running time $O(n^3)$ with running space of $O(n^2)$. | |
102 | |
103 See Also | |
104 -------- | |
105 floyd_warshall | |
106 floyd_warshall_numpy | |
107 all_pairs_shortest_path | |
108 all_pairs_shortest_path_length | |
109 """ | |
110 from collections import defaultdict | |
111 | |
112 # dictionary-of-dictionaries representation for dist and pred | |
113 # use some defaultdict magick here | |
114 # for dist the default is the floating point inf value | |
115 dist = defaultdict(lambda: defaultdict(lambda: float("inf"))) | |
116 for u in G: | |
117 dist[u][u] = 0 | |
118 pred = defaultdict(dict) | |
119 # initialize path distance dictionary to be the adjacency matrix | |
120 # also set the distance to self to 0 (zero diagonal) | |
121 undirected = not G.is_directed() | |
122 for u, v, d in G.edges(data=True): | |
123 e_weight = d.get(weight, 1.0) | |
124 dist[u][v] = min(e_weight, dist[u][v]) | |
125 pred[u][v] = u | |
126 if undirected: | |
127 dist[v][u] = min(e_weight, dist[v][u]) | |
128 pred[v][u] = v | |
129 for w in G: | |
130 dist_w = dist[w] # save recomputation | |
131 for u in G: | |
132 dist_u = dist[u] # save recomputation | |
133 for v in G: | |
134 d = dist_u[w] + dist_w[v] | |
135 if dist_u[v] > d: | |
136 dist_u[v] = d | |
137 pred[u][v] = pred[w][v] | |
138 return dict(pred), dict(dist) | |
139 | |
140 | |
141 def reconstruct_path(source, target, predecessors): | |
142 """Reconstruct a path from source to target using the predecessors | |
143 dict as returned by floyd_warshall_predecessor_and_distance | |
144 | |
145 Parameters | |
146 ---------- | |
147 source : node | |
148 Starting node for path | |
149 | |
150 target : node | |
151 Ending node for path | |
152 | |
153 predecessors: dictionary | |
154 Dictionary, keyed by source and target, of predecessors in the | |
155 shortest path, as returned by floyd_warshall_predecessor_and_distance | |
156 | |
157 Returns | |
158 ------- | |
159 path : list | |
160 A list of nodes containing the shortest path from source to target | |
161 | |
162 If source and target are the same, an empty list is returned | |
163 | |
164 Notes | |
165 ------ | |
166 This function is meant to give more applicability to the | |
167 floyd_warshall_predecessor_and_distance function | |
168 | |
169 See Also | |
170 -------- | |
171 floyd_warshall_predecessor_and_distance | |
172 """ | |
173 if source == target: | |
174 return [] | |
175 prev = predecessors[source] | |
176 curr = prev[target] | |
177 path = [target, curr] | |
178 while curr != source: | |
179 curr = prev[curr] | |
180 path.append(curr) | |
181 return list(reversed(path)) | |
182 | |
183 | |
184 def floyd_warshall(G, weight="weight"): | |
185 """Find all-pairs shortest path lengths using Floyd's algorithm. | |
186 | |
187 Parameters | |
188 ---------- | |
189 G : NetworkX graph | |
190 | |
191 weight: string, optional (default= 'weight') | |
192 Edge data key corresponding to the edge weight. | |
193 | |
194 | |
195 Returns | |
196 ------- | |
197 distance : dict | |
198 A dictionary, keyed by source and target, of shortest paths distances | |
199 between nodes. | |
200 | |
201 Notes | |
202 ------ | |
203 Floyd's algorithm is appropriate for finding shortest paths | |
204 in dense graphs or graphs with negative weights when Dijkstra's algorithm | |
205 fails. This algorithm can still fail if there are negative cycles. | |
206 It has running time $O(n^3)$ with running space of $O(n^2)$. | |
207 | |
208 See Also | |
209 -------- | |
210 floyd_warshall_predecessor_and_distance | |
211 floyd_warshall_numpy | |
212 all_pairs_shortest_path | |
213 all_pairs_shortest_path_length | |
214 """ | |
215 # could make this its own function to reduce memory costs | |
216 return floyd_warshall_predecessor_and_distance(G, weight=weight)[1] |