GraphAdjList.h

Go to the documentation of this file.

#ifndef GRAPH_ADJ_LIST
#define GRAPH_ADJ_LIST
 
#include <stdexcept>
#include <sstream>
#include <unordered_map>
#include <JSONutil.h>
 
using namespace std;
 
#include "SLelement.h"
#include "Edge.h"
 
namespace bridges {
    namespace datastructure {
        template<typename K, typename E1 = K, typename E2 = E1>
        class GraphAdjList : public DataStructure {
            private:
                // list of graph vertices
                // maintained as a map to accommodate strings
                unordered_map<K, Element<E1>* > vertices;
                // adjacency lists
                unordered_map<K, SLelement<Edge<K, E2> >*> adj_list;
 
                // large graph related
                static const int LargeGraphVertSize = 2000;
 
                bool forceLargeViz = false;
                bool forceSmallViz = false;
 
                GraphAdjList(const GraphAdjList& gr) = delete; //would not be correct
                const GraphAdjList& operator= (const GraphAdjList& gr) = delete; //would not be correct
            public:
 
                GraphAdjList() = default;
                GraphAdjList(GraphAdjList&& gr) = default;
 
                virtual ~GraphAdjList() override {
                    for (auto& v : vertices) {
                        if (adj_list[v.first]) {
                            // discard the edges in the adj. list
                            SLelement<Edge<K, E2 >> *tmp;
                            for (SLelement<Edge<K, E2 >> *sle =
                                    adj_list[v.first]; sle != nullptr; ) {
                                tmp = sle;
                                sle = sle->getNext();
                                delete tmp;
                            }
                            adj_list[v.first] = nullptr;
                        }
                        delete vertices[v.first]; // free the element at v
                        vertices[v.first] = nullptr;
 
                    }
                }
                virtual const string getDStype() const override {
                    if (forceLargeViz || (!forceSmallViz &&
                            vertices.size() > LargeGraphVertSize &&
                            areAllVerticesLocated())) {
                        return "largegraph";
                    }
                    return "GraphAdjacencyList";
                }
 
                void addVertex(const K& k, const E1& e = E1()) {
                    stringstream conv;
                    conv << k;
                    if (vertices.find(k) == vertices.end()) {
                        // vertex does not exist, create one
                        vertices[k] = new Element<E1>(e, conv.str());
                        adj_list[k] = nullptr;
                    }
                }
                void addEdge(const K& src, const K& dest, const E2& data = E2()) {
                    try {
                        vertices.at(src);
                        vertices.at(dest);
                        // links structure is redundant and needs
                        // to be removed in future implementations!
                        vertices[src]->links[vertices.at(dest)]; //In C++ this creates the linkvisualizer
 
                        stringstream conv;
                        conv << dest;
                        // add the edge
                        adj_list.at(src) =
                            new SLelement<Edge<K, E2> > (adj_list.at(src),
                            Edge<K, E2> (src, dest, &(vertices[src]->links[vertices.at(dest)]), data), conv.str());
 
                    }
                    catch ( const out_of_range& ) {
                        cerr << "addEdge(): Nonexistent vertex?" << endl <<
                            "Create vertices first prior to adding edges that use that vertex" << endl
                            <<  "Cannot add edge between non-existent verticies"
                            << endl;
                        throw;
                    }
                }
                bool isEdge(const K& src, const K& dest) {
                    try {
                        vertices.at(src);
                        vertices.at(dest);
                        for (auto& e : outgoingEdgeSetOf(src))
                            if (e.to() == dest) { // found it
                                cout << "found it!" << src << "," << dest << endl;
                                return true;
                            }
                    }
                    catch ( const out_of_range& ) {
                        return false;
                    }
                    return false;
                }
                const 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& vertID, E1 const & data) {
                    try {
                        Element<E1> *el = vertices.at(vertID);
                        el->setValue (data);
                    }
                    catch ( const out_of_range& ) {
                        cerr << "setVertexData(): Nonexistent vertex" << endl;
                        throw;
                    }
                    catch (const char* msg) {
                        cerr << msg << endl;
                    }
                }
                E2&  getEdgeData (const K& src, const K& dest) {
                    try {
                        vertices.at(src);
                        vertices.at(dest);
                        SLelement<Edge<K, E2> > *sle = adj_list.at(src);
                        while (sle) {
                            Edge<K, E2> ed = sle->getValue();
                            if (ed.to() == dest) { //edge exists
                                return ed.getEdgeData();
                            }
                            sle = sle->getNext();
                        }
                        throw "Edge not found!";
                    }
                    catch ( const out_of_range& ) {
                        cerr << "getEdgeData(): Edge not found" << endl;
                        throw;
                    }
                    catch (const char* msg) {
                        cerr << msg << endl;
                    }
                    // should never reach here
                    throw "getEdgeData(): Edge not found";
                }
                E2 const&  getEdgeData (const K& src, const K& dest) const {
                    try {
                        vertices.at(src);
                        vertices.at(dest);
                        SLelement<Edge<K, E2> > *sle = adj_list.at(src);
                        while (sle) {
                            Edge<K, E2> ed = sle->getValue();
                            if (ed.getVertex() == dest) { //edge exists
                                return ed.getEdgeData();
                            }
                            sle = sle->getNext();
                        }
                        throw "Edge not found!";
                    }
                    catch ( const out_of_range& ) {
                        cerr << "getEdgeData(): Edge not found" << endl;
                        throw;
                    }
                    catch (const char* msg) {
                        cerr << msg << endl;
                    }
                    // should never reach here
                    throw "getEdgeData(): Edge not found";
                }
 
