/**
 * @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! */
    std::vector<Vertex> v=graph.getVertices();
    std::vector<Edge> e=graph.getEdges();
    for(unsigned int i=0;i<v.size();i++)
      graph.setVertexLabel(v[i],"UNEXPLORED");
    for(unsigned int i=0;i<e.size();i++)
      graph.setEdgeLabel(e[i].source,e[i].dest,"UNEXPLORED");
    queue<Vertex> bfs;
    bfs.push(v[0]);
    graph.setVertexLabel(v[0],"DONE");
    Vertex st =graph.getAdjacent(v[v.size()-1])[0];
    int w = graph.getEdgeWeight(v[v.size()-1],st);
    Vertex s= v[v.size()-1];
    Vertex d = st;
    while(bfs.empty()==false)
    {
      Vertex cur = bfs.front();
      std::vector<Vertex> cu=graph.getAdjacent(cur);
      for(unsigned int i=0;i<cu.size();i++)
      {

        if(graph.getVertexLabel(cu[i])=="UNEXPLORED")
        {
              bfs.push(cu[i]);
              graph.setVertexLabel(cu[i],"DONE");
              graph.setEdgeLabel(cur,cu[i],"FOUND");
         }
         else if(graph.getEdgeLabel(cur,cu[i])=="UNEXPLORED")
         {
              graph.setEdgeLabel(cur,cu[i],"CROSSED");
         }
         if(graph.getEdgeWeight(cur,cu[i])<w)
         {
           w=graph.getEdgeWeight(cur,cu[i]);
           s=cur;
           d=cu[i];
         }
      }
      bfs.pop();
    }
    graph.setEdgeLabel(s,d,"MIN");
    return w;
}

/**
 * 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! */
    std::vector<Vertex> v=graph.getVertices();
    std::vector<Edge> e=graph.getEdges();
    for(unsigned int i=0;i<v.size();i++)
      graph.setVertexLabel(v[i],"UNEXPLORED");
    for(unsigned int i=0;i<e.size();i++)
      graph.setEdgeLabel(e[i].source,e[i].dest,"UNEXPLORED");
    queue<Vertex> bfs;
    bfs.push(start);
    graph.setVertexLabel(start,"DONE");
    unordered_map<Vertex,Vertex> map;
    while(bfs.empty()==false)
    {
      Vertex cur = bfs.front();
      std::vector<Vertex> cu=graph.getAdjacent(cur);
      for(unsigned int i=0;i<cu.size();i++)
      {
        if(graph.getVertexLabel(cu[i])=="UNEXPLORED")
        {
          bfs.push(cu[i]);
          graph.setVertexLabel(cu[i],"DONE");
          graph.setEdgeLabel(cur,cu[i],"FOUND");
          pair<Vertex,Vertex> p (cu[i],cur);
          map.insert(p);

        }
        else if(graph.getEdgeLabel(cur,cu[i])=="UNEXPLORED")
          graph.setEdgeLabel(cur,cu[i],"CROSSED");
      }
      bfs.pop();
    }
    int ret=0;
    while(end!=start)
    {
      graph.setEdgeLabel(end,map[end],"MINPATH");
      end=map[end];
      ret=ret+1;
    }
    return ret;
}

/**
 * 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! */
    std::vector<Vertex> v=graph.getVertices();
    DisjointSets ds;
    ds.addelements(v.size());
    std::vector<Edge> e=graph.getEdges();
    std::sort(e.begin(),e.end(),so);
    unsigned int j=0;
    for(unsigned int i=0;i<e.size();i++)
    {
      if(!(j<(v.size()-1)))
        break;
      if(ds.find(e[i].source)!=ds.find(e[i].dest))
      {
        ds.setunion(e[i].source,e[i].dest);
        graph.setEdgeLabel(e[i].source,e[i].dest,"MST");
        j++;
      }
    }
}
bool GraphTools::so(Edge a, Edge b)
{
  return(a.weight<b.weight);
}