Dijkstra's single-source shortest-path using OpenMP

/*
 * WeightedGraph.h
 *
 *  Created on: Apr 24, 2011
 *      Author: cirvante
 */

#ifndef WEIGHTEDGRAPH_H_
#define WEIGHTEDGRAPH_H_

#include <limits>
#include <algorithm>
#include <stdexcept>
#include <string>
#include <list>
#include <vector>
#include <map>

using namespace std;

class Vertex;
class Edge;

typedef list<Edge*>::iterator                               AdjListIterator;
typedef map<string, Vertex*>::iterator                      GraphIterator;
typedef map<pair<Vertex*, Vertex*>, Edge* >::iterator       GraphEdgeIterator;
enum EdgeState { UNVISITED, DISCOVERY, BACK };


class WeightedGraph {
    public:
        WeightedGraph();
        ~WeightedGraph();
        int size() const;
        bool isEmpty() const;
        void insertVertex(string id);
        void insertEdge(string src, string dst, double cost);
        Vertex* opposite(Vertex* v, Edge* e) throw (logic_error);
        Vertex* getVertex(string id) throw (logic_error);
        map<string, Vertex*>* getVertices();
        vector<string> getVertexNames();
        double getDistance(Vertex* src, Vertex* dst) throw (logic_error);
        bool areAdjacent(Vertex* u, Vertex* v);
        void clearVisited();
        void printGraph();
    private:
        map<string, Vertex*> _internalVertexMap;
        map<pair<Vertex*, Vertex*>, Edge* > _globalEdgeMap;
        int _size;
};

class Vertex {
    public:
        string name;

        Vertex(const string n): name(n), _parent(NULL), _visited(false){}

        list<Edge*> neighbors() const;
        void addNeighbor(Edge* e);
        Vertex* parent() const;
        void setParent(Vertex* v);
        bool visited() const;
        void setVisited(bool visitState);

    private:
        list <Edge*> _neighbors;
        Vertex* _parent;
        bool _visited;
};

class Edge {
    public:

        Edge(const double c, Vertex* s, Vertex* d): _cost(c), _src(s), _dest(d), _state(UNVISITED){}

        double cost() const;
        enum EdgeState currentState() const;
        void setState(EdgeState state);
        Vertex* fromVertex() const;
        Vertex* toVertex() const;
        void setSource(Vertex* sourceVertex);
        void setDest(Vertex* destVertex);
        void setCost(double weight);

    private:
        double _cost;
        Vertex* _src;
        Vertex* _dest;
        EdgeState _state;
};
/*
* Just a small object to pass as a comparator for std::priority_queue. This is needed so the priority queue
* works as a min-heap and not a max-heap, as is the default implementation. That, and I never overloaded
* any operators in my Edge class.
*/
class PathCompare {
    public:
        bool operator()(const Edge* lhs, const Edge* rhs) const {
            return (lhs->cost() > rhs->cost());
        }
};

#endif /* WEIGHTEDGRAPH_H_ */


/*
 * WeightedGraph.cpp
 *
 *  Created on: Apr 25, 2011
 *      Author: cirvante
 */

#include <iostream>
#include "WeightedGraph.h"

/*
 * Implementation of class WeightedGraph
 */


WeightedGraph::WeightedGraph() { //Constructor
    _size = 0;
}

WeightedGraph::~WeightedGraph() {}

int WeightedGraph::size() const { //Returns the number of vertices
    return _size;
}

bool WeightedGraph::isEmpty() const { //Returns whether the graph is empty or not
    return _size == 0;
}

void WeightedGraph::insertVertex(string id) { //Inserts a vertex into the internal map
    Vertex* newVertex = new Vertex(id);
    _internalVertexMap[id] = newVertex;
    ++_size;
    /*
    for(GraphIterator itr = _internalVertexMap.begin(); itr != _internalVertexMap.end(); ++itr) {
        cout << itr->second->name << endl;
    }

    cout << endl;
    */
}

