Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (5.13 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: Salim Fadhley <salimfadhley@gmail.com>
10
#          Matteo Dell'Amico <matteodellamico@gmail.com>
11
"""Shortest paths and path lengths using the A* ("A star") algorithm.
12
"""
13
from heapq import heappush, heappop
14
from itertools import count
15

    
16
import networkx as nx
17
from networkx.utils import not_implemented_for
18

    
19
__all__ = ['astar_path', 'astar_path_length']
20

    
21

    
22
@not_implemented_for('multigraph')
23
def astar_path(G, source, target, heuristic=None, weight='weight'):
24
    """Returns a list of nodes in a shortest path between source and target
25
    using the A* ("A-star") algorithm.
26

27
    There may be more than one shortest path.  This returns only one.
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
    heuristic : function
40
       A function to evaluate the estimate of the distance
41
       from the a node to the target.  The function takes
42
       two nodes arguments and must return a number.
43

44
    weight: string, optional (default='weight')
45
       Edge data key corresponding to the edge weight.
46

47
    Raises
48
    ------
49
    NetworkXNoPath
50
        If no path exists between source and target.
51

52
    Examples
53
    --------
54
    >>> G = nx.path_graph(5)
55
    >>> print(nx.astar_path(G, 0, 4))
56
    [0, 1, 2, 3, 4]
57
    >>> G = nx.grid_graph(dim=[3, 3])  # nodes are two-tuples (x,y)
58
    >>> nx.set_edge_attributes(G, {e: e[1][0]*2 for e in G.edges()}, 'cost')
59
    >>> def dist(a, b):
60
    ...    (x1, y1) = a
61
    ...    (x2, y2) = b
62
    ...    return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5
63
    >>> print(nx.astar_path(G, (0, 0), (2, 2), heuristic=dist, weight='cost'))
64
    [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2)]
65

66

67
    See Also
68
    --------
69
    shortest_path, dijkstra_path
70

71
    """
72
    if source not in G or target not in G:
73
        msg = 'Either source {} or target {} is not in G'
74
        raise nx.NodeNotFound(msg.format(source, target))
75

    
76
    if heuristic is None:
77
        # The default heuristic is h=0 - same as Dijkstra's algorithm
78
        def heuristic(u, v):
79
            return 0
80

    
81
    push = heappush
82
    pop = heappop
83

    
84
    # The queue stores priority, node, cost to reach, and parent.
85
    # Uses Python heapq to keep in priority order.
86
    # Add a counter to the queue to prevent the underlying heap from
87
    # attempting to compare the nodes themselves. The hash breaks ties in the
88
    # priority and is guaranteed unique for all nodes in the graph.
89
    c = count()
90
    queue = [(0, next(c), source, 0, None)]
91

    
92
    # Maps enqueued nodes to distance of discovered paths and the
93
    # computed heuristics to target. We avoid computing the heuristics
94
    # more than once and inserting the node into the queue too many times.
95
    enqueued = {}
96
    # Maps explored nodes to parent closest to the source.
97
    explored = {}
98

    
99
    while queue:
100
        # Pop the smallest item from queue.
101
        _, __, curnode, dist, parent = pop(queue)
102

    
103
        if curnode == target:
104
            path = [curnode]
105
            node = parent
106
            while node is not None:
107
                path.append(node)
108
                node = explored[node]
109
            path.reverse()
110
            return path
111

    
112
        if curnode in explored:
113
            continue
114

    
115
        explored[curnode] = parent
116

    
117
        for neighbor, w in G[curnode].items():
118
            if neighbor in explored:
119
                continue
120
            ncost = dist + w.get(weight, 1)
121
            if neighbor in enqueued:
122
                qcost, h = enqueued[neighbor]
123
                # if qcost <= ncost, a less costly path from the
124
                # neighbor to the source was already determined.
125
                # Therefore, we won't attempt to push this neighbor
126
                # to the queue
127
                if qcost <= ncost:
128
                    continue
129
            else:
130
                h = heuristic(neighbor, target)
131
            enqueued[neighbor] = ncost, h
132
            push(queue, (ncost + h, next(c), neighbor, ncost, curnode))
133

    
134
    raise nx.NetworkXNoPath("Node %s not reachable from %s" % (target, source))
135

    
136

    
137
def astar_path_length(G, source, target, heuristic=None, weight='weight'):
138
    """Returns the length of the shortest path between source and target using
139
    the A* ("A-star") algorithm.
140

141
    Parameters
142
    ----------
143
    G : NetworkX graph
144

145
    source : node
146
       Starting node for path
147

148
    target : node
149
       Ending node for path
150

151
    heuristic : function
152
       A function to evaluate the estimate of the distance
153
       from the a node to the target.  The function takes
154
       two nodes arguments and must return a number.
155

156
    Raises
157
    ------
158
    NetworkXNoPath
159
        If no path exists between source and target.
160

161
    See Also
162
    --------
163
    astar_path
164

165
    """
166
    if source not in G or target not in G:
167
        msg = 'Either source {} or target {} is not in G'
168
        raise nx.NodeNotFound(msg.format(source, target))
169

    
170
    path = astar_path(G, source, target, heuristic, weight)
171
    return sum(G[u][v].get(weight, 1) for u, v in zip(path[:-1], path[1:]))