I'm seeking a code review for the following C++ implementation of Dijkstra's algorithm. I'm trying emphasize code reusability and extensibility but performance is also potentially important.
Documentation
Heap.h
This class implements the priority queue for use in Dijkstra
method of Graph
class.
The insertion into the priority queue is performed lazily which is not a problem since the
Dijkstra
method inserts the initialized nodes in their priority order.The
Heap<Item>
template class makes some assumptions about the storedItem
API; namely that theItem
object possess a.key()
method. This implies that there is a coupling betweenHeap
andGraph
which is probably undesirable.The keys are stored internally to the
Item
class which makes it difficult to implement thedecrease_key
API. I have implemented a workaround which involves calling thebuild_min_heap
method from withinGraph<Label, Edge>::Dijkstra
each time a node's priority is modified. This achieves log(n) complexity but is sub-optimal compared todecrease_key
which requires an additionalint
argument locating theNode
within the heap. Unfortunately eachNode
object does not know its own position within the heap which makes this difficult to implement. Can the Observer pattern be used here or am I overcomplicating things?
Graph.h
The
Graph<Label, Edge>
template class contains an innerNode
class.Node
pointers are accessed via theirLabel
using thepointerOf
method which is implemented usingstd::map<Label,Node*>
Each
Node
object contains a list outgoing edges together with their weights. I have additionally stored a list of incoming edges in order to prevent dangling pointers (see~Node
destructor).
Headers
#include <iostream>
#include <map>
#include <vector>
#include <unordered_set>
#include <list>
Heap
template<class Item, class Key>
class Heap {
public:
// implements priority queue data ADT
void insert(Item* val);
Item* extract_min();
void build_min_heap() { for (int i = heapSize_/2 ; i >= 0 ; i--) min_heapify(i); }
int heapSize() const { return heapSize_; }
private:
void decrease_key(int i, Key newkey);
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; }
int heapSize_ = 0;
std::vector<Item*> myHeap_;
};
template<class Item, class Key>
void Heap<Item,Key>::decrease_key(int i, Key newkey)
{
if( newkey < myHeap_[i]->key() )
{
myHeap_[i]->key() = newkey;
while( i > 0 && myHeap_[parent(i)]->key() > myHeap_[i]->key() )
{
std::iter_swap( myHeap_.begin()+i,myHeap_.begin()+parent(i) );
i = parent(i);
}
}
}
template<class Item, class Key>
void Heap<Item,Key>::insert(Item* val)
{
myHeap_.push_back(val);
++heapSize_;
}
template<class Item, class Key>
void Heap<Item,Key>::min_heapify(int i)
{
int l = left(i);
int r = right(i);
int smallest;
if( l < heapSize_ && myHeap_[l]->key() < myHeap_[i]->key() ) { smallest = l; }
else { smallest = i; }
if( r < heapSize_ && myHeap_[r]->key() < myHeap_[smallest]->key() ) smallest = r;
if( smallest!=i )
{
// swap i with m
std::iter_swap( myHeap_.begin()+i,myHeap_.begin()+smallest );
min_heapify(smallest);
}
}
template<class Item, class Key>
Item* Heap<Item,Key>::extract_min()
{
Item* min = myHeap_[0];
std::iter_swap(myHeap_.begin(),myHeap_.begin() + heapSize_-1);
// run min_heapify on the decremented heap
--heapSize_;
min_heapify(0);
return min;
}
Graph
template<class Label, class Edge>
class Graph {
public:
// adds a node to the graph
void addNode(const Label& name);
// deletes a node from the graph
void deleteNode(const Label& name);
// adds a directed edge from name1 to name2
void addEdge(const Label& name1, const Label& name2, Edge w = 1);
void listNeighbors(const Label& name);
void Dijkstra(const Label& start);
private:
// forward declaration
class Node;
class CompareNode;
bool relax(Node* u, Node* v);
// returns a pointer to a node given its label
Node* pointerOf(const Label& name);
std::map<Label,Node*> nodeMap_;
// priority queue for Dijkstra
Heap<Node, Edge> Q;
};
template<class Label, class Edge> class
Graph<Label,Edge>::Node {
public:
Node(const Label& name) : label_(name), Pi_(nullptr), d_(0) {}
~Node();
void addOutgoing(Node* p, Edge w) { outgoing_.push_back( {p,w} ); }
void addIncoming(Node* p) { incoming_.push_back(p); }
void deleteOutgoing(Node* p);
// API for priority queue
Edge key() { return d_; }
const Label& label() const { return label_; }
// node identifier
Label label_;
// incoming and outgoing nodes
std::list< std::pair<Node*, Edge> > outgoing_;
std::list<Node*> incoming_;
// predecessor/distance data structure for Dijkstra
Node* Pi_;
Edge d_;
};
template<class Label, class Edge>
class Graph<Label,Edge>::CompareNode {
public:
CompareNode(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>
bool Graph<Label,Edge>::relax(Node* u, Node* v)
{
// find the weight of the node pointing from u to v
typename std::list< std::pair<Node*, Edge> >::iterator it
= std::find_if( u->outgoing_.begin(),u->outgoing_.end(),CompareNode(v) );
if( it != u->outgoing_.end() ) // if there is an edge pointing from u to v
{
Edge w = it->second;
// check relaxation condition
if(v->d_ > u->d_ + w)
{
v->d_ = u->d_ + w;
v->Pi_ = u;
return true;
}
return false;
}
return false;
}
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->deleteOutgoing(this);
std::cout << "Node '" << label_ << "' destroyed\n";
}
template<class Label, class Edge>
void Graph<Label,Edge>::addNode(const Label& name)
{
Node* n = new Node(name);
nodeMap_.insert( {name,n} ); // does nothing if name is already there
}
template<class Label, class Edge>
void Graph<Label,Edge>::deleteNode(const Label& name)
{
typename std::map<Label,Node*>::iterator it = nodeMap_.find(name);
if( it != nodeMap_.end() ) delete it->second;
}
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 name1 and name2 exist
{
n1->addOutgoing(n2,w);
n2->addIncoming(n1);
}
}
template<class Label, class Edge>
void Graph<Label,Edge>::listNeighbors(const Label& name)
{
Node* n = pointerOf(name);
for( auto it : n->outgoing_ ) std::cout << "(" << it.first->label_ << "," << it.second << ")" << " ";
}
template<class Label, class Edge>
void Graph<Label,Edge>::Node::deleteOutgoing(Node* n)
{
typename std::list< std::pair<Node*, Edge> >::iterator it
= std::find_if(outgoing_.begin(),outgoing_.end(),CompareNode(n));
if( it != outgoing_.end() ) outgoing_.erase(it);
}
template<class Label, class Edge>
typename Graph<Label,Edge>::Node* Graph<Label,Edge>::pointerOf(const Label& name)
{
typename std::map<Label,Node*>::iterator it = nodeMap_.find(name);
if( it != nodeMap_.end() ) { return it->second; }
else { return nullptr; }
}
template<class Label, class Edge>
void Graph<Label,Edge>::Dijkstra(const Label& start)
{
for( auto it : Graph::nodeMap_ ) it.second->d_ = std::numeric_limits<Edge>::max();
// initialize the distance estimate of the starting node to zero
Node* pstart = pointerOf(start); // maintain pointer for future use
pstart->d_ = 0;
// create a set to store processed nodes
std::unordered_set<Node*> S;
// insert nodes into priority queue in correct order
Q.insert(pstart);
for( auto it : nodeMap_ )
{
if(it.second != pstart ) Q.insert(it.second);
}
while( Q.heapSize()!=0 ) //
{
Node* u = Q.extract_min();
S.insert( u );
// for each neighbor v of u, perform relax(u,v)
for( auto it : u->outgoing_ )
{
if( relax( u, it.first ) ) Q.build_min_heap();
}
}
// print out the shortest path weights
for( auto it : S ) std::cout << "(" << it->label_ << "," << it->d_ << ")" << " ";
}
Main
int main()
{
std::vector<std::string> nodes = {"a","b","c","d","e","f","g"};
std::vector< std::pair<std::string,std::string> > edges =
{
{"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"}
};
std::cout << "\n";
Graph<std::string,double> myGraph;
for(auto it : nodes) myGraph.addNode(it);
for(auto it : edges) myGraph.addEdge(it.first,it.second);
myGraph.Dijkstra("a");
}
Output
(e,3) (c,2) (g,1) (d,3) (f,2) (b,1) (a,0)
addEdge
method takes an explicit argument for the edge costw
with default value 1. \$\endgroup\$