Return to Question

The main conceptual changes from my previous attempt is that I have abstracted away the shortest paths algorithm using the Strategy pattern. In the main function I give two concrete examples using the Dijkstra and Bellman-Ford algorithm.

The main conceptual changes from my previous attempt is that I have abstracted away the shortest paths algorithm using the Strategy pattern. In the main function I give two concrete examples using the Dijkstra and Bellman-Ford algorithm.

I've been designing a dynamic graph to improve my understanding of C++11. The dynamic aspect means it could represent the hyperlink structure of internet, with node deletion corresponding to removing dead links. I'd be grateful for a review of coding style/design patterns/optimization.

template<class Label, class Edge>
class Dijkstra : public Graph<Label,Edge>::SPEngine {
private:
 // priority queue for Dijkstra
 Heap<typename Graph<Label,Edge>::CompareNode> Q;
public:
 void apply(Graph<Label,Edge>& g, const Label& start);
};
template<class Label, class Edge>
void Dijkstra<Label,Edge>::apply(Graph<Label,Edge>& g, const Label& start)
{
 // initialize distance estimates
 for (auto it = g.lookup_.begin(); it != g.lookup_.end(); ++it) it->second->d_ = std::numeric_limits<Edge>::max();
 typename Graph<Label,Edge>::Node* pstart = g.pointerOf(start); // maintain pointer for future use
 pstart->d_ = 0;
 // create a set to store processed nodes
 std::unordered_set<typename Graph<Label,Edge>::Node*> S;
 // insert initialized nodes into priority queue in correct order
 Q.insert(pstart);
 for (auto it = g.lookup_.begin(); it != g.lookup_.end(); ++it)
 {
 if (it->second.get() != pstart) Q.insert(it->second.get());
 }
 while (Q.heapSize()!=0)
 {
 typename Graph<Label,Edge>::Node* u = (typename Graph<Label,Edge>::Node*)Q.extract_min();
 S.insert(u);
 // for each neighbor v of u, perform relax(u,v)
 for (auto it : u->outgoing_)
 {
 g.relax(u,it.first);
 }
 }
}

I've been designing a dynamic graph to improve my understanding of C++11. The dynamic aspect means that it could represent the hyperlink structure of a chunk of the internet, with node deletion corresponding to removing dead links. I'd be grateful for a review of coding style/design patterns/optimization.

template<class Label, class Edge>
class Dijkstra : public Graph<Label,Edge>::SPEngine {
private:
 // priority queue for Dijkstra
 Heap<typename Graph<Label,Edge>::CompareNode> Q;
public:
 void apply(Graph<Label,Edge>& g, const Label& start);
};
template<class Label, class Edge>
void Dijkstra<Label,Edge>::apply(Graph<Label,Edge>& g, const Label& start)
{
 // initialize distance estimates
 for (auto it = g.lookup_.begin(); it != g.lookup_.end(); ++it) it->second->d_ = std::numeric_limits<Edge>::max();
 typename Graph<Label,Edge>::Node* pstart = g.pointerOf(start); // maintain pointer for future use
 pstart->d_ = 0;
 // create a set to store processed nodes
 std::unordered_set<typename Graph<Label,Edge>::Node*> S;
 // insert initialized nodes into priority queue in correct order
 Q.insert(pstart);
 for (auto it = g.lookup_.begin(); it != g.lookup_.end(); ++it)
 {
 if (it->second.get() != pstart) Q.insert(it->second.get());
 }
 while (Q.heapSize()!=0)
 {
 typename Graph<Label,Edge>::Node* u = static_cast<typename Graph<Label,Edge>::Node*>(Q.extract_min());
 S.insert(u);
 // for each neighbor v of u, perform relax(u,v)
 for (auto it : u->outgoing_)
 {
 g.relax(u,it.first);
 }
 }
}