Object oriented approach to Dijkstra's algorithm

Question

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 stored Item API; namely that the Item object possess a .key() method. This implies that there is a coupling between Heap and Graph which is probably undesirable.

• The keys are stored internally to the Item class which makes it difficult to implement the decrease_key API. I have implemented a workaround which involves calling the build_min_heap method from within Graph<Label, Edge>::Dijkstra each time a node's priority is modified. This achieves log(n) complexity but is sub-optimal compared to decrease_key which requires an additional int argument locating the Node within the heap. Unfortunately each Node 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 inner Node class. Node pointers are accessed via their Label using the pointerOf method which is implemented using std::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)

Answer 1

General Comments

1. You don't do memory management correctly anywhere
2. There is already heap functionality in the standard library.
   There is also a priority_queue that is based on this heap functionality.
3. Dijkstra usually has a start and an end (not just a start).
4. Is Dijkstra() really a method on the graph?
   I would have made this a standalone function.
5. Your vertical spacing is very dense it makes it hard to read.

Memory management is your big problem in this code. You pass around pointers. You should never do this especially across interface boundaries (its OK inside a class if you are careful. But across an interface boundary they provide no concept of ownership semantics. Pass references or smart pointers as appropriate).

Small side note:

template<class Item, class Key>

It is very old school to use class here in the template (though there is nothing wrong with it). But normally I would use typename.

The argument I have heard (that I think it is weak) is that Item does not need to be a class what happens if I specialize with int (that's not a class).

template<typename Item, typename Key>

Comments: Bad comments are worse than no comments. The problem with comments is that they are not checked by the compiler and thus overtime bad comments can diverge from the code. Then they become a maintenance problem. Do you believe the code or do you believe the comments (which do you fix)?

So you should make your comments describe WHY you are doing it. Maybe a very high level HOW (like the algorithm name with a link to the algorithm description on wikipedia).

You should not have comments the explain what the code is doing. If you have well named functions and variables this should be obvious from the code.

These are useless comments. I don't need a comment to tell me that this function adds a node to the graph. The name of the function tells me that it adds a node and it is a member of the Graph class so I know it is adding a node to a graph.

// adds a node to the graph
void addNode(const Label& name);

More useless comments.

// deletes a node from the graph
void deleteNode(const Label& name);
// adds a directed edge from name1 to name2

This is even worse

// forward declaration
class Node;

You are explaining the language to me now. I am pretty certain I can tell what that the next statement does.

Heap Interface

template<class Item, class Key>
class Heap {
public:
    // implements priority queue data ADT
    void insert(Item* val);
    Item* extract_min();
    void build_min_heap();
    int heapSize() const;
}

Requiring all members to have a member called key that has a type of Key is a it funkey. Technically with a tiny piece of work you could actually get the type Key automatically from the object (so we can ignore this).

But relying on the key member is not how we handle this situation normally. Rather we pass a type that knows how to compare objects.

Normally I would do:

template<typename Item, typename Compare = std::less<Item>>
class Heap {
};

The class Compare is a functor that tests if two objects of type Item can be compared less than each other.

Compare   comparator;
if (comparator(lhs, rhs)) { // is lhs < rhs
}

As shown above I would set a default type of std:less. The behavior of this is to use the classes built in operator< (if it does not have one you need to explicitly provide a comparator type).

Ownership:

void insert(Item* val);
Item* extract_min();

I suppose this interface you are passing ownership of the object to the heap and you expect the user to manually remove all items from the heap and call delete on them when you are done.

You should reflect this in your interface by using std::unique_ptr. This tells any user of your heap that you are passing ownership of the object to the heap. And when you return it pass by std::unique_ptr so that it is obvious that you are returning ownership of the object and the user is expected to delete it.

You also need to add a destructor to make sure any object left in the heap on destruction are correctly destroyed.

Normally containers use value semantics (not pointers). So you insert an object and the container takes a copy (or in C++11 moves the object content). I would suggest you move away from using pointers and use value semantics.

Heap Management

I don't like the need for people to manually rebuild the heap void build_min_heap();. When I insert an item I expect the heap to be placed in the correct place to maintain the heap.

What I would like to see as the interface is simply:

 T const&   top() const;       // get a reference to the top item
 void push(T const& val);      // push a new item into the queue
 void pop();                   // remove the top item.

 // If you want to get fancy and use modern C++ then maybe
 void push(T&& val);           // push using move semantics.
 template<typename... Args >
 void emplace(Args&&... args);

Graph

Interface

The only thing I don't like (and its not a major issue) is that the Dijkstra() method does not really seem to belong to a graph.

void Dijkstra(const Label& start);

This is strange though:

void listNeighbors(const Label& name);

List the Neighbors of a node? Where is the return value (the list of Neighbors), how am I supposed to use the values.

Now looking at the code you mean print the the Neighbors. Sure OK. I can see that.

Memory Leak

Node* n = new Node(name);
nodeMap_.insert( {name,n} ); // does nothing if name is already there

Does nothing except leak the node.

Again you are not doing correct memory management. You are passing objects around by pointer. This does not express the ownership semantics of the object and as a result you are going to leak memory like a sieve. If you must use owned pointers then learn how to use std::unique_ptr.

Adding Edges:

Why is there a difference between adding an in edge than an out edge.

    n1->addOutgoing(n2,w);
    n2->addIncoming(n1);   // I would expect this to have the same parameters.

Answer 2

Heap.h

I removed decrease_key and added two new member functions swapIndices and adjust_priority. Nodes now keep track of their position in the queue using an integer member variable idx_ located in the Node class. Unfortunately this leads to a tight coupling between the Node and the Heap classes.

template<class Item, class Compare = std::less<Item>>
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_; }
    void print() const;
    void adjust_priority(int i);
