Dynamic graph in C++11 with shortest path algorithm

Question

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.

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 have also implemented the Observer-Observable pattern with the Nodes playing the role of observables. The motivation for using the observer pattern was to decouple the Node class from the mutable Heap class which is used in the Dijkstra algorithm.

Headers

#include <iostream>
#include <unordered_map>
#include <vector>
#include <unordered_set>
#include <list>

Observer

class Observable;
class Observer {
public:
 virtual ~Observer() {}
 virtual void update(Observable* = nullptr)=0;
 void registerWith(Observable* observable);
};
class Observable {
public:
 Observable() : observer_(nullptr) {}
 void notifyObserver();
 void registerObserver(Observer* observer);
private:
 Observer* observer_;
};
inline void Observer::registerWith(Observable* observable)
{
 if (observable) observable->registerObserver(this);
}
inline void Observable::notifyObserver()
{
 if(observer_) observer_->update(this);
}
inline void Observable::registerObserver(Observer* observer)
{
 observer_=observer;
}

Heap

template<class Compare>
class Heap : Observer {
public:
 // implements priority queue data ADT
 void insert(Observable* val);
 Observable* extract_min();
 void build_min_heap() { for (int i = arr_.size()/2 ; i >= 0 ; --i) min_heapify(i); }
 int heapSize() const { return arr_.size(); }
 void print() const;
 void update(Observable* p);
private:
 void indexSwap(Observable* a, Observable* b);
 void min_heapify(int i);
 int parent(int i) { return i/2; }
 int left(int i) { return 2*i; }
 int right(int i) { return 2*i+1; }
 // underlying array
 std::vector<Observable*> arr_;
 // keeps track of locations in array
 std::unordered_map<Observable*,unsigned int> lookup_;
};
template<class Compare>
void Heap<Compare>::insert(Observable* val)
{
 unsigned int n = arr_.size();
 lookup_[val] = n;
 arr_.push_back(val);
 update(val);
 registerWith(val);
}
template<class Compare>
void Heap<Compare>::indexSwap(Observable* a, Observable* b)
{
 unsigned int temp = lookup_[a];
 lookup_[a] = lookup_[b];
 lookup_[b] = temp;
}
template<class Compare>
void Heap<Compare>::update(Observable* p)
{
 int i = lookup_[p];
 while ( i > 0 && !Compare()(arr_[parent(i)],arr_[i]) )
 {
 indexSwap( arr_[i], arr_[parent(i)] );
 std::iter_swap( arr_.begin()+i, arr_.begin()+parent(i) );
 i = parent(i);
 }
}
template<class Compare>
void Heap<Compare>::min_heapify(int i)
{
 int l = left(i);
 int r = right(i);
 int smallest;
 if ( l < arr_.size() && Compare()(arr_[l],arr_[i]) ) { smallest = l; }
 else { smallest = i; }
 if ( r < arr_.size() && Compare()(arr_[r],arr_[smallest]) ) smallest = r;
 if ( smallest!=i )
 {
 // swap position i with smallest
 indexSwap( arr_[i], arr_[smallest] );
 std::iter_swap( arr_.begin()+i, arr_.begin()+smallest );
 min_heapify(smallest);
 }
}
template<class Compare>
Observable* Heap<Compare>::extract_min()
{
 Observable* min = arr_[0];
 indexSwap( arr_[0], arr_[arr_.size()-1] );
 std::iter_swap(arr_.begin(),arr_.begin() + arr_.size()-1);
 // run min_heapify on the decremented heap
 arr_.pop_back();
 min_heapify(0);
 return min;
}

Graph

