directedgraph.cpp

/*= compile: g++ -std=c++11 -Wall $src -o $exe =*/
/*= run: $exe =*/

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <cassert>

using namespace std;

template <typename T>
using Data = T;

template <typename T>
struct vertex {
    Data<T> *data;
    map<int, vertex<T>*> linkedTo;
    vertex() {}
    explicit vertex(Data<T> *d) : data(d) {}
};

struct directedEdge {
    int x;
    int y;
};

template <typename T>
class directedGraph {
    map<int, vertex<T>*> vertices;
    vector<directedEdge> es;
public:
    directedGraph() : vertices(), es() {}

    ~directedGraph() {
        for (auto &i : vertices) {
            delete i.second;
        }
    }

    vertex<T>* createVertex(const int id, const Data<T> d) {
        Data<T> *data = new Data<T>(d);
        auto x = this->vertices[id] = new vertex<T>(data);
        return x;
    }

    void insert(const directedEdge &e, const map<int, T> &d) {
        vertex<T> *x, *y;
        auto fst = this->vertices.find(e.x);
        auto scd = this->vertices.find(e.y);

        if (fst == this->vertices.end()) {
            auto found = d.find(e.x);
            assert(found != d.end());
            x = this->createVertex(found->first, found->second);
        } else {
            x = fst->second;
        }

        if (scd == this->vertices.end()) {
            auto found = d.find(e.y);
            assert(found != d.end());
            y = this->createVertex(found->first, found->second);
        } else {
            y = scd->second;
        }

        // Create the link
        x->linkedTo[e.y] = y;
    }

    void traverse() const {
        if (this->vertices.empty()) {
            cout << "No elements in graph";
            return;
        }
        map<int, bool> isVisited;
        for (auto &i : this->vertices) {
            vector<T> links;
            if (isVisited[i.first] == false) {
                isVisited[i.first] = true;
                cout << "Found vertex: " << *i.second->data << endl;
            }
            for (auto &j : i.second->linkedTo) {
                if (isVisited[j.first] == false) {
                    isVisited[j.first] = true;
                    cout << "Found vertex: " << *j.second->data << endl;
                }
                links.push_back(*j.second->data);
            }
            cout << *i.second->data << " points to:" << endl;
            for (auto &j : links) {
                cout << "\t" << j << endl;
            }
            cout << endl;
        }
    }
};

int main() {
    map<int, string> data;
    data[1] = "Abhishek";
    data[2] = "Prasad";
    data[3] = "Compro";
    data[4] = "None";
    vector<directedEdge> edges = {{1, 2}, {2, 3}, {3, 1}, {1, 3}};
    directedGraph<string> d;
    for (auto &i : data) {
        d.createVertex(i.first, i.second);
    }
    for (unsigned i = 0; i < edges.size(); ++i) {
        d.insert(edges[i], data);
    }
    d.traverse();
    return 0;
}