Dijkstra的通用实现

Question

以下是Dijkstra的实现

作为此rags-to-riches版本的Dijkstra算法的面向对象方法

#include <set>
#include <vector>
#include <string>
#include <map>
#include <queue>
#include <algorithm>
#include <iterator>
#include <iostream>
/*

一个非常简单的图形对象：

这里的图类型只应该提供一个非常简单的图实现。关键是它提供了Dijkstra算法所需的最低要求。

*/
namespace ThorsAnvil
{
    template<typename N, typename IdType = N>
    class Graph
    {
            class Node;
            using NodeHolder    = typename std::set<Node>;
        public:
            using NodeId        = IdType;
            using NodeRef       = typename NodeHolder::iterator;
            using Edges         = std::vector<std::pair<NodeRef, int>>;
        private:
        class Node
        {
            N data;
            mutable Edges   outedge;
            public:
                Node(N const& data)
                    : data(data)
                {}
                void addEdge(NodeRef e, int cost) const
                {
                    outedge.emplace_back(e, cost);
                }
                NodeId const& id() const
                {
                    return data;
                }
                Edges const& getEdges() const
                {
                    return outedge;
                }
                friend bool operator<(Node const& lhs, Node const& rhs)
                {
                    return lhs.data < rhs.data;
                }
        };
        NodeHolder   nodes;
        public:
            NodeRef addNode(N const& data)
            {
                auto result = nodes.emplace(data);
                return result.first;
            }
            NodeRef getRef(N const& data)
            {
                return nodes.find(data);
            }
            void addEdge(NodeRef src, NodeRef dst, int cost)
            {
                if (src != nodes.end() && dst != nodes.end()) {
                    src->addEdge(dst, cost);
                }
            }
            Edges const& getEdges(N const& node) const
            {
                static Edges const empty;

                NodeRef    nodeInfo = nodes.find(node);
                if (nodeInfo == nodes.end()) {
                    return empty;
                }
                return nodeInfo->getEdges();
            }
    };
    /*

Dijkstra类

    */
    template<typename Graph>
    class Dijkstra
    {
        //  Graph: The graph type we will traverse
        //     Graph::NodeRef          Type that defines references to the nodes.
        //     Graph::NodeId           A type that uniquely identifies a node.
        //        nodeRef->id()        Gives a unique ID that identifies the node.
        //                             So we don't need to processes it more than once.
        //        nodeRef->getEdges()  returns a container with {NodeRef, Cost}
        using NodeRef = typename Graph::NodeRef;
        using NodeId  = typename Graph::NodeId;
        /*

QueInfo

        */
        // Its a tuple really:
        // It is used in a priority queue used by the route algorithm
        //     1:  The node we have reached.
        //     2:  The cost to get to this node.
        //     3:  An ordered list of nodes to get here with this cost.
        struct QueInfo: public std::tuple<NodeRef, int, std::vector<NodeRef>>
        {
            public:
                QueInfo(QueInfo const&) = default;
                QueInfo(NodeRef const& data, int cost, std::vector<NodeRef> const& route)
                    : std::tuple<NodeRef, int, std::vector<NodeRef>>(data, cost, route)
                {
                    // Add the current node to the end of the route
                    std::get<2>(*this).push_back(data);
                }
                // Allow QueInfo to be ordered (for the priority queue
                friend bool operator<(QueInfo const& lhs, QueInfo const& rhs)
                {
                    return std::get<1>(lhs) > std::get<1>(rhs);
                }
        };
        /*

Dijkstra (成员和构造函数)

        */
        Graph const&  graph;
        public:
            Dijkstra(Graph const& graph)
                : graph(graph)
            {}
            /*

Dijkstra算法实现.

            */
            std::vector<NodeRef> route(NodeRef const& src, NodeRef const& dst)
            {
                std::set<NodeId>              found;
                std::priority_queue<QueInfo>  frontier;

                frontier.emplace(src, 0, std::vector<NodeRef>());

                while(!frontier.empty()) {

                    QueInfo next    = frontier.top();
                    frontier.pop();

                    NodeRef const& current = std::get<0>(next);

                    if (found.find(current->id()) != found.end()) {
                        continue;
                    }
                    found.emplace(current->id());

                    std::vector<NodeRef> const& result = std::get<2>(next);
                    if (current == dst) {
                        return result;
                    }

                    for(auto const& loop: current->getEdges()) {
                        frontier.emplace(loop.first, std::get<1>(next) + loop.second, result);
                    }
                }
                return {};
            }
    };
}
/*

示例Main:

*/
template<typename T>
struct RefPrinter
{
    T const& data;
    RefPrinter(T const& data) : data(data) {}
    friend std::ostream& operator<<(std::ostream& str, RefPrinter const& value)
    {
        return str << value.data->id();
    }
};

int main()
{
    using Graph    = ThorsAnvil::Graph<std::string>;
    using Dijkstra = ThorsAnvil::Dijkstra<Graph>;

    Graph graph;
    for(auto const& it : {"a","b","c","d","e","f","g"}) {
        graph.addNode(it);
    }
    for(auto const& it : std::initializer_list<std::pair<std::string, std::string>>{
                 {"a","b"},{"b","c"},{"c","d"},
                 {"b","a"},{"c","b"},{"d","c"},
                 {"c","e"},{"e","f"},{"b","f"},
                 {"e","c"},{"f","e"},{"f","b"},
                 {"f","g"},{"a","g"},
                 {"g","f"},{"g","a"}
             }) {
        graph.addEdge(graph.getRef(it.first), graph.getRef(it.second), 1);
    }

    Dijkstra    dijkstra(graph);

    auto result = dijkstra.route(graph.getRef("a"), graph.getRef("e"));
    std::copy(std::begin(result), std::end(result),
              std::ostream_iterator<RefPrinter<Graph::NodeRef>>(std::cout, "\n"));
}

Answer 1

嗯，我喜欢偶尔的方法之间的空白行，这与这种风格不同。但至少这是一种一贯的风格，你知道该期待什么。请给我for和while后面的空位。在声明outedge、nodes & nodeInfo和addNode时，一个空格就足够了，addNode可以是一个返回表达式的一行，名称result并不能帮助读者。好吧，关于更有实质意义的评论。

我通常觉得data的标识符有点模糊，但它有其用途。getRef参数是数据，但是getEdges接受节点的相同用途？我想addNode & getRef应该把它命名为node。看起来，nodeInfo最好是简单地命名为nodeRef。

请拼写: QueueInfo

当然，frontier是一个很好的命名选择。

我更希望看到这样的评论：

    //     0:  The node we have reached.
    //     1:  The cost to get to this node.
    //     2:  An ordered list of nodes to get here with this cost.

因为这与get引用相匹配，所以我们不会命名这些引用。

实际上，当循环遍历current->getEdges()时，我想引入一个cost临时变量是值得的，因为loop.second本质上也是未命名的。它将帮助读者，编译器将优化它。

                std::vector<NodeRef> const& result = std::get<2>(next);

result显然是错误的标识符，它太模糊了。这应该是inEdges。loop应该被命名为edge。

    graph.addEdge(graph.getRef(it.first), graph.getRef(it.second), 1);

这将有助于看到第二次测试，其中一些边缘没有单位成本-额外的信用渲染与graphViz。我确实希望看到评估result路径的成本。

包括测试代码的荣誉。