                void setEdgeData (const K& src, const K& dest, E2& data) {
                    try {
                        vertices.at(src);
                        vertices.at(dest);
                        SLelement<Edge<K, E2> > *sle = adj_list.at(src);
                        while (sle) {
                            Edge<K, E2> ed = sle->getValue();
                            if (ed.to() == dest) { //edge exists
                                ed.setEdgeData(data); //change edge data
                                sle->setValue(ed); //change slelement data
                                return;
                            }
                            sle = sle->getNext();
                        }
                        throw "getEdgeData(): Edge not found!";
                    }
                    catch ( const out_of_range& ) {
                        cerr << "setEdgeData(): Nonexistent vertices or " <<
                            " edge not found" << endl;
                        throw;
                    }
                    catch (const char* msg) {
                        cerr << msg << endl;
                    }
                    // will never reach here, but avoids compiler warnings
                    throw "getEdgeData(): Edge not found";
                }
                unordered_map<K, Element<E1>*>* getVertices() {
                    return &vertices;
                }
 
                const unordered_map<K, Element<E1>*>* getVertices() const {
                    return &vertices;
                }
                const Element<E1>* getVertex(const K& key) const {
                    try {
                        return vertices.at(key);
                    }
                    catch (const std::out_of_range& oor) {
                        /* std::cerr << "Out of Range error: " << oor.what() */
                        /*  << "returning null pointer\n"; */
                        return nullptr;
                    }
                }
 
                Element<E1>* getVertex(const K& key) {
                    try {
                        return vertices.at(key);
                    }
                    catch (const std::out_of_range& oor) {
                        /* std::cerr << "Out of Range error: " << oor.what() */
                        /*  << "returning null pointer\n"; */
                        return nullptr;
                    }
                }
 
                Edge<K, E2> getEdge(const K& src, const K& dest) {
                    // check to see if the two vertices exist, else
                    // return null
                    try  {
                        // look for the edge
                        SLelement<Edge<K, E2 >> *sle = adj_list[src];
                        while (sle != nullptr) {
                            K edge_dest = ((Edge<K, E2>) sle->getValue()).to();
                            if (edge_dest == dest)  // found
                                return sle->getValue();
                            sle = sle->getNext();
                        }
                    }
                    catch (const std::out_of_range& oor) {
                        // one or both vertices doesnt exist
                        std::cout << "one or both vertices are likely missing from graph\n";
                        throw;
                    }
                    throw "Edge not found";
                }
 
                const unordered_map<K, SLelement<Edge<K, E2> >*>&
                getAdjacencyList() const {
                    return adj_list;
                }
 
                SLelement<Edge<K, E2> >* getAdjacencyList(const K& k) {
                    try {
                        return adj_list.at(k);
                    }
                    catch (const out_of_range& ) {
                        cerr <<  "Cannot get adjacencyList of a non-existent vertex -- " << k << "\n";
                        throw;
                    }
                }
 
                const SLelement<Edge<K, E2> >* getAdjacencyList(const K& k) const {
                    try {
                        return adj_list.at(k);
                    }
                    catch (const out_of_range& ) {
                        cerr <<  "Cannot getAdjacencyList() of a non-existent vertex!"
                            << endl;
                        throw;
                    }
                }
 
