I often find myself using common graph search algorithms like A* for tasks like path planning. However, in these contexts it would generally be impractical to define the entire graph in advance; rather, I usually have a function which can dynamically determine the neighbors of a given node (i.e. state transitions).

I haven't yet found a library designed for graph search under these conditions (NetworkX and Altgraph, e.g., generally seem to require the user to explicitly define the entire graph to search in it) and therefore usually end up implementing search algorithms myself. Is there a Python library optimized for this kind of graph search?

Sample implementation, so to show the sort of thing I'd use it for:

def heuristic_search(start, neighbors, goal, min_dist, heuristic=euclidean_distance_func, max_iters=100000, astar = False):
    Graph search using a heuristic

    :param astar: Whether to use A* or pure heuristic search
    :param start: Start node
    :param neighbors: Function to yield neighbors (actions and associated state transitions) of a node
    :param goal: Goal node
    :param min_dist: Goal distance from goal node
    :param heuristic: Function to estimate distance between two nodes
    :param max_iters: Max # of iterations

    :return: Path of actions from start to goal

    parents = {start: None}
    frontier = [(heuristic(start, goal), 0, start)] #priority, path_dist, node                                  

    i = 1

    while frontier and i <= max_iters:

        priority, path_dist, node = heapq.heappop(frontier)

        print("Iteration {}: node {} \n\t heuristic {}, path length {}".format(i, node, priority, path_dist))

        if distance(node, goal) < min_dist:
            path = []
            while parents[node] is not None:
                node, action = parents[node]

            return reversed(path)

        for neighbor, action in neighbors(node):

            if neighbor not in parents:
                parents[neighbor] = node, action

                neighbor_path_dist = path_dist + heuristic(neighbor, node)

                priority = heuristic(neighbor, goal)
                if astar:
                    priority += neighbor_path_dist

                heapq.heappush(frontier, (priority, neighbor_path_dist, neighbor))

        i += 1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.