Vertex* WeightedGraph::getVertex(string id) throw (logic_error) {
    if (_internalVertexMap.empty()) throw logic_error("Graph is empty.");
    Vertex* vtr = _internalVertexMap[id];
    if (vtr == NULL) throw logic_error("Vertex does not exist.");
    return vtr;
}

map<string, Vertex*>* WeightedGraph::getVertices() {
    return &_internalVertexMap;
}

vector<string> WeightedGraph::getVertexNames() {
    vector<string> vtr;
    for (GraphIterator itr = _internalVertexMap.begin(); itr != _internalVertexMap.end(); ++itr) {
        vtr.push_back(itr->first);
    }
    return vtr;
}

//inserts an edge connecting the given vertices and adds said edge to both vertices' adjacency lists
void WeightedGraph::insertEdge(string src, string dst, double cost) {

    Vertex* srcVertex = _internalVertexMap[src];
    Vertex* dstVertex = _internalVertexMap[dst];
    Edge* newEdge = new Edge(cost, srcVertex, dstVertex);          //create a new edge
    srcVertex->addNeighbor(newEdge);                    //add edge to incidence lists of both vertices
    dstVertex->addNeighbor(newEdge);
    _globalEdgeMap[make_pair(srcVertex, dstVertex)] = newEdge;          //add edge to the global list (for printing purposes)

    /*
    for(GraphIterator itr = _internalVertexMap.begin(); itr != _internalVertexMap.end(); ++itr) {
        cout << "Opposite of " << itr->second->name << " is ";
        try {
            cout << opposite(itr->second, newEdge)->name << endl;
        }
        catch (logic_error &incidenceFailure) {
            cout << incidenceFailure.what() << endl;
        }
    }
    */
}

//returns the weight of the edge between two vertices. If the vertices are not adjacent, then the largest possible double is returned.
double WeightedGraph::getDistance(Vertex* src, Vertex* dst) throw (logic_error) {

    //if one or both vertices have no incident edges, throw an exception.
    if (src->neighbors().empty() || dst->neighbors().empty()) throw logic_error("Vertex is a singleton");
    else if (src == dst) return 0.0;
    if (areAdjacent(src, dst))
        return _globalEdgeMap[make_pair(src, dst)]->cost();
    else if (areAdjacent(dst, src))
        return _globalEdgeMap[make_pair(dst, src)]->cost();
    else return numeric_limits<double>::infinity();
}

//returns a pointer to the vertex opposite to v along the given edge e
Vertex* WeightedGraph::opposite(Vertex* v, Edge* e) throw (logic_error) {
    //if the vertex has no neighbors (i.e., it is the only vertex in the graph, it has no opposite
    //we throw an exception instead of returning a null pointer
    if (v->neighbors().empty()) throw logic_error("Vertex is a singleton");
    if (v == e->fromVertex())
        return e->toVertex();        //if v is the edge's source vertex, return its destination vertex
    else if (v == e->toVertex())
        return e->fromVertex();      //if v is the edge's destination vertex, return its source vertex
    //if the edge is not incident on the vertex, throw an exception
    else throw logic_error("Edge is not incident on the given vertex");
}

//returns whether or not two vertices are adjacent
bool WeightedGraph::areAdjacent(Vertex* u, Vertex* v) {

    if (_globalEdgeMap.find(make_pair(u, v)) != _globalEdgeMap.end()) return true;
    else return false;
}

//Makes all previously visited nodes and edges un-visited.
void WeightedGraph::clearVisited() {
    for(GraphIterator itr = _internalVertexMap.begin(); itr != _internalVertexMap.end(); ++itr) {
        itr->second->setVisited(false);
    }

    for (GraphEdgeIterator itr2 = _globalEdgeMap.begin(); itr2 != _globalEdgeMap.end(); ++itr2) {
        itr2->second->setState(UNVISITED);
    }
}

