#include "graph.h"

graph::graph() : directed(false) { }
graph::graph(bool dir) : directed(dir) { }

int graph::addVertex(const char* vert) {
    return vtxlst.addVertex(vert, adjList, adjMatrix);
}

bool graph::addEdge(const char* src, const char* dest, double weight, bool dir) {
    return edglst.addEdge(src, dest, weight, vtxlst, adjList, adjMatrix, dir);
}

void graph::displayVertices() const { cout << vtxlst << '\n'; }
void graph::displayEdges() const {
    for (unsigned int i=0; i<edglst.size(); i++) {
        edge e = edglst.getEdge(i);
        cout << vtxlst.getVertexName(e.from) << " --> "
             << vtxlst.getVertexName(e.to) << " ("
             << e.weight << ")\n";
    }
}

unsigned int graph::getVertexListSize() const { return vtxlst.size(); }
unsigned int graph::getEdgeListSize() const { return edglst.size(); }

void graph::displayAdjacencyList() const {
    for (unsigned int i=0; i<adjList.size(); i++) {
        cout << vtxlst.getVertexName(i) << ": ";
        if (adjList[i].size() == 0) cout << "None\n";
        else {
            for (unsigned int j=0; j<adjList[i].size(); j++) {
                if (j>0) cout << ", ";
                cout << "-->" << vtxlst.getVertexName(adjList[i][j].to)
                     << " (" << adjList[i][j].weight << ")";
            }
            cout << '\n';
        }
    }
}

void graph::displayAdjacencyMatrix() const {
    unsigned int i, j;
    cout << "   ";
    for (i=0; i<adjMatrix.size(); i++) {
        cout << setfill(' ') << setw(3) << vtxlst.getVertexName(i);
    }
    cout << '\n';
    for (i=0; i<adjMatrix.size(); i++) {
        cout << setw(2) << vtxlst.getVertexName(i) << ':';
        for (j=0; j<adjMatrix[i].size(); j++) {
            cout << setw(3) << (int)adjMatrix[i][j];
        }
        cout << '\n';
    }
}

void graph::shortestPath(const char* src, const char* dest) {
        const double DOUBLE_MAX = 1000000000.0;
    // make sure source vertex exists
    int posSrc = vtxlst.findVertex(src);
    if (posSrc == -1) {
        cout << "Error: Source vertex not found: " << src << '\n';
        return;
    }

    // make sure destination vertex exists
    int posDest = vtxlst.findVertex(dest);
    if (posDest == -1) {
        cout << "Error: Destination vertex not found: "
             << dest << '\n';
        return;
    }

    unsigned int i, j, v=0, x=0;
    vector<vector<int> > minPath;
    vector<double> minWeight;
    vector<bool> weightFound;
 
    for (i=0; i<vtxlst.size(); i++) {
        vector<int>* vint = new vector<int>();
        minPath.push_back(*vint);
        double wgt = adjMatrix[posSrc][i];
        if (wgt == 0.0) wgt = DOUBLE_MAX;
        else {
            if ((int) i != posSrc) minPath[i].push_back(posSrc);
            minPath[i].push_back(i);
        }
        minWeight.push_back(wgt);
        weightFound.push_back(false);
    }

    minWeight[posSrc] = 0;
    weightFound[posSrc] = true;

    for (i=0; i<vtxlst.size()-1; i++) {
        double min = DOUBLE_MAX;
        for (j=0; j<vtxlst.size(); j++) {
            if (!weightFound[j]) {
                if (minWeight[j] < min) {
                    v = j;
                    min = minWeight[v];
                }
            }
        }
        weightFound[v] = true;

        for (j=0; j<vtxlst.size(); j++) {
            if (!weightFound[j]) {
                double wgt = adjMatrix[v][j];
                if (wgt != 0.0 && (min + wgt < minWeight[j])) {
                    minWeight[j] = min + wgt;
                    minPath[j].clear();
                    for (x=0; x<minPath[v].size(); x++) {
                        minPath[j].push_back(minPath[v][x]);
                    }
                    minPath[j].push_back(j);
                }
            }
        }
    }

    for (x=0; x<minPath[posDest].size(); x++) {
        cout << minPath[posDest][x] << ' ';
    }
    cout << '\n';
    return;
}