private:
    void swapIndices(Item* a, Item* 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; }
    int heapSize_ = 0;
    std::vector<Item*> myHeap_;
};

template<class Item, class Compare>
void Heap<Item,Compare>::insert(Item* val)
{
    val->idx_ = heapSize_;
    myHeap_.push_back(val);
    ++heapSize_;
}

template<class Item, class Compare>
void Heap<Item,Compare>::swapIndices(Item* a, Item* b)
{
    int temp = a->idx_;
    a->idx_ = b->idx_;
    b->idx_ = temp;
}

template<class Item, class Compare>
void Heap<Item,Compare>::adjust_priority(int i)
{
    while( i > 0 && myHeap_[parent(i)]->key() > myHeap_[i]->key() )
    {
        swapIndices( myHeap_[i], myHeap_[parent(i)] );
        std::iter_swap( myHeap_.begin()+i, myHeap_.begin()+parent(i) );
        i = parent(i);
    }
}

template<class Item, class Compare>
void Heap<Item,Compare>::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
        swapIndices( myHeap_[i], myHeap_[smallest] );
        std::iter_swap( myHeap_.begin()+i, myHeap_.begin()+smallest );
        min_heapify(smallest);
    }
}

template<class Item, class Compare>
Item* Heap<Item,Compare>::extract_min()
{
    Item* min = myHeap_[0];
    swapIndices( myHeap_[0], myHeap_[heapSize_-1] );
    std::iter_swap(myHeap_.begin(),myHeap_.begin() + heapSize_-1);
    // run min_heapify on the decremented heap
    --heapSize_;
    min_heapify(0);
    return min;
}

Graph.h

The graph destructor ~Graph and addNode function have now been modified to prevent memory leaks.

The Dijkstra method has been optimized by replacing build_min_heap with adjust_priority. I still haven't found a nice way to decouple Heap.h from Graph.h.

template<class Label, class Edge>
class Graph {
public:
    ~Graph() { for( auto it : nodeMap_) delete it.second; }
    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 Dijkstra(const Label& start);
private:
    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> Q;
};

template<class Label, class Edge> class
Graph<Label,Edge>::Node {
public:
    Node(const Label& name) : label_(name), Pi_(nullptr), d_(0), idx_(0) { std::cout << "Node '" << name << "' created" << "\n"; }
    ~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_; }
    void setkey(Edge key) { d_ = key; }
    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_;
    // position in underlying array
    int idx_;
};

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)
{
    if( ! pointerOf(name) ) // avoids memory leak if name is already there
    {
        Node* n = new Node(name);
        nodeMap_.insert( {name,n} );
    }
}

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>::printNeighbors(const Label& name)
{
    Node* n = pointerOf(name);
    for( auto it : n->outgoing_ ) std::cout << "(" << it.first->label_ << "," << it.second << ")" << " ";
    std::cout << "\n";
}

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.adjust_priority( it.first->idx_ );
            }
        }
    }
    // print out the shortest path weights
    for( auto it : S ) std::cout << "(" << it->label_ << "," << it->d_ << ")" << " ";
    std::cout << "\n";
}