A* algorithm implementation in modern C++

Question 1

I've written the A* search algorithm in C++. My goal is primarily writingconcise andunderstandable code, while making use of some new features ofmodern C++ (where appropriate) and having generallygood performance (importance of these goals in the order they were mentioned).

The goal of the algorithm is to find the best (cheapest) path from a starting node to a target node on a graph. The input to the algorithm is an adjacency list, start and target node IDs and an (admissible and consistent) heuristic function that computes the estimated distance of two nodes. The adjacency list is a map (NodeID -> map (NodeID -> Cost)) and describes the edges in the graph and their cost. The adjacency list is assumed to be symmetric, i.e.,adjacency[x][y] == adjacency[y][x].

On a high level, the algorithm works as follows:

Put the starting node into a priority queueboundary. This queue contains the set of not-yet-visited nodes that are connected to at least one already visited node by an edge
Ifboundary is empty, return the empty path
Take out the entryv fromboundary with the least cumulative cost
If this node is the target node, reconstruct the path and return
Add all neighbors of nodev toboundary that are not yet visited
Go to step 2

Do you have recommendations on how to improve the following code with regard to my above-mentioned goals? I'm specifically wondering whether theboundary.push part could be written more concise without afor loop. What other features of modern C++ did I miss that would improve this code? If you spot some issues with this code, feel free to mention them.

Header file (a_star.h):

#include <functional>#include <map>#include <vector>typedef size_t NodeID;typedef float Cost;typedef std::pair<const NodeID, Cost> Edge;typedef std::map<const NodeID, std::map<const NodeID, Cost>> AdjacencyList;typedef std::vector<NodeID> Path;typedef const std::function<Cost(NodeID, NodeID)> HeuristicFn;Path a_star(AdjacencyList& adjacency,            NodeID         start,            NodeID         target,            HeuristicFn&   heuristic);

Source filea_star.cpp:

#include "a_star.h"#include <memory>#include <numeric>#include <queue>#include <ranges>#include <set>struct PathNode {    NodeID node; // node    Cost total_cost; // cost of reaching node from starting node    Cost estimated_cost; // lower bound on the cost for any path from starting to target node through this node    std::shared_ptr<PathNode> previous; // previous record};bool operator>(const PathNode& left, const PathNode& right) {    return left.estimated_cost > right.estimated_cost;}Path backtrace(PathNode& last_record) {    PathNode current = last_record;    Path path {current.node};    while (current.previous != nullptr) {        current = *current.previous;        path.emplace_back(current.node);    }    std::reverse(path.begin(), path.end());    return path;}Path a_star(AdjacencyList& adjacency,            NodeID         start,            NodeID         target,            HeuristicFn&   heuristic) {    std::set<NodeID> visited;    std::priority_queue<PathNode, std::vector<PathNode>, std::greater<>> boundary;    boundary.push({start, 0, heuristic(start, target), nullptr});    visited.emplace(start);    auto was_not_visited_yet = [visited] (Edge& entry) {        return !visited.contains(entry.first);    };    for (; !boundary.empty(); boundary.pop()) {        auto current = boundary.top();        if (current.node == target) {            return backtrace(current);        }        visited.emplace(current.node);        auto edge_to_record = [current, heuristic, target] (Edge& edge) -> PathNode {            Cost total_cost = current.total_cost + edge.second;            Cost estimated_cost = total_cost + heuristic(current.node, target);            return {edge.first, total_cost, estimated_cost, std::make_shared<PathNode>(current)};        };        auto neighbor_records = std::ranges::views::filter(adjacency[current.node], was_not_visited_yet)                                | std::ranges::views::transform(edge_to_record);        for (const PathNode& neighbor_record : neighbor_records) {            boundary.push(neighbor_record);        }    }    return {}; // no path to target}```

Question 2

First thought: this would likely be more efficient with an adjacency matrix, implemented as astd::mdspan from C++23. Or astd::vector of sparse row data.

Question 3

Second thought:for (; !boundary.empty(); boundary.pop()) could be written aswhile (const auto current = boundary.pop()) or maybefor (const auto current : boundary).

Question 4

@Davislor Thanks for mentioningstd::mdspan. I'll look into it. Using an adjacency matrix could indeed speed up the algorithm.

Question 5

@Davislor Regardingwhile (const auto current = boundary.pop()): How does this work exactly? According to thedocs, the return value ofboundary.pop() isvoid? Regardingfor (const auto current : boundary): This looks good. I'll try it.

Question 6