//Prints all edges in the graph and their weights.
void WeightedGraph::printGraph() {

    cout << "Printing all edges currently in graph: " << endl;
    //for each edge on the list, print its cost and the names of its end vertices
    for(GraphEdgeIterator itr = _globalEdgeMap.begin(); itr != _globalEdgeMap.end(); ++itr) {
        cout << "(" << itr->second->fromVertex()->name << ", " << itr->second->toVertex()->name << ") : cost " << itr->second->cost() << endl;
    }
    cout << endl;
}

/*
 * Implementation of class Vertex
 */

//returns the adjacency list of the vertex
list<Edge*> Vertex::neighbors() const {
    return _neighbors;
}

//adds an edge to the vertex's adjacency list
void Vertex::addNeighbor(Edge* e) {
    _neighbors.push_back(e);
}

//returns a pointer to this vertex's parent vertex (for traversal purposes)
Vertex* Vertex::parent() const {
    return _parent;
}

//sets the vertex's parent vertex (for traversal purposes)
void Vertex::setParent(Vertex* v) {
    _parent = v;
}

//returns whether this vertex has been visited previously in a traversal
bool Vertex::visited() const {
    return _visited;
}

void Vertex::setVisited(bool visitState) {
    _visited = visitState;
}

/*
 * Implementation of class Edge
 */

//returns the edge weight
double Edge::cost() const {
    return _cost;
}

//returns the edge's current state (for traversal purposes)
enum EdgeState Edge::currentState() const {
    return _state;
}

//sets the edge's current state to either discovery or back (for traversal purposes)
void Edge::setState(EdgeState state) {
    _state = state;
}

//returns the edge's source vertex
Vertex* Edge::fromVertex() const {
    return _src;
}

//returns the edge's destination vertex
Vertex* Edge::toVertex() const {
    return _dest;
}

//sets the edge's source vertex
void Edge::setSource(Vertex* sourceVertex) {
    _src = sourceVertex;
}

//sets the edge's destination vertex
void Edge::setDest(Vertex* destVertex) {
    _dest = destVertex;
}

//sets the edge weight
void Edge::setCost(double weight) {
    _cost = weight;
}

/*
 * GraphTest.cpp
 *
 *  Created on: Apr 30, 2011
 *      Author: cirvante
 */

#include <stack>
#include <queue>
#include <iostream>
#include <fstream>
#include <omp.h>
#include "WeightedGraph.h"

void depthFirstSearch(WeightedGraph& graph, string startV, string endV);
void enqueueAll(WeightedGraph& graph, Vertex* v, list<Edge*> adjList, queue<Vertex*>& nq);

void DijkstraShortestPath(WeightedGraph& graph, string sourceV);
void printPQ(priority_queue< Edge*, vector<Edge*>, PathCompare > pq);

int main() {

    WeightedGraph wg = WeightedGraph();

    char filename[64];
    cout << "Enter filename: ";
    cin >> filename;

    ifstream inFile(filename, ios::in);
    if (!inFile) {
        cout << "ERROR: File not found, terminating..." << endl;
        return 1;
    }

    char v1[64];
    char v2[64];
    double wt;

    while (inFile >> v1 >> v2 >> wt) {
        wg.insertVertex(v1);
        wg.insertVertex(v2);
        wg.insertEdge(v1, v2, wt);
    }

    //uncommenting this and commenting the file-handling code makes it work right
    /*
    wg.insertVertex("narf");
    wg.insertVertex("balls");
    wg.insertVertex("narf");
    wg.insertVertex("foo");
    wg.insertVertex("derp");
    wg.insertVertex("pie");
    wg.insertVertex("cox");
    wg.insertEdge("foo", "derp", 50);
    wg.insertEdge("narf", "balls", 30);
    wg.insertEdge("foo", "balls", 20);
    wg.insertEdge("balls", "derp", 60);
    wg.insertEdge("derp", "narf", 40);
    wg.insertEdge("derp", "cox", 30);
    wg.insertEdge("foo", "narf", 50);
    wg.insertEdge("narf", "pie", 99);
    wg.insertEdge("cox", "pie", 15);
    wg.insertEdge("cox", "narf", 10);
    */

    wg.printGraph();

    vector<string> vid = wg.getVertexNames();

    #pragma omp parallel for ordered
    for (int i = 0; i < vid.size(); ++i) {
        #pragma omp ordered
        cout << "[thread:" << omp_get_thread_num() << "] ";
        DijkstraShortestPath(wg, vid[i]);
    }

    return 0;

}

