路径查找的实现图

Question

我需要一个用于多种路径查找算法的图表，所以我想问一下我的新图实现是否正常。在相关领域(图形、路径查找、算法)工作的开发人员会做类似的事情吗？

节点类：

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

这是我的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;
    }
}

以下是连接：

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

不需要delete或default默认构造函数

如果将用户声明的构造函数添加到类中，编译器将不会生成隐式默认构造函数。因此，没有必要= delete它。

相反，如果您没有添加任何用户声明的构造函数，它将生成一个隐式默认构造函数，因此不需要使用= default显式添加构造函数。

考虑使用std::unordered_map

图算法不关心节点的顺序，所以考虑使用std::unordered_map而不是std::map来保存节点及其邻接列表。与用于std::unordered_map的O(\log N)相比，在std::map中查找节点的是O(1)。您仍然可以使用begin()和end()迭代它。

通过引用

返回邻接列表

Graph::operator[]()按值返回std::vector<Connection>。这会导致每次调用时都要复制一个副本，这可能非常昂贵，特别是在大而密集的图形中。通过(const)引用返回它，就像data.operator[]()所做的那样。

使用与STL容器

相同的语义。

对于成员函数，您已经使用了与STL容器相同的名称，如begin()和size()。这很好，这意味着如果某人已经知道如何使用STL容器，那么使用您的Graph类就更容易了。但也要确保这些函数的行为与STL的行为相匹配。特别是，operator[]不会抛出异常，所以您的也不应该抛出异常。STL容器提供了成员函数at()，如果找不到您提供的键，它就会抛出。如果您需要这个功能，可以考虑向您自己的类中添加一个at()成员函数。

如果您不喜欢operator[]可能会插入一个尚未存在的节点，请考虑不要将该成员函数添加到Graph中。

使nodeContainsConnection()成为Graph

的成员函数

奇怪的是，nodeContainsConnection()不是成员函数，不像addConnection()这样的其他函数。我还会将它重命名为containsConnection()。

简化了addConnection()

利用这样一个事实:如果元素还不存在，operator[]将访问元素或插入元素。如果它插入一个，则默认构造一个std::vector<Connection>，因此您可以立即在其上使用push_back()，甚至更好的是使用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

请考虑本节：

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

我会在那里省略[[nodiscard]]，因为忽略返回值并没有坏处。这个属性对于像sscanf()这样的函数更有用，因为为了知道副作用的有效性，必须使用返回类型。这里，只是杂乱无章。

const也是没有意义的，因为我们返回一个值。我们所做的只是让它更难作为迭代器使用。重要的const是使data常量的一个，这意味着data.begin()和data.end()返回const_iterator值。我会更进一步，通过在那里调用data.cbegin()和data.cend()来使这一点变得更加明显：

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