Return to Question

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

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

 */
 std::vector<NodeRef> route(NodeRef const& src, NodeRef const& dst)
 {
 using PriorityQueue = std::priority_queue<QueInfo>;
  std::set<NodeId> found;
 PriorityQueue  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 {};
 }
 };
}
/*

*/
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>;
 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);
 }
 ThorsAnvil::Dijkstra<Graph> 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"));
}

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

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

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

##A very simple Graph object:

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

QueInfo structure:

 */
 // Its a tuple really:
 // 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.
 template<typename T>
 struct QueInfo: public std::tuple<T, int, std::vector<T>>
 {
 public:
 QueInfo(QueInfo const&) = default;
 QueInfo(T const& data, int cost, std::vector<T> const& result)
 : std::tuple<T, int, std::vector<T>>(data, cost, result)
 {
 std::get<2>(*this).push_back(data);
 }
 };
 /*

A cost for ordering the priority queue of QueInfo objects:

 */
 template<typename T>
 struct Cost
 {
 bool operator()(QueInfo<T> const& lhs, QueInfo<T> const& rhs) const
 {
 return std::get<1>(lhs) > std::get<1>(rhs);
 }
 };
 /*

##The Algorithm:

 */
 // Inputs:
 // src: start node in the graph object.
 //  dst: end node in the graph object.
 // graph: The graph we are traversing.
 // G::NodeRef Type that defines references to the nodes.
 //  G::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}
 template<typename G>
 std::vector<typename G::NodeRef> dijkstra(typename G::NodeRef const& src, typename G::NodeRef const& dst, G const& graph)
 {
  using NodeId = typename G::NodeId;
 using NodeRef  = typename G::NodeRef;
 using PriorityQueue = std::priority_queue<QueInfo<NodeRef>, std::vector<QueInfo<NodeRef>>, Cost<NodeRef>>;
 std::set<NodeId> found;
 PriorityQueue frontier;
 frontier.emplace(src, 0, std::vector<NodeRef>());
 while(!frontier.empty()) {
 QueInfo<NodeRef> 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 {};
 }
}
/*

*/
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>;
 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);
 }
 auto result = dijkstra(graph.getRef("a"), graph.getRef("g"), graph);
 std::copy(std::begin(result), std::end(result),
 std::ostream_iterator<RefPrinter<Graph::NodeRef>>(std::cout, "\n"));
}

##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)
 {
 using PriorityQueue = std::priority_queue<QueInfo>;

 std::set<NodeId> found;
 PriorityQueue 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 {};
 }
 };
}
/*

*/
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>;
 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);
 }
 ThorsAnvil::Dijkstra<Graph> 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"));
}