void depthFirstSearch(WeightedGraph& graph, string startV, string endV) {


    stack<Vertex*, vector<Vertex*> > vStack;
    queue<Vertex*> vQueue;
    bool found = false;

    Vertex *start, *end, *u, *v;

    start = graph.getVertex(startV);
    end = graph.getVertex(endV);

    graph.clearVisited();
    vStack.push(start);

    cout << "Performing depth-first search of vertex " << end->name << " from vertex " << start->name << endl;

    do {
        u = vStack.top();
        vStack.pop();
        if (u == end) {
            cout << u->name << endl;;
            found = true;
        }
        else {
            if (u->visited() == false) {
                u->setVisited(true);
                cout << u->name << " --> ";
                enqueueAll(graph, u, u->neighbors(), vQueue);

                while (!vQueue.empty()) {
                    v = vQueue.front();
                    vQueue.pop();
                    if (v->visited() == false) vStack.push(v);
                }
            }
        }
    }
    while (!vStack.empty() && !found);

    if (!found) cout << "Vertex was not found.";
    cout << endl;

}

void enqueueAll(WeightedGraph& graph, Vertex* v, list<Edge*> adjList, queue<Vertex*>& nq) {
    for (AdjListIterator itr = adjList.begin(); itr != adjList.end(); ++itr) {
        Vertex* vte = graph.opposite(v, *itr);
        nq.push(vte);
    }
}

void DijkstraShortestPath(WeightedGraph& graph, string sourceV) {

    Vertex* src = graph.getVertex(sourceV);
    Edge* pathEdge = new Edge(0.0, src, src);
    double minDist;
    priority_queue< Edge*, vector<Edge*>, PathCompare > pq;
    queue<Vertex*> vQueue;
    Vertex* v;

    graph.clearVisited();
    pq.push(pathEdge);

    cout << "Showing single-source shortest path run for source vertex " << src->name << ". Format is (start, end) : cost." << endl;

    do {
        pathEdge = pq.top();
        pq.pop();
        //Vertex* from = pathEdge->fromVertex();
        Vertex* to = pathEdge->toVertex();
        if (to->visited() == false) {
            to->setVisited(true);
            //cout << "(" << from->name << ", " << to->name << " : cost " << pathEdge->cost() << ")" << endl;
            cout << "(" << src->name << ", " << to->name << " : cost " << pathEdge->cost() << ")" << endl;
            pathEdge->setSource(to);
            minDist = pathEdge->cost();

            enqueueAll(graph, pathEdge->fromVertex(), pathEdge->fromVertex()->neighbors(), vQueue);

            while (!vQueue.empty()) {
                v = vQueue.front();
                vQueue.pop();

                if (v->visited() == false) {
                    pathEdge->setDest(v);
                    //cout << from->name << " " << v->name <<endl;
                    //cout << pathEdge->cost() << endl;
                    pathEdge->setCost(minDist + graph.getDistance(pathEdge->fromVertex(), v));
                    //cout << pathEdge->cost() << endl;
                    pq.push(new Edge(pathEdge->cost(), pathEdge->fromVertex(), pathEdge->toVertex()));
                    //printPQ(pq);
                }
            }
        }
    }
    while(!pq.empty());

    cout << endl;

}

void printPQ(priority_queue< Edge*, vector<Edge*>, PathCompare > pq) {
    cout << "Printing contents of edge priority queue: " << endl;
    while (!pq.empty()) {
        Edge* e = pq.top();
        cout << e->fromVertex()->name << " " << e->toVertex()->name << " " << e->cost() << endl;
        pq.pop();
    }
    cout << endl;
}