A generic implementation of Dijkstra

Question

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

• glampert: Is this meant to be a rags-to-riches of this question?
• Loki Astari: @glampert: Not originally (I had no idea about this). But I have polished it a bit more and added the tag.
• MikeMB: You found a bug in VS2015 (the loop in main) - I'll have to see, if there is already a bug report for it.

Answer 1

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.