template<class Label, class Edge>
class Graph {
public:
 class SPEngine;
 Graph(const std::shared_ptr<SPEngine>& engine = std::shared_ptr<SPEngine>()) : engine_(engine) {}
 void setSPEngine(const std::shared_ptr<SPEngine>& engine) { engine_ = engine; }
 void addNode(const Label& name);
 void deleteNode(const Label& name);
 // adds a directed edge pointing from name1 to name2
 void addEdge(const Label& name1, const Label& name2, Edge w = 1);
 void printNeighbors(const Label& name);
 void shortestPaths(const Label& start);
 struct CompareNode;
 struct Node;
 void relax(Node* u, Node* v);
 // returns a pointer to a node given its label
 Node* pointerOf(const Label& name);
 std::unordered_map<Label,std::unique_ptr<Node>> lookup_;
private:
 struct isSame;
 std::shared_ptr<SPEngine> engine_;
};
template<class Label, class Edge> class
Graph<Label,Edge>::SPEngine {
public:
 virtual ~SPEngine() {}
 virtual void apply(Graph<Label,Edge>& g, const Label& start) = 0;
};
template<class Label, class Edge>
void Graph<Label,Edge>::shortestPaths(const Label& start) {
 engine_->apply(*this,start);
 // print out the shortest path weights
 for (auto it = lookup_.begin(); it != lookup_.end(); ++it) {
 std::cout << "(" << it->second->label_ << "," << it->second->d_ << ")" << " ";
 }
 std::cout << "\n";
}
template<class Label, class Edge> struct
Graph<Label,Edge>::Node : public Observable {
 Node(const Label& name) : label_(name), Pi_(nullptr), d_(0) {}
 ~Node();
 // node identifier
 Label label_;
 // incoming and outgoing nodes
 std::list< std::pair<Node*, Edge> > outgoing_;
 std::list<Node*> incoming_; // to handle node deletions
 void addOutgoing(Node* p, Edge w) { outgoing_.push_back( {p,w} ); }
 void addIncoming(Node* p) { incoming_.push_back(p); }
 void removeOutgoing(Node* p);
 void removeIncoming(Node* p);
 // predecessor/distance data structure for shortest paths method
 Node* Pi_;
 Edge d_;
};
template<class Label, class Edge>
struct Graph<Label,Edge>::isSame {
 isSame(Node* n) : n_(n) {}
 bool operator()(const std::pair<Node*,Edge>& elem) const { return n_ == elem.first; }
private:
 Node* n_;
};
template<class Label, class Edge>
struct Graph<Label,Edge>::CompareNode {
 bool operator()(Observable* u, Observable* v) const {
 return ((Node*)u)->d_ < ((Node*)v)->d_;
 }
};
template<class Label, class Edge>
void Graph<Label,Edge>::relax(Node* u, Node* v)
{
 // find the weight of the edge pointing from u to v
 typename std::list< std::pair<Node*, Edge> >::iterator it
 = std::find_if( u->outgoing_.begin(),u->outgoing_.end(),isSame(v) );
 if ( it != u->outgoing_.end() ) // if there is an edge pointing from u to v
 {
 Edge w = it->second;
 // check relaxation condition
 if (u->d_ == std::numeric_limits<Edge>::max() && w > 0) return; // corrects mathematical bug
 if (v->d_ > u->d_ + w)
 {
 v->d_ = u->d_ + w;
 v->Pi_ = u;
 v->notifyObserver(); // v was modified
 return; // (u,v) was relaxed
 }
 return; // (u,v) was not relaxed
 }
 return; // (u,v) does not exist
}
template<class Label, class Edge>
Graph<Label,Edge>::Node::~Node()
{
 // for each incoming node n, remove 'this' pointer from n's list of outgoing
 for (auto it : incoming_) {
 it->removeOutgoing(this);
 }
 for (auto it : outgoing_) {
 it.first->removeIncoming(this);
 }
 std::cout << "Node " << this->label_ << " destroyed.\n";
}
template<class Label, class Edge>
void Graph<Label,Edge>::addNode(const Label& name)
{
 try {
 if (pointerOf(name)) throw 0;
 lookup_.emplace(name,std::unique_ptr<Node>(new Node(name)));
 } catch(...) {
 std::cout << "EXCEPTION: Graph already contains node with same label.\n";
 }
}
template<class Label, class Edge>
void Graph<Label,Edge>::deleteNode(const Label& name)
{
 try {
 Node* p = pointerOf(name);
 if (!p) throw 0; // throw if it's not there
 lookup_.erase(name);
 } catch(...) {
 std::cout << "EXCEPTION: Graph does not contain node with that label.\n";
 }
}
template<class Label, class Edge>
void Graph<Label,Edge>::addEdge(const Label& name1,const Label& name2, Edge w)
{
 Node* n1 = pointerOf(name1);
 Node* n2 = pointerOf(name2);
 if (n1 && n2) { // if both name1 and name2 exist
 n1->addOutgoing(n2,w);
 n2->addIncoming(n1);
 }
}
template<class Label, class Edge>
void Graph<Label,Edge>::printNeighbors(const Label& name)
{
 try {
 Node* n = pointerOf(name);
 if (!n) throw 0;
 for (auto it : n->outgoing_) std::cout << "(" << it.first->label_ << "," << it.second << ")" << " ";
 std::cout << "\n";
 } catch(...) {
 std::cout << "EXCEPTION: Graph does not contain node with that label.\n";
 }
}
template<class Label, class Edge>
void Graph<Label,Edge>::Node::removeOutgoing(Node* n)
{
 typename std::list< std::pair<Node*, Edge> >::iterator it
 = std::find_if(outgoing_.begin(),outgoing_.end(),isSame(n));
 try {
 if ( it == outgoing_.end() ) throw 0;
 outgoing_.erase(it);
 std::cout << "Removed " << it->first->label_ << " from " << this->label_ << "'s" << " outgoing list.\n";
 } catch(...) {
 std::cout << "Failed to remove " << n->label_ << " from " << this->label_ << "'s" << " outgoing list.\n";
 }
}
template<class Label, class Edge>
void Graph<Label,Edge>::Node::removeIncoming(Node* n)
{
 typename std::list<Node*>::iterator it
 = std::find(incoming_.begin(),incoming_.end(),n);
 try {
 if ( it == incoming_.end() ) throw 0;
 incoming_.erase(it);
 std::cout << "Removed " << (*it)->label_ << " from " << this->label_ << "'s" << " incoming list.\n";
 } catch(...) {
 std::cout << "Failed to remove " << n->label_ << " from " << this->label_ << "'s" << " incoming list.\n";
 }
}
template<class Label, class Edge>
typename Graph<Label,Edge>::Node* Graph<Label,Edge>::pointerOf(const Label& name)
{
 typename std::unordered_map<Label,std::unique_ptr<Node>>::iterator it = lookup_.find(name);
 if ( it != lookup_.end() ) {
 return it->second.get();
 }
 else {
 return nullptr;
 }
}

