Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/shortest_paths/astar.py: 15%
59 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1"""Shortest paths and path lengths using the A* ("A star") algorithm.
2"""
3from heapq import heappop, heappush
4from itertools import count
6import networkx as nx
7from networkx.algorithms.shortest_paths.weighted import _weight_function
9__all__ = ["astar_path", "astar_path_length"]
12@nx._dispatch(edge_attrs="weight", preserve_node_attrs="heuristic")
13def astar_path(G, source, target, heuristic=None, weight="weight"):
14 """Returns a list of nodes in a shortest path between source and target
15 using the A* ("A-star") algorithm.
17 There may be more than one shortest path. This returns only one.
19 Parameters
20 ----------
21 G : NetworkX graph
23 source : node
24 Starting node for path
26 target : node
27 Ending node for path
29 heuristic : function
30 A function to evaluate the estimate of the distance
31 from the a node to the target. The function takes
32 two nodes arguments and must return a number.
33 If the heuristic is inadmissible (if it might
34 overestimate the cost of reaching the goal from a node),
35 the result may not be a shortest path.
36 The algorithm does not support updating heuristic
37 values for the same node due to caching the first
38 heuristic calculation per node.
40 weight : string or function
41 If this is a string, then edge weights will be accessed via the
42 edge attribute with this key (that is, the weight of the edge
43 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
44 such edge attribute exists, the weight of the edge is assumed to
45 be one.
46 If this is a function, the weight of an edge is the value
47 returned by the function. The function must accept exactly three
48 positional arguments: the two endpoints of an edge and the
49 dictionary of edge attributes for that edge. The function must
50 return a number or None to indicate a hidden edge.
52 Raises
53 ------
54 NetworkXNoPath
55 If no path exists between source and target.
57 Examples
58 --------
59 >>> G = nx.path_graph(5)
60 >>> print(nx.astar_path(G, 0, 4))
61 [0, 1, 2, 3, 4]
62 >>> G = nx.grid_graph(dim=[3, 3]) # nodes are two-tuples (x,y)
63 >>> nx.set_edge_attributes(G, {e: e[1][0] * 2 for e in G.edges()}, "cost")
64 >>> def dist(a, b):
65 ... (x1, y1) = a
66 ... (x2, y2) = b
67 ... return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5
68 >>> print(nx.astar_path(G, (0, 0), (2, 2), heuristic=dist, weight="cost"))
69 [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2)]
71 Notes
72 -----
73 Edge weight attributes must be numerical.
74 Distances are calculated as sums of weighted edges traversed.
76 The weight function can be used to hide edges by returning None.
77 So ``weight = lambda u, v, d: 1 if d['color']=="red" else None``
78 will find the shortest red path.
80 See Also
81 --------
82 shortest_path, dijkstra_path
84 """
85 if source not in G or target not in G:
86 msg = f"Either source {source} or target {target} is not in G"
87 raise nx.NodeNotFound(msg)
89 if heuristic is None:
90 # The default heuristic is h=0 - same as Dijkstra's algorithm
91 def heuristic(u, v):
92 return 0
94 push = heappush
95 pop = heappop
96 weight = _weight_function(G, weight)
98 G_succ = G._adj # For speed-up (and works for both directed and undirected graphs)
100 # The queue stores priority, node, cost to reach, and parent.
101 # Uses Python heapq to keep in priority order.
102 # Add a counter to the queue to prevent the underlying heap from
103 # attempting to compare the nodes themselves. The hash breaks ties in the
104 # priority and is guaranteed unique for all nodes in the graph.
105 c = count()
106 queue = [(0, next(c), source, 0, None)]
108 # Maps enqueued nodes to distance of discovered paths and the
109 # computed heuristics to target. We avoid computing the heuristics
110 # more than once and inserting the node into the queue too many times.
111 enqueued = {}
112 # Maps explored nodes to parent closest to the source.
113 explored = {}
115 while queue:
116 # Pop the smallest item from queue.
117 _, __, curnode, dist, parent = pop(queue)
119 if curnode == target:
120 path = [curnode]
121 node = parent
122 while node is not None:
123 path.append(node)
124 node = explored[node]
125 path.reverse()
126 return path
128 if curnode in explored:
129 # Do not override the parent of starting node
130 if explored[curnode] is None:
131 continue
133 # Skip bad paths that were enqueued before finding a better one
134 qcost, h = enqueued[curnode]
135 if qcost < dist:
136 continue
138 explored[curnode] = parent
140 for neighbor, w in G_succ[curnode].items():
141 cost = weight(curnode, neighbor, w)
142 if cost is None:
143 continue
144 ncost = dist + cost
145 if neighbor in enqueued:
146 qcost, h = enqueued[neighbor]
147 # if qcost <= ncost, a less costly path from the
148 # neighbor to the source was already determined.
149 # Therefore, we won't attempt to push this neighbor
150 # to the queue
151 if qcost <= ncost:
152 continue
153 else:
154 h = heuristic(neighbor, target)
155 enqueued[neighbor] = ncost, h
156 push(queue, (ncost + h, next(c), neighbor, ncost, curnode))
158 raise nx.NetworkXNoPath(f"Node {target} not reachable from {source}")
161@nx._dispatch(edge_attrs="weight", preserve_node_attrs="heuristic")
162def astar_path_length(G, source, target, heuristic=None, weight="weight"):
163 """Returns the length of the shortest path between source and target using
164 the A* ("A-star") algorithm.
166 Parameters
167 ----------
168 G : NetworkX graph
170 source : node
171 Starting node for path
173 target : node
174 Ending node for path
176 heuristic : function
177 A function to evaluate the estimate of the distance
178 from the a node to the target. The function takes
179 two nodes arguments and must return a number.
180 If the heuristic is inadmissible (if it might
181 overestimate the cost of reaching the goal from a node),
182 the result may not be a shortest path.
183 The algorithm does not support updating heuristic
184 values for the same node due to caching the first
185 heuristic calculation per node.
187 weight : string or function
188 If this is a string, then edge weights will be accessed via the
189 edge attribute with this key (that is, the weight of the edge
190 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
191 such edge attribute exists, the weight of the edge is assumed to
192 be one.
193 If this is a function, the weight of an edge is the value
194 returned by the function. The function must accept exactly three
195 positional arguments: the two endpoints of an edge and the
196 dictionary of edge attributes for that edge. The function must
197 return a number or None to indicate a hidden edge.
198 Raises
199 ------
200 NetworkXNoPath
201 If no path exists between source and target.
203 See Also
204 --------
205 astar_path
207 """
208 if source not in G or target not in G:
209 msg = f"Either source {source} or target {target} is not in G"
210 raise nx.NodeNotFound(msg)
212 weight = _weight_function(G, weight)
213 path = astar_path(G, source, target, heuristic, weight)
214 return sum(weight(u, v, G[u][v]) for u, v in zip(path[:-1], path[1:]))