Implementing graph for pathfinding

Question

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); }

        [[nodiscard]] std::vector<Connection> operator[](Node node) const;
    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;
    }
}

Answer 1

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);
}

Answer 2

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(); }