Note that an undirected graph, as in your work, is a special case of directed graphs: you can simulate an undirected graph by creating for each undirected edge \$\{u,v\}\$ two directed arcs \$(u,v), (v,u)\$.

Question 7

Missing and redundant`const`

Make sure that all pointer and reference parameters that point to data that should not be modified are passed asconst. This includeslast_record,adjacency andedge in the lambda. Note that you cannot useoperator[] onadjacency anymore, instead use.at().

On the other hand, you usedconst in places where it is not necessary. For example, you don't have to explicitly make the first template parameter ofstd::mapconst, as it will do that for you, seestd::map::value_type.

Range algorithms vs. good old`for` and`if`

Functional style programming can be really nice in some cases, but here it actually does not provide any benefits, and I think it's just simpler to write:

for (auto& [neighbor, cost]: adjacency.at(current.node)) {    if (!visited.contains(neighbor))        boundary.push(edge_to_record({neighbor, cost}));}

Unnecessary use of`std::shared_ptr`

Astd::shared_ptr is a rather heavy-weight pointer. Also, every time you callstd::make_shared<current> you are making a heap-allocated copy ofcurrent, potentially multiple times for the same value ofcurrent. This is not ideal.

Instead, consider changingvisited so it is a set or map ofPathNodes. Sincestd::set,std::map and similar containers ensure the items they contain have stable pointers, you can then just store a raw pointer inPathNode and have it safely point to any node already invisited.

But do you need pointers at all? In the end you only care about theNodeIDs. So why not makePathNode::previous be aNodeID instead of a (smart) pointer?

Think about your data structures

There are some concerns about your use ofstd::set andstd::map. First of all, these containers have\$O(\log N)\$ complexity for adding and finding entries. If you don't need the order of the elements to be preserved, you can instead usestd::unordered_set andstd::unordered_map for faster access times. But sometimes you don't even need to look up specific elements. For example, given a node, you don't care about looking up a specific neighbor, you only want to iterate over all its neighbors. So you could have written:

typedef std::unordered_map<NodeId, std::vector<Edge>> AdjacencyList;

These generic containers are great if you don't know much aboutNodeId, or if they can have any value. But if you know thatNodeIds are unsigned numbers that are assigned sequentially starting from zero, and there are no gaps, then you can just useNodeId as an index into an array or vector. So:

typedef std::vector<std::vector<Edge>> AdjacencyList;

And this is the point where Davislor's comment that an adjacency matrix might be more efficient suddenly makes a lot more sense.

In this case, you could also replacestd::set<NodeId> visited with astd::vector<bool> visited, which only uses one bit per node in the graph, and only requires one memory allocation to ever be made, whereasstd::set will allocate memory for each individual item you store in it.

Having more compact datastructures reduces memory bandwidth and improves the efficiency of your cache. Having datastructures that have\$O(1)\$ operations instead of\$O(\log N)\$ ones will greatly speed up your algorithm for large graphs.

Question 8

Thank you for your valuable comments. I have a few questions: (1) You say, I cannot useoperator[] onadjacency anymore. What's the reason for this? I didn't found anydeprecation notice. Is it best practice to use.at() instead ofoperator[] or is this specific to my code? (2) According tocplusplus.com, the worst-case complexity ofunordered_map::emplace is $O(N)$, do you know why? Does this only apply if I have $N - 1$ hash collisions?

Question 9

@Green绿色 You can't useoperator[] after you makeadjacency const, becauseoperator[] isn't a const operation.operator[] inserts a new element when the index doesn't exist.

Question 10

@Green绿色 If the hash table used internally to index the elements of astd::unordered_map is full, it has to grow the hash table and reindex all elements. That is why it can cost \$O(N)\$ for a singleemplace(). However,amortized over many calls toemplace() it is a \$O(1)\$ operation.

Question 11

As I understand your code, a new node is pushed for every unvisited neighbour of the node that is visited.

A result of that is that the queue will contain, in many cases, duplicate nodes, or "almost duplicate" nodes with the same ID but a differentprevious and differenttotal_cost. These duplicates are bad. If theirestimated_cost is high, all they do is clog up the queue, but their estimated cost doesn't need to be high. The same part of the graph can be explored multiple times, even though only unvisited neighbours are pushed, because it would be pushed againbefore it has been visited.

There are some things you can do to avoid this. A simple trick is, when getting the top node out of the queue, skip it if it had been visited. That way some duplicates still clog up the queue, but at least they're not redundantly processed, and some duplicates are prevented by not processing useless nodes.