                ElementVisualizer *getVisualizer (const K& k) {
                    try {
                        Element<E1> *el = vertices.at(k);
 
                        return el->getVisualizer();
                    }
                    catch (const out_of_range& ) {
                        cerr <<  "Graph vertex " << k << " not found in graph!" << endl;
                        throw;
                    }
                }
                LinkVisualizer *getLinkVisualizer (const K& k1, const K& k2) {
                    try {
                        return getEdge(k1, k2).getLinkVisualizer();
                    }
                    catch (const out_of_range& ) {
                        cerr <<  "Either source or destination node not found in graph!\n";
                        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
 
                    // check for large graph
                    if (forceLargeViz ||
                        (!forceSmallViz &&
                            vertices.size() > LargeGraphVertSize &&
                            areAllVerticesLocated())) {
                        return getDataStructureRepresentationLargeGraph();
                    }
 
                    unordered_map<K, int> node_map;
                    int i = 0;
                    string nodes_JSON = "", links_JSON = "";
 
                    for (const auto& v : 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 vertices and form the links JSON
 
                    for (const auto& v : vertices) {
                        // get adj. list
                        Element<E1>* src_vert = vertices.at(v.first);
                        // iterate through list and form links
                        for (SLelement<Edge<K, E2 >> * it = adj_list.at(v.first); it != nullptr;
                            it = it->getNext()) {
                            Element<E1>* dest_vert = vertices.at(it->getValue().to() );
                            links_JSON +=  src_vert->getLinkRepresentation(
                                    *(src_vert->getLinkVisualizer(dest_vert)),
                                    JSONencode(node_map.at(v.first)),
                                    JSONencode(node_map.at(it->getValue().to())) ) + COMMA;
                        }
                    }
 
                    //Remove trailing comma
                    if (links_JSON.size()) {
                        links_JSON = links_JSON.erase(links_JSON.size() - 1);
                    }
 
                    string graph_alist_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_alist_json;
                }
                string getDataStructureRepresentationLargeGraph () const {
 
                    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 = "";
 
                    for (const auto& v : vertices) {
                        if (node_map.emplace(v.first, i).second) {
                            i++;
                            const ElementVisualizer *elvis =
                                vertices.at(v.first)->getVisualizer();
                            string loc_str = "";
                            if ( (elvis->getLocationX() != INFINITY) &&
                                (elvis->getLocationY() != INFINITY) ) {
                                loc_str =
                                    OPEN_BOX +
                                    JSONencode(elvis->getLocationX())  + COMMA +
                                    JSONencode(elvis->getLocationY()) +
                                    CLOSE_BOX + COMMA;
                            }
                            nodes_JSON +=  OPEN_BOX + loc_str +
                                elvis->getColor().getCSSRepresentation() +
                                CLOSE_BOX + COMMA;
                        }
                    }
 
                    //Remove trailing comma and nullptr entry
 
                    if (nodes_JSON.size()) {
                        nodes_JSON = nodes_JSON.erase(nodes_JSON.size() - 1);
                    }
 
                    // next link information
                    string links_JSON =  "";
                    for (const auto& v : vertices) {
                        // get adj. list
                        Element<E1>* src_vert = vertices.at(v.first);
                        // iterate through list and form links
                        for (SLelement<Edge<K, E2 >> * it = adj_list.at(v.first); it != nullptr;
                            it = it->getNext()) {
                            Element<E1>* dest_vert = vertices.at(it->getValue().to() );
                            LinkVisualizer *lv = src_vert->getLinkVisualizer(dest_vert);
                            string src = JSONencode(node_map.at(v.first));
                            string dest = JSONencode(node_map.at(it->getValue().to()));
                            links_JSON +=  OPEN_BOX +
                                src  + COMMA +
                                dest + COMMA +
                                lv->getColor().getCSSRepresentation() +
                                CLOSE_BOX + COMMA;
 
                        }
                    }
                    //Remove trailing comma
                    if (links_JSON.size())
                        links_JSON = links_JSON.erase(links_JSON.size() - 1);
 
                    string graph_alist_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_alist_json;
 
                }
                bool areAllVerticesLocated() const {
                    for (const auto& v : vertices) {
                        ElementVisualizer *elvis = v.second->getVisualizer();
                        if (elvis->getLocationX() == INFINITY
                            || elvis->getLocationY() == INFINITY)
                            return false;
                    }
                    return true;
                }
 
            public:
 
                void forceLargeVisualization(bool f) {
                    if (f) {
                        forceLargeViz = true;
                        forceSmallViz = false;
                    }
                    else {
                        forceLargeViz = false;
                    }
                }
 
                void forceSmallVisualization(bool f) {
                    if (f) {
                        forceSmallViz = true;
                        forceLargeViz = false;
                    }
                    else {
                        forceSmallViz = false;
                    }
                }
 
                //  @brief This is a helper class to return sets of vertices
                //  in a  way that are iterable with range for loops.
                //  Students should not have to use this directly.
                class KeySet_helper {
                        std::unordered_map<K, Element<E1>* > const & underlying_map;
 
                    public:
                        KeySet_helper (std::unordered_map<K, Element<E1>* > const  & um)
                            : underlying_map(um)
                        {}
 
                        class const_iterator {
                                typename std::unordered_map<K, Element<E1>* >::const_iterator it;
                            public:
                                const_iterator(typename std::unordered_map<K, Element<E1>* >::const_iterator i )
                                    : it(i)
                                {}
 
                                bool operator!=(const const_iterator& it) const {
                                    return this->it != it.it;
                                }
 
                                const K& operator*() const {
                                    return it->first;
                                }
 
                                const_iterator& operator++() {
                                    it ++;
                                    return *this;
                                }
                        };
 
                        const_iterator begin() const {
                            return const_iterator(underlying_map.begin());
                        }
 
                        const_iterator end() const {
                            return const_iterator(underlying_map.end());
                        }
                };
 
                KeySet_helper keySet() const {
                    return KeySet_helper(this->vertices);
                }
 
                typename SLelement<Edge<K, E2 >>::SLelement_listhelper
                outgoingEdgeSetOf(K const & k) {
                    return typename SLelement<Edge<K, E2 >>::SLelement_listhelper(getAdjacencyList(k));
                }
 
                typename SLelement<Edge<K, E2 >>::SLelement_constlisthelper
                outgoingEdgeSetOf(K const & k) const {
                    return typename SLelement<Edge<K, E2 >>::SLelement_constlisthelper(getAdjacencyList(k));
                }
 
                class VertexElementSet_listhelper {
                        typename std::unordered_map<K, Element<E1>* > & underlying_map;
 
                    public:
                        VertexElementSet_listhelper (std::unordered_map<K, Element<E1>* > & um)
                            : underlying_map(um)
                        {}
 
                        class iterator {
                                typename std::unordered_map<K, Element<E1>* >::iterator it;
                            public:
                                iterator(typename std::unordered_map<K, Element<E1>* >::iterator i )
                                    : it(i)
                                {}
 
                                bool operator!=(const iterator & it) const {
                                    return this->it != it.it;
                                }
 
                                Element<E1>*  operator*()  {
                                    return it->second;
                                }
 
                                iterator & operator++() {
                                    it ++;
                                    return *this;
                                }
                        };
 
                        class const_iterator {
                                typename std::unordered_map<K, Element<E1>* >::const_iterator it;
                            public:
                                const_iterator(typename std::unordered_map<K, Element<E1>* >::const_iterator i )
                                    : it(i)
                                {}
 
                                bool operator!=(const const_iterator & it) const {
                                    return this->it != it.it;
                                }
 
                                Element<E1> const*  operator*() const {
                                    return it->second;
                                }
 
                                const_iterator & operator++() {
                                    it ++;
                                    return *this;
                                }
                        };
 
                        iterator begin() {
                            return iterator(underlying_map.begin());
                        }
 
                        iterator end() {
                            return iterator(underlying_map.end());
                        }
 
                        const_iterator begin() const {
                            return const_iterator(underlying_map.begin());
                        }
 
                        const_iterator end() const {
                            return const_iterator(underlying_map.end());
                        }
 
                };
 
                VertexElementSet_listhelper vertexSet () {
                    return VertexElementSet_listhelper(vertices);
                }
 
                class constVertexElementSet_listhelper {
                        typename std::unordered_map<K, Element<E1>* > const & underlying_map;
 
                    public:
                        constVertexElementSet_listhelper (std::unordered_map<K, Element<E1>* > const & um)
                            : underlying_map(um)
                        {}
 
                        class const_iterator {
                                typename std::unordered_map<K, Element<E1>* >::const_iterator it;
                            public:
                                const_iterator(typename std::unordered_map<K, Element<E1>* >::const_iterator i )
                                    : it(i)
                                {}
 
                                bool operator!=(const const_iterator & it) const {
                                    return this->it != it.it;
                                }
 
                                Element<E1> const*  operator*() const {
                                    return it->second;
                                }
 
                                const_iterator & operator++() {
                                    it ++;
                                    return *this;
                                }
                        };
 
                        const_iterator begin() const {
                            return const_iterator(underlying_map.begin());
                        }
 
                        const_iterator end() const {
                            return const_iterator(underlying_map.begin());
                        }
                };
                constVertexElementSet_listhelper vertexSet () const {
                    return constVertexElementSet_listhelper(vertices);
                }
        };
 
        //end of GraphAdjList class
    }
}//end of bridges namespace
#endif