#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 "..\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 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;

    Component strongComp(graph& g);
  private:
    void Strong(graph& g, size_t);
    std::vector<size_t> num;
    std::vector<size_t> lowlink;
    LibUtils::SearchableStack<size_t> stack_;
    size_t visitNum;
    Component comp;
  };
  /*
   * 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.
   * 
   */
  //----< helper function for strong components >--------------

  template <typename V, typename E>
  void Algorithms<V,E>::Strong(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());
      comp.push_back(compElem);
    }
  }
  //----< returns strong components of graph g >---------------

  template <typename V, typename E>
  Algorithms<std::string, std::string>::Component
    Algorithms<V,E>::strongComp(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;
  }
}
#endif