Another technique is to prevent duplicates from ever being created, but you need different data structures for that: a priority queue that can be efficiently indexed by node ID. You can make that with a binary heap that also maintains a map from node ID to index in the heap.

G. Sliepen 69.5k3 gold badges75 silver badges180 bronze badges · Accepted Answer · 2023-06-09 22:38:56Z

Missing and redundant`const`

Make sure that all pointer and reference parameters that point to data that should not be modified are passed asconst. This includeslast_record,adjacency andedge in the lambda. Note that you cannot useoperator[] onadjacency anymore, instead use.at().

On the other hand, you usedconst in places where it is not necessary. For example, you don't have to explicitly make the first template parameter ofstd::mapconst, as it will do that for you, seestd::map::value_type.

Range algorithms vs. good old`for` and`if`

Functional style programming can be really nice in some cases, but here it actually does not provide any benefits, and I think it's just simpler to write:

for (auto& [neighbor, cost]: adjacency.at(current.node)) {    if (!visited.contains(neighbor))        boundary.push(edge_to_record({neighbor, cost}));}

Unnecessary use of`std::shared_ptr`

Astd::shared_ptr is a rather heavy-weight pointer. Also, every time you callstd::make_shared<current> you are making a heap-allocated copy ofcurrent, potentially multiple times for the same value ofcurrent. This is not ideal.

Instead, consider changingvisited so it is a set or map ofPathNodes. Sincestd::set,std::map and similar containers ensure the items they contain have stable pointers, you can then just store a raw pointer inPathNode and have it safely point to any node already invisited.

But do you need pointers at all? In the end you only care about theNodeIDs. So why not makePathNode::previous be aNodeID instead of a (smart) pointer?

Think about your data structures

There are some concerns about your use ofstd::set andstd::map. First of all, these containers have\$O(\log N)\$ complexity for adding and finding entries. If you don't need the order of the elements to be preserved, you can instead usestd::unordered_set andstd::unordered_map for faster access times. But sometimes you don't even need to look up specific elements. For example, given a node, you don't care about looking up a specific neighbor, you only want to iterate over all its neighbors. So you could have written:

typedef std::unordered_map<NodeId, std::vector<Edge>> AdjacencyList;

These generic containers are great if you don't know much aboutNodeId, or if they can have any value. But if you know thatNodeIds are unsigned numbers that are assigned sequentially starting from zero, and there are no gaps, then you can just useNodeId as an index into an array or vector. So:

typedef std::vector<std::vector<Edge>> AdjacencyList;

And this is the point where Davislor's comment that an adjacency matrix might be more efficient suddenly makes a lot more sense.

In this case, you could also replacestd::set<NodeId> visited with astd::vector<bool> visited, which only uses one bit per node in the graph, and only requires one memory allocation to ever be made, whereasstd::set will allocate memory for each individual item you store in it.

Having more compact datastructures reduces memory bandwidth and improves the efficiency of your cache. Having datastructures that have\$O(1)\$ operations instead of\$O(\log N)\$ ones will greatly speed up your algorithm for large graphs.

Thank you for your valuable comments. I have a few questions: (1) You say, I cannot useoperator[] onadjacency anymore. What's the reason for this? I didn't found anydeprecation notice. Is it best practice to use.at() instead ofoperator[] or is this specific to my code? (2) According tocplusplus.com, the worst-case complexity ofunordered_map::emplace is $O(N)$, do you know why? Does this only apply if I have $N - 1$ hash collisions?
@Green绿色 You can't useoperator[] after you makeadjacency const, becauseoperator[] isn't a const operation.operator[] inserts a new element when the index doesn't exist.
@Green绿色 If the hash table used internally to index the elements of astd::unordered_map is full, it has to grow the hash table and reindex all elements. That is why it can cost \$O(N)\$ for a singleemplace(). However,amortized over many calls toemplace() it is a \$O(1)\$ operation.

Movatterモバイル変換

Stack Exchange Network

A* algorithm implementation in modern C++

2 Answers2

Missing and redundant`const`

Range algorithms vs. good old`for` and`if`

Unnecessary use of`std::shared_ptr`

Think about your data structures

You mustlog in to answer this question.

Related

Hot Network Questions

Subscribe to RSS

Movatterモバイル変換

A* algorithm implementation in modern C++

2 Answers2

Missing and redundantconst

Range algorithms vs. good oldfor andif

Unnecessary use ofstd::shared_ptr

Think about your data structures

You mustlog in to answer this question.

Related

Hot Network Questions

Missing and redundant`const`

Range algorithms vs. good old`for` and`if`

Unnecessary use of`std::shared_ptr`