GraphAdjMatrix.h

Go to the documentation of this file.

#ifndef GRAPH_ADJ_MATRIX_H
#define GRAPH_ADJ_MATRIX_H
 
#include <stdexcept>    //out of range
#include <sstream>      //stringstream
 
#include "Element.h"    //DataStructure, unordered_map, string, cerr, using std
 
namespace bridges {
    namespace datastructure {
        template <typename K, typename E1 = K, typename E2 = E1>
        class GraphAdjMatrix : public DataStructure {
            private:
                unordered_map<K, Element<E1>* > vertices; // graph vertices
                unordered_map<K, unordered_map<K, int> > matrix; // adjacency matrix
                // maintain edge specific data
                unordered_map<K, unordered_map<K, E2> > edge_data;
 
            public:
                virtual const string getDStype() const override {
                    return "GraphAdjacencyMatrix";
                }
 
          virtual ~GraphAdjMatrix() {
            for (auto it : vertices)
              delete it.second;
          }
          GraphAdjMatrix() = default;
 
          // The default version of these functions would be incorrect.
          // So marking them delete to avoid problems.
          // We could write them if necessary
          GraphAdjMatrix(const GraphAdjMatrix&) = delete;
          GraphAdjMatrix& operator=(const GraphAdjMatrix&) = delete;
 
          
                void addVertex(const K& k, const E1& e = E1()) {
                    stringstream conv;
                    conv << k; //Converts key into string
                    vertices[k] = new Element<E1>(e, conv.str());
                    for (const auto& p : vertices) {
                        // edge weights are 0
                        matrix[k][p.first] = matrix[p.first][k] = 0;
                    }
                }
 
                void addEdge(const K& src, const K& dest, const unsigned int& wt) {
                    try {                   //create default link data
                        vertices.at(src)->links[vertices.at(dest)];
                        // add edge
                        matrix.at(src).at(dest) = wt;
                    }
                    catch (const out_of_range& ) {
                        cerr << "Cannot addEdge between non-existent verticies." << endl;
                        throw;
                    }
                }
                const unordered_map<K, unordered_map<K, int>>& getMatrix() const {
                    return matrix;
                }
 
                const unordered_map<K, int>& getMatrix(K key) const {
                    return matrix.at(key);
                }
 
                unordered_map<K, Element<E1> *>* getVertices() {
                    return &vertices;
                }
                const Element<E1>* getVertex(const K& key) const {
                    return vertices.at(key);
                }
 
                Element<E1>* getVertex(const K& key) {
                    return vertices.at(key);
                }
                E1  getVertexData (const K& src) {
                    try {
                        Element<E1> *el = vertices.at(src);
                        return  (vertices.at(src))->getValue();
                    }
                    catch ( const out_of_range& ) {
                        cerr << "getVertexData(): vertex not found" << endl;
                        throw;
                    }
                    // should never reach here
                    throw "getVertexData(): vertex not found";
                }
                void setVertexData (const K& vID, const E1& data) {
                    try {
                        Element<E1> *el = vertices.at(vID);
                        el->setValue (data);
                    }
                    catch ( const out_of_range& ) {
                        cerr << "setVertexData(): Nonexistent vertices or " <<
                            " edge not found" << endl;
                        throw;
                    }
                    catch (const char* msg) {
                        cerr << msg << endl;
                    }
                }
                E2 const & getEdgeData (const K& src, const K& dest) const {
                    try {
                        vertices.at(src);
                        vertices.at(dest);
                        return edge_data[src][dest];
                    }
                    catch ( const out_of_range& oor) {
                        cerr << "getEdgeData(): Nonexistent vertices or " <<
                            " edge not found" << endl;
                        throw;
                    }
                    catch (const char* msg) {
                        cerr << msg << endl;
                        throw;
                    }
                    // should never reach here
                    throw "getEdgeData(): Edge not found";
                }
                void setEdgeData (const K& src, const K& dest, const E2& data) {
                    try {
                        vertices.at(src);
                        vertices.at(dest);
                        edge_data[src][dest] = data;
                    }
                    catch ( const out_of_range& oor) {
                        cerr << "setEdgeData(): Nonexistent vertices or " <<
                            " edge not found" << endl;
                        throw;
                    }
                    catch (const char* msg) {
                        cerr << msg << endl;
                        throw;
                    }
                }
                ElementVisualizer *getVisualizer (const K& k) {
                    try {
                        Element<E1> *el = vertices.at(k);
 
                        return el->getVisualizer();
                    }
                    catch (const out_of_range& oor) {
                        cerr <<  "Graph vertex " << k << " not found in graph!" << endl;
                        throw;
                    }
                }
                LinkVisualizer *getLinkVisualizer (const K& k1, const K& k2) {
                    try {
                        Element<E1> *el1 = vertices.at(k1);
                        Element<E1> *el2 = vertices.at(k2);
 
                        return el1->getLinkVisualizer(el2);
                    }
                    catch (const out_of_range& oor) {
                        cerr <<  "Either source or destination node not found in graph!"
                            << endl;
                        throw;
                    }
                }
 
            private:
 
                virtual const string getDataStructureRepresentation() const override {
                    using bridges::JSONUtil::JSONencode;
 
                    // map the nodes to a sequence of ids, 0...N-1
                    // then get the JSON string for nodes placeholder
                    // nullptr prevents insertion of other nullptrs
 
                    unordered_map<K, int> node_map;
                    int i = 0;
                    string nodes_JSON = "", links_JSON = "";
 
                    for (const auto& v : this->vertices) {
                        if (node_map.emplace(v.first, i).second) {
                            i++;
                            nodes_JSON += v.second->getElementRepresentation() + COMMA;
                        }
                    }
 
                    //Remove trailing comma and nullptr entry
 
                    if (nodes_JSON.size()) {
                        nodes_JSON = nodes_JSON.erase(nodes_JSON.size() - 1);
                    }
 
                    // iterate through the N squared entries vertices and form the links JSON
 
                    for (const auto& src : vertices) {
                        for (const auto& dest : vertices) {
                            if (matrix.at(src.first).at(dest.first)) {  // link exists
                                Element<E1>* src_v = vertices.at(src.first);
                                Element<E1>* dest_v = vertices.at(dest.first);
                                links_JSON +=  src_v->getLinkRepresentation(
                                        *(src_v->getLinkVisualizer(dest_v)),
                                        JSONencode(node_map.at(src.first)),
                                        JSONencode(node_map.at(dest.first))) + COMMA;
                            }
                        }
                    }
 
                    //Remove trailing comma
                    if (links_JSON.size()) {
                        links_JSON = links_JSON.erase(links_JSON.size() - 1);
                    }
 
                    string graph_amatrix_json =
                        QUOTE + "nodes"  + QUOTE + COLON +
                        OPEN_BOX + nodes_JSON + CLOSE_BOX + COMMA +
                        QUOTE + "links" + QUOTE + COLON + OPEN_BOX +
                        links_JSON + CLOSE_BOX +
                        CLOSE_CURLY;
 
                    return graph_amatrix_json;
                }
        }; //end of GraphAdjList class
    }
}//end of bridges namespace
#endif