/**
 * @file graph_tools.cpp
 * This is where you will implement several functions that operate on graphs.
 * Be sure to thoroughly read the comments above each function, as they give
 *  hints and instructions on how to solve the problems.
 */

#include "graph_tools.h"

/**
 * Finds the minimum edge weight in the Graph graph.
 * THIS FUNCTION IS GRADED.
 *
 * @param graph - the graph to search
 * @return the minimum weighted edge
 *
 * @todo Label the minimum edge as "MIN". It will appear blue when
 *  graph.savePNG() is called in minweight_test.
 *
 * @note You must do a traversal.
 * @note You may use the STL stack and queue.
 * @note You may assume the graph is connected.
 *
 * @hint Initially label vertices and edges as unvisited.
 */
int GraphTools::findMinWeight(Graph& graph)
{
    /* Your code here! */
    //return -1;
    vector<Vertex> allVertices=graph.getVertices();
    vector<Edge> allEdges=graph.getEdges();
    //setting everything to unexplored for now
    makeUnexplored(graph, allVertices, allEdges);
    queue<Vertex> tempQueue;
    Vertex start=graph.getStartingVertex();
    int minWeight=0;
    graph.setVertexLabel(start, "VISITED");
    tempQueue.push(start);
    Vertex min1, min2; //for the two vertices that's going to contain the minimum edge
    while(tempQueue.empty()==false){
        Vertex u=tempQueue.front();
        tempQueue.pop();
        vector<Vertex> neighbors=graph.getAdjacent(u);
        for(unsigned long i=0; i<neighbors.size(); i++){
            Vertex v=neighbors[i]; //v would be the potentially unexplored one
            if(graph.getVertexLabel(v)=="UNEXPLORED"){
                graph.setVertexLabel(v, "VISITED");
                graph.setEdgeLabel(u, v, "DISCOVERY");
                tempQueue.push(v);
            }
            else if(graph.getEdgeLabel(u, v)=="UNEXPLORED"){
                graph.setEdgeLabel(u, v, "CROSS");
            }
            if(graph.getEdgeWeight(u, v)<minWeight||minWeight==0){
                min1=u;
                min2=v;
                minWeight=graph.getEdgeWeight(u,v);
            }
        }
    }
//by now should have minWeight and which vertices the edge is betweeen
    graph.setEdgeLabel(min1,min2,"MIN");

    return minWeight;
}
void GraphTools::makeUnexplored(Graph&graph, vector<Vertex> &allVertices, vector<Edge> &allEdges){
    for(unsigned long i=0; i<allVertices.size(); i++){
        graph.setVertexLabel(allVertices[i],"UNEXPLORED");
        vector<Vertex> neighborVertices=graph.getAdjacent(allVertices[i]);
        for(unsigned long j=0; j<neighborVertices.size(); j++){
            graph.setEdgeLabel(allVertices[i],neighborVertices[j],"UNEXPLORED");
        }
    }
}

/**
 * Returns the shortest distance (in edges) between the Vertices
 *  start and end.
 * THIS FUNCTION IS GRADED.
 *
 * @param graph - the graph to search
 * @param start - the vertex to start the search from
 * @param end - the vertex to find a path to
 * @return the minimum number of edges between start and end
 *
 * @todo Label each edge "MINPATH" if it is part of the minimum path
 *
 * @note Remember this is the shortest path in terms of edges,
 *  not edge weights.
 * @note Again, you may use the STL stack and queue.
 * @note You may also use the STL's unordered_map, but it is possible
 *  to solve this problem without it.
 *
 * @hint In order to draw (and correctly count) the edges between two
 *  vertices, you'll have to remember each vertex's parent somehow.
 */
int GraphTools::findShortestPath(Graph& graph, Vertex start, Vertex end)
{
    /* Your code here! */
    //return -1;
    vector<Vertex> allVertices=graph.getVertices();
    vector<Edge> allEdges=graph.getEdges();
    //setting everything to unexplored for now
    makeUnexplored(graph, allVertices, allEdges);
    queue<Vertex> tempQueue;
    tempQueue.push(start);
    unordered_map<Vertex, Vertex> vertexMap;
    while(tempQueue.empty()==false){
        Vertex u=tempQueue.front();
        tempQueue.pop();
        vector<Vertex> neighbors=graph.getAdjacent(u);
        for(unsigned long i=0; i<neighbors.size(); i++){
            Vertex v=neighbors[i]; //v would be the potentially unexplored one
            if(graph.getVertexLabel(v)=="UNEXPLORED"){
                graph.setVertexLabel(v, "VISITED");
                graph.setEdgeLabel(u, v, "DISCOVERY");
                tempQueue.push(v);
                vertexMap[v]=u;
            }
            else if(graph.getEdgeLabel(u, v)=="UNEXPLORED"){
                graph.setEdgeLabel(u, v, "CROSS");
            }
        }
    }
    int c=0;
    while(start!=end){
        graph.setEdgeLabel(end, vertexMap[end], "MINPATH");
        end=vertexMap[end];
        c++;
    }
    return c;
}

/**
 * Finds a minimal spanning tree on a graph.
 * THIS FUNCTION IS GRADED.
 *
 * @param graph - the graph to find the MST of
 *
 * @todo Label the edges of a minimal spanning tree as "MST"
 *  in the graph. They will appear blue when graph.savePNG() is called.
 *
 * @note Use your disjoint sets class from MP 7.1 to help you with
 *  Kruskal's algorithm. Copy the files into the libdsets folder.
 * @note You may call std::sort instead of creating a priority queue.
 */
void GraphTools::findMST(Graph& graph)
{
    /* Your code here! */
    //Get a list of all edges in the graph and sort them by increasing weight.
    vector<Edge> allEdges=graph.getEdges();
    sort(allEdges.begin(), allEdges.end());
    //Create a disjoint sets structure where each vertex is represented by a set.
    DisjointSets sets;
    vector<Vertex> allVertices=graph.getVertices();
    sets.addelements(allVertices.size());
    //traversing
    for(unsigned int i = 0; i < allEdges.size(); i++){
        Vertex u=allEdges[i].dest;
        Vertex v=allEdges[i].source;
        if(sets.find(u)!=sets.find(v)){
            graph.setEdgeLabel(u, v, "MST");
            sets.setunion(u,v);
        }
    }
}