Dijkstra

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

Bellman_Ford

template<class Label, class Edge>
class Bellman_Ford : public Graph<Label,Edge>::SPEngine {
public:
 void apply(Graph<Label,Edge>& g, const Label& start);
};
template<class Label, class Edge>
void Bellman_Ford<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);
 pstart->d_ = 0;
 for (int i = 1; i <= g.lookup_.size()-1; ++i) {
 for (auto it1 = g.lookup_.begin(); it1 != g.lookup_.end(); ++it1) {
 typename Graph<Label,Edge>::Node* u = it1->second.get();
 for (auto it : u->outgoing_) {
 g.relax(u,it.first);
 }
 }
 }
}

Main

int main() {
 std::vector<std::string> nodes = {"a","b","c","d","e","f","g","h","i","j"};
 std::string v = nodes.front();
 std::vector< std::pair<std::string,std::string> > edges =
 {
 {"a","b"},{"b","c"},{"c","d"},
 {"c","e"},{"e","f"},{"b","f"},
 {"f","g"},{"g","a"},
 {"h","i"},{"i","j"},{"j","d"},
 {"f","h"},{"j","f"},{"f","d"}
 };
 Graph<std::string,int> myGraph;
 for (auto it : nodes) myGraph.addNode(it);
 for (auto it : edges) myGraph.addEdge(it.first,it.second);
 std::shared_ptr<Dijkstra<std::string,int>> dijkstra(new Dijkstra<std::string,int>);
 std::shared_ptr<Bellman_Ford<std::string,int>> BF(new Bellman_Ford<std::string,int>);
 myGraph.setSPEngine(dijkstra);
 std::cout << "Performing Dijkstra starting at vertex " << v << ":\n";
 myGraph.shortestPaths(v);
 myGraph.setSPEngine(BF);
 std::cout << "Performing Bellman_Ford starting at vertex " << v << ":\n";
 myGraph.shortestPaths(v);
}

Output

Performing Dijkstra starting at vertex a:
(h,3) (g,3) (f,2) (c,2) (e,3) (j,5) (d,3) (b,1) (i,4) (a,0) 
Performing Bellman_Ford starting at vertex a:
(h,3) (g,3) (f,2) (c,2) (e,3) (j,5) (d,3) (b,1) (i,4) (a,0) 
Removed h from f's outgoing list.
Removed h from i's incoming list.
Node h destroyed.
Removed g from f's outgoing list.
Removed g from a's incoming list.
Node g destroyed.
Removed f from e's outgoing list.
Removed f from b's outgoing list.
Removed f from j's outgoing list.
Removed f from d's incoming list.
Node f destroyed.
Removed c from b's outgoing list.
Removed c from d's incoming list.
Removed c from e's incoming list.
Node c destroyed.
Node e destroyed.
Removed j from i's outgoing list.
Removed j from d's incoming list.
Node j destroyed.
Node d destroyed.
Removed b from a's outgoing list.
Node b destroyed.
Node i destroyed.
Node a destroyed.