7
\$\begingroup\$

Here is an implementation of Dijkstra

As an rags-to-riches version of this Object oriented approach to Dijkstra's algorithm

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

A very simple Graph object:

The graph type here is only supposed to provide a very simplistic implementation of a graph. The point is that it provides the minimum requirements that are needed by Dijkstra algorithm.

*/
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 class

    */
    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 (Members and constructor)

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

Dijkstra algorithm implementation.

            */
            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 {};
            }
    };
}
/*

An Example 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"));
}
\$\endgroup\$
  • \$\begingroup\$ Is this meant to be a rags-to-riches of this question? \$\endgroup\$ – glampert Jan 6 '16 at 2:38
  • \$\begingroup\$ @glampert: Not originally (I had no idea about this). But I have polished it a bit more and added the tag. \$\endgroup\$ – Martin York Jan 6 '16 at 6:55
  • \$\begingroup\$ You found a bug in VS2015 (the loop in main) - I'll have to see, if there is already a bug report for it. \$\endgroup\$ – MikeMB Jan 10 '16 at 19:41
1
\$\begingroup\$

Well, I'm fond of the occasional blank line between methods, which differs from this style. But at least it's a consistent style, you know what to expect. A space after for and while please. A single space would suffice when declaring outedge, nodes & nodeInfo, and addNode could be a one-liner that returns an expression, the name result doesn't help the reader. Ok, on to more substantive remarks.

I usually find an identifier of data a bit vague, but it has its uses. The getRef parameter is data, yet getEdges accepts node for the same use? I suspect addNode & getRef should name it node. It seems nodeInfo would be better named simply nodeRef.

Please spell it: QueueInfo

Certainly frontier is a good naming choice.

I would prefer to see this comment:

    //     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.

as that matches the get references, and we're not naming such references.

Actually, when looping over current->getEdges(), I guess it would be worth introducing a cost temp variable, since loop.second also is essentially unnamed. It will help the reader, and the compiler will optimize it away.

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

result is clearly the wrong identifier, it is far too vague. This should be inEdges. loop should be named edge.

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

It would be helpful to see a 2nd test where some edges don't have unit cost - extra credit for rendering with graphViz. I did hope to see the cost of the result path evaluated.

Kudos for including test code.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.