2
\$\begingroup\$

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.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.