#ifndef GRAPHALGORITHMS_H
#define GRAPHALGORITHMS_H
/////////////////////////////////////////////////////////////////
// GraphAlgorithms.h - Algorithms on graph structures          //
// ver 1.0                                                     //
// ----------------------------------------------------------- //
// copyright © Jim Fawcett, 2012                               //
// All rights granted provided that this notice is retained    //
// ----------------------------------------------------------- //
// Jim Fawcett, CST 4-187, Syracuse University, 315 443 3948   //
// Summer Projects, 2012                                       //
// Win7, Visual Studio 2010                                    //
/////////////////////////////////////////////////////////////////
/*
 * Package Operations:
 * -------------------
 * This package provides classes supporting algorithms on
 * directed graphs.  It provides the classes:
 * - strongComp:
 *   Find strong components of graph (mutual dependencies in
 *   a dependency graph.
 * And the functions:
 * - vertsWithNoParents
 *   Find all the top-level vertices, e.g., no parents, if they
 *   exist.
 * Package Plans:
 * --------------
 * - CondensedGraph:
 *   Builds graph of strong components (which is always acyclic)
 * - TopoSort:
 *   Executes topological sort on condensed graphs
 * - ExpandCondensedGraph
 *   Expands sorted condensed graph to a quasi-sorted graph
 *   of the original vertices
 * - Disconnected:
 *   Find disconnected components
 */
#include <vector>
#include <list>
#include <set>
#include "..\graph\Graph.h"
#include "..\LibUtils\LibUtils.h"

namespace DirectedGraph
{
  //-----------------------------------------------------------
  // vertsWithNoParents - find top vertices if any

  template <typename V, typename E>
  std::vector< Vertex<V,E> > vertsWithNoParents(Graph<V,E>& g)
  {
    typedef std::pair<int,E> Edge;

    std::vector<size_t> parentCount;
    Graph<V,E>::iterator iter = g.begin();
    while(iter != g.end())
    {
      parentCount.push_back(0);
      ++iter;
    }
    iter = g.begin();
    while(iter != g.end())
    {
      Vertex<V,E> v = *iter;
      for(size_t i=0; i<v.size(); ++i)
      {
        Edge e = v[i];
        parentCount[e.first]++;
      }
      ++iter;
    }
    std::vector<Vertex<V,E>> noParents;
    for(size_t j=0; j<g.size(); ++j)
      if(parentCount[j] == 0)
        noParents.push_back(g[j]);
    return noParents;
  }

  /////////////////////////////////////////////////////////////
  // class Component
  //
  // - Mutually dependent vertices of a directed graph belong to
  //   sets called strong components.  
  // - By convention a vertex that has no mutually dependent
  //   partners is said to be a strong component of size 1.  
  // - If a vertex is mutually dependent on one or more other 
  //   vertices its strong component is the set containing all
  //   such vertices.
  // - The Components class is a collection of strong component
  //   representations, each of which holds the indices of each
  //   vertex in a strong component of the graph, e.g., the index
  //   of the vertex in the graph vertices collection.
  // - An instance of Components is filled and returned by
  //   Algorithms<V,E>::strongComp(graph& g);

  class Components
  {
  public:
    typedef std::vector<std::vector<size_t>> Comps;
    Components() {}
    Components(Comps& comps) : comps_(comps) {}
    std::vector<size_t>& operator[](size_t i) { return comps_[i]; }
    size_t size() { return comps_.size(); }
    size_t component(size_t index);
    void push_back(std::vector<size_t>& vec) { comps_.push_back(vec); }
  private:
    Comps comps_;
  };
  //----< find strong component of g[index] >------------------

  size_t Components::component(size_t index)
  {
    for(size_t i=0; i<comps_.size(); ++i)
      for(size_t j=0; j<comps_[i].size(); ++j)
        if(comps_[i][j] == index)
          return i;
    return comps_.size();
  }
  /////////////////////////////////////////////////////////////
  // class Algorithms - finds strong components

  template <typename V, typename E>
  class Algorithms
  {
  public:
    //typename typedef std::vector<std::vector<size_t>> Component;
    typedef Graph<V,E> graph;
    typedef Vertex<V,E> vertex;

    Components strongComp(const graph& g);
    Components createCondensedGraph(const graph& g, graph& condGraph);
    std::vector<size_t> topoSort(graph& g);
  private:
    void Strong(const graph& g, size_t);
    void indexWalk(graph& g, size_t start);
    std::vector<size_t> num;
    std::vector<size_t> lowlink;
    LibUtils::SearchableStack<size_t> stack_;
    size_t visitNum;
    Components comp;
    std::set<size_t> targetVertices_;
    std::vector<size_t> orderedVertices_;
  };
  /*
   * A strong componet is a set of mutually dependent vertices where
   * you interpret a directed edge as a dependency relationship.
   *
   * The implemented here is based on an algorithm published by
   * D. Sleator, CMU which was based on an original by Tarjan.
   * http://www.cs.cmu.edu/afs/cs/academic/class/15451-s06/www/lectures/DFS-strong-components.pdf
   */
  //----< helper function for strong components >--------------

  template <typename V, typename E>
  void Algorithms<V,E>::Strong(const graph& g, size_t v)
  {
    ++visitNum;
    num[v-1] = visitNum;
    lowlink[v-1] = visitNum;
    stack_.push(v);
    for(size_t i=0; i<g[v-1].size(); ++i)
    {
      size_t w = g[v-1][i].first + 1;  // w is child vertex index counting from 1
      if(num[w-1] == 0)
      {
        Strong(g,w);
        lowlink[v-1] = std::min(lowlink[v-1], lowlink[w-1]);
      }
      else
      {
        if(num[w-1] < num[v-1])
          if(stack_.contains(w))
            lowlink[v-1] = std::min(lowlink[v-1], num[w-1]);
      }
    }
    if(lowlink[v-1] == num[v-1])
    {
      std::vector<size_t> compElem;
      size_t top = stack_.top();
      size_t cmp = num[v-1];
      while(stack_.size() > 0 && num[stack_.top()-1] >= num[v-1])
        compElem.push_back(stack_.pop()-1);
      comp.push_back(compElem);
    }
  }
  //----< returns strong components of graph g >---------------

  template <typename V, typename E>
  Components Algorithms<V,E>::strongComp(const graph& g)
  {
    std::vector<size_t> compElem;
    visitNum = 0;
    for(size_t i=0; i<g.size(); ++i)
    {
      num.push_back(0);
      lowlink.push_back(0);
    }
    for(size_t i=0; i<g.size(); ++i)
    {
      if(num[i] == 0)
      {
        Strong(g, i+1);
      }
    }
    return comp;
  }

  template <typename V, typename E>
  Components Algorithms<V,E>::createCondensedGraph(const graph& g, graph& condGraph)
  {
    Components comp = strongComp(g);

    //insert strong components as vertices
    for(size_t i=0; i<comp.size(); ++i)
    {
      // Each strong component is a vertex of the condensed graph
      size_t index = comp[i][0];
      size_t id = g[index].id();
      std::string value = "sc" + LibUtils::toString(i) + "-v" + LibUtils::toString(id);
      Vertex<V,E> v(id, value);
      condGraph.addVertex(v);
    }
    // to each vertex add an edge going to strong component of
    // every child of every vertex in strong component, eliminating
    // duplicates and edges that stay in strong component
    for(size_t i=0; i<comp.size(); ++i)  // for each strong component
    {
      size_t parentStrongComp = i;
      targetVertices_.clear();
      for(size_t j=0; j<comp[i].size(); ++j)  // for each vertex in component
      {
        // find strong components of child vertices
        size_t vertexIndex = comp[i][j];
        for(size_t k=0; k<g[vertexIndex].size(); ++k)  // for each child in vertex
        {
          size_t childVertexIndex = g[vertexIndex][k].first;
          size_t childStrongComp = comp.component(childVertexIndex);
          if(childStrongComp != parentStrongComp && targetVertices_.count(childStrongComp) == 0)
          {
            targetVertices_.insert(childStrongComp);
            condGraph.addEdge("cedge",condGraph[parentStrongComp],condGraph[childStrongComp]);
          }
        }
      }
    }
    return comp;
  }

  template <typename V, typename E>
  void Algorithms<V,E>::indexWalk(Graph<V,E>& g, size_t index)
  {
    g[index].visited() = true;
    for(size_t i=0; i<g[index].size(); ++i)
      if(!g[index].visited())
        indexWalk(g, g[index][i].first);
    orderedVertices_.push_back(index);
  }
  template <typename V, typename E>
  std::vector<size_t> Algorithms<V,E>::topoSort(Graph<V,E>& g)
  {
    g.resetVisited();
    orderedVertices_.clear();
    for(size_t i=0; i<g.size(); ++i)
      indexWalk(g, i);
    return orderedVertices_;
  }
}
#endif