# Implementing graph for pathfinding

I need a graph for multiple pathfinding algorithms,so I wanted to ask whether my new graph implementation is ok. Would someone who works as a developer in related fields(Graphs, Pathfinding, Algorithms) do things similarly.

Node class:


#include "Coordinates.hpp"
#include <stdint.h>

namespace Pathfinding::Datastructures
{
struct Node
{
Node() = delete;
constexpr explicit Node(uint32_t i_ ) : id(i_) {};
uint32_t id;
};

[[nodiscard]] bool operator<(const Node & lhs, const Node & rhs);
[[nodiscard]] bool operator==(const Node & lhs, const Node & rhs);
}



Here is my graph.hpp:

#include <map>
#include <vector>

#include "Node.hpp"
#include "Connection.hpp"

namespace Pathfinding::Datastructures
{
class Graph
{
public:
Graph() = default;
void addConnection(Node start, Node goal, double weight);

[[nodiscard]] auto begin() { return data.begin(); }
[[nodiscard]] auto end() { return data.end(); }

[[nodiscard]] const auto begin() const { return data.begin(); }
[[nodiscard]] const auto end() const { return data.end(); }

[[nodiscard]] std::size_t size() const { return data.size(); }

[[nodiscard]] bool contains(Node node) const { return data.contains(node); }

protected:
std::map<Node, std::vector<Connection>> data;
};
}


Graph.cpp:

#include "Graph.hpp"

#include <vector>
#include <exception>

#include "Connection.hpp"
#include "Node.hpp"

#include <iostream>

namespace Pathfinding::Datastructures
{
namespace
{
[[nodiscard]] bool nodeContainsConnection(const Graph & graph,
const Node & start, const Node & end)
{
for(const auto neighbor : graph[start])
{
if(neighbor.node == end)
{
return true;
}
}
return false;
}
}

void Graph::addConnection(Node start, Node goal, double weight)
{
if(data.contains(start))
{
if(!nodeContainsConnection(*this, start, goal))
{
data[start].push_back(Connection(goal, weight));
data[goal].push_back(Connection(start, weight));
}
}
else
{
data[start] = {Connection(goal, weight)};
data[goal] = {Connection(start, weight)};
}
}

std::vector<Connection> Graph::operator[](Node node) const
{
const auto it = data.find(node);
if(it == data.end())
{
throw std::exception("Node not present in graph");
}
return it->second;
}
}


Here is connection:


namespace Pathfinding::Datastructures
{
struct Connection
{
Connection() = delete;
Connection(Node node_, double weight_) : node(node_), weight(weight_) {}
Node node;
double weight;
};

[[nodiscard]] bool operator==(const Connection & lhs, const Connection & rhs);
}


Connection.cpp:

#include "Connection.hpp"

namespace Pathfinding::Datastructures
{
bool operator==(const Connection & lhs, const Connection & rhs)
{
return lhs.weight == rhs.weight && lhs.node == rhs.node;
}
}

• It might be better to see how all this is used. Jan 15 at 2:24

# No need to delete or default the default constructors

If you add a user-declared constructor to a class, the compiler will not generate an implicit default constructor. So there is no need to = delete it.

Conversely, if you didn't add any user-declared constructors, it will generate an implicit default constructor, so there is no need to explicitly add one using = default.

# Consider using a std::unordered_map

Graph algorithms don't care about the order of nodes, so consider using a std::unordered_map instead of a std::map to hold the nodes and their adjacency lists. Looking up nodes in a std::unordered_map is $$\O(1)\$$, compared to $$\O(\log N)\$$ for std::map. You can still iterate over it using begin() and end().

# Return the adjacency list by reference

Graph::operator[]() returns a std::vector<Connection> by value. This causes a copy to be made every time it is called, which can be expensive, especially in large, dense graphs. Return it by (const) reference, just like data.operator[]() does.

# Use the same semantics as the STL containers

You already use the same names for member functions as STL containers, like begin() and size(). That's great, it means it is easier for someone to use your Graph class if they already know how to use STL containers. But also make sure the behavior of these functions matches that of the STL. In particular, operator[] does not throw exceptions, so yours should not either. STL containers provide the member function at() that does throw if the key you provided is not found. Consider adding an at() member function to your own class if you want this functionality.

If you don't like that operator[] might insert a node that didn't exist yet, consider not adding that member function to Graph.

# Make nodeContainsConnection() a member function of Graph

It is strange that nodeContainsConnection() is not a member function, unlike other functions like addConnection(). I would also rename it to containsConnection().

# Simplify addConnection()

Make use of the fact that operator[] will access an element or insert it if it didn't exist yet. If it inserts one, a std::vector<Connection> will be default constructed, so you can immediately push_back() on it, or even better, use emplace_back():

void Graph::addConnection(Node start, Node goal, double weight)
{
if (containsConnection(start, goal))
return;

data[start].emplace_back(goal, weight);
data[goal].emplace_back(start, weight);
}

• Thanks for the answer. I don't think I can simplify addConnection() that much, because I am making sure you can't add another edge to the same two nodes. Thats why I check whether the connection to this node is already present. Thats is also why nodeContainsConnection() is "static", I only need it in this part of code. If I need it somewhere else I will add it to the header. About the auto keyword, should I use it all the time as return type, even when returning stuff like bool or int?
– a a
Jan 15 at 23:35
• I think I should use a std::set to prevent multiple connections to the same node, will add comparison operator which only compares nodes.
– a a
Jan 15 at 23:38
• Ah, I forgot to add the check if the graph already contained the connection. Indeed, using std::set (or probably better, std::unordered_set) could help avoid that problem. You can even use it when returing a bool or int, although not everyone likes that. Sometimes having an explicit return type makes it more clear what the function is going to do. Other times the function name alone is already enough to tell you what is going to be returned (like begin() returning an iterator). Jan 15 at 23:40
• Is "If you [had] used auto return type deduction for operator[], you would automatically have returned a reference" really true? I think you need to write auto& or perhaps decltype(auto) for that. Jan 16 at 8:47
• @TobySpeight You're right. I was just thinking that all these functions are basically pass-through to the underlying data container, so why not do auto foo() { return data.foo(); } for everything, but of course that is generalizing too much and forgetting the fact that auto never deduces references. Jan 16 at 11:56

Consider this section:

    [[nodiscard]] const auto begin() const { return data.begin(); }
[[nodiscard]] const auto end() const { return data.end(); }


I would leave out the [[nodiscard]] there, as it does no harm to ignore the return value. That attribute is more useful for functions like sscanf() where the return type must be used in order to know the validity of the side-effects. Here, it's just clutter.

The const is also pointless, since we return a value. All we're doing is making it harder to use as an iterator. The important const is the one that makes data constant, meaning that data.begin() and data.end() return const_iterator values. I'd go a little further and make that more obvious by calling data.cbegin() and data.cend() there:

    auto begin() const { return data.cbegin(); }
auto end() const { return data.cend(); }