Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/shortest_paths/astar.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 """Shortest paths and path lengths using the A* ("A star") algorithm. | |
2 """ | |
3 from heapq import heappush, heappop | |
4 from itertools import count | |
5 | |
6 import networkx as nx | |
7 from networkx.algorithms.shortest_paths.weighted import _weight_function | |
8 | |
9 __all__ = ["astar_path", "astar_path_length"] | |
10 | |
11 | |
12 def astar_path(G, source, target, heuristic=None, weight="weight"): | |
13 """Returns a list of nodes in a shortest path between source and target | |
14 using the A* ("A-star") algorithm. | |
15 | |
16 There may be more than one shortest path. This returns only one. | |
17 | |
18 Parameters | |
19 ---------- | |
20 G : NetworkX graph | |
21 | |
22 source : node | |
23 Starting node for path | |
24 | |
25 target : node | |
26 Ending node for path | |
27 | |
28 heuristic : function | |
29 A function to evaluate the estimate of the distance | |
30 from the a node to the target. The function takes | |
31 two nodes arguments and must return a number. | |
32 | |
33 weight : string or function | |
34 If this is a string, then edge weights will be accessed via the | |
35 edge attribute with this key (that is, the weight of the edge | |
36 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no | |
37 such edge attribute exists, the weight of the edge is assumed to | |
38 be one. | |
39 If this is a function, the weight of an edge is the value | |
40 returned by the function. The function must accept exactly three | |
41 positional arguments: the two endpoints of an edge and the | |
42 dictionary of edge attributes for that edge. The function must | |
43 return a number. | |
44 | |
45 Raises | |
46 ------ | |
47 NetworkXNoPath | |
48 If no path exists between source and target. | |
49 | |
50 Examples | |
51 -------- | |
52 >>> G = nx.path_graph(5) | |
53 >>> print(nx.astar_path(G, 0, 4)) | |
54 [0, 1, 2, 3, 4] | |
55 >>> G = nx.grid_graph(dim=[3, 3]) # nodes are two-tuples (x,y) | |
56 >>> nx.set_edge_attributes(G, {e: e[1][0] * 2 for e in G.edges()}, "cost") | |
57 >>> def dist(a, b): | |
58 ... (x1, y1) = a | |
59 ... (x2, y2) = b | |
60 ... return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5 | |
61 >>> print(nx.astar_path(G, (0, 0), (2, 2), heuristic=dist, weight="cost")) | |
62 [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2)] | |
63 | |
64 | |
65 See Also | |
66 -------- | |
67 shortest_path, dijkstra_path | |
68 | |
69 """ | |
70 if source not in G or target not in G: | |
71 msg = f"Either source {source} or target {target} is not in G" | |
72 raise nx.NodeNotFound(msg) | |
73 | |
74 if heuristic is None: | |
75 # The default heuristic is h=0 - same as Dijkstra's algorithm | |
76 def heuristic(u, v): | |
77 return 0 | |
78 | |
79 push = heappush | |
80 pop = heappop | |
81 weight = _weight_function(G, weight) | |
82 | |
83 # The queue stores priority, node, cost to reach, and parent. | |
84 # Uses Python heapq to keep in priority order. | |
85 # Add a counter to the queue to prevent the underlying heap from | |
86 # attempting to compare the nodes themselves. The hash breaks ties in the | |
87 # priority and is guaranteed unique for all nodes in the graph. | |
88 c = count() | |
89 queue = [(0, next(c), source, 0, None)] | |
90 | |
91 # Maps enqueued nodes to distance of discovered paths and the | |
92 # computed heuristics to target. We avoid computing the heuristics | |
93 # more than once and inserting the node into the queue too many times. | |
94 enqueued = {} | |
95 # Maps explored nodes to parent closest to the source. | |
96 explored = {} | |
97 | |
98 while queue: | |
99 # Pop the smallest item from queue. | |
100 _, __, curnode, dist, parent = pop(queue) | |
101 | |
102 if curnode == target: | |
103 path = [curnode] | |
104 node = parent | |
105 while node is not None: | |
106 path.append(node) | |
107 node = explored[node] | |
108 path.reverse() | |
109 return path | |
110 | |
111 if curnode in explored: | |
112 # Do not override the parent of starting node | |
113 if explored[curnode] is None: | |
114 continue | |
115 | |
116 # Skip bad paths that were enqueued before finding a better one | |
117 qcost, h = enqueued[curnode] | |
118 if qcost < dist: | |
119 continue | |
120 | |
121 explored[curnode] = parent | |
122 | |
123 for neighbor, w in G[curnode].items(): | |
124 ncost = dist + weight(curnode, neighbor, w) | |
125 if neighbor in enqueued: | |
126 qcost, h = enqueued[neighbor] | |
127 # if qcost <= ncost, a less costly path from the | |
128 # neighbor to the source was already determined. | |
129 # Therefore, we won't attempt to push this neighbor | |
130 # to the queue | |
131 if qcost <= ncost: | |
132 continue | |
133 else: | |
134 h = heuristic(neighbor, target) | |
135 enqueued[neighbor] = ncost, h | |
136 push(queue, (ncost + h, next(c), neighbor, ncost, curnode)) | |
137 | |
138 raise nx.NetworkXNoPath(f"Node {target} not reachable from {source}") | |
139 | |
140 | |
141 def astar_path_length(G, source, target, heuristic=None, weight="weight"): | |
142 """Returns the length of the shortest path between source and target using | |
143 the A* ("A-star") algorithm. | |
144 | |
145 Parameters | |
146 ---------- | |
147 G : NetworkX graph | |
148 | |
149 source : node | |
150 Starting node for path | |
151 | |
152 target : node | |
153 Ending node for path | |
154 | |
155 heuristic : function | |
156 A function to evaluate the estimate of the distance | |
157 from the a node to the target. The function takes | |
158 two nodes arguments and must return a number. | |
159 | |
160 Raises | |
161 ------ | |
162 NetworkXNoPath | |
163 If no path exists between source and target. | |
164 | |
165 See Also | |
166 -------- | |
167 astar_path | |
168 | |
169 """ | |
170 if source not in G or target not in G: | |
171 msg = f"Either source {source} or target {target} is not in G" | |
172 raise nx.NodeNotFound(msg) | |
173 | |
174 weight = _weight_function(G, weight) | |
175 path = astar_path(G, source, target, heuristic, weight) | |
176 return sum(weight(u, v, G[u][v]) for u, v in zip(path[:-1], path[1:])) |