#include "Graph.h"
#include <iostream>
using namespace std;
#include <vector>
using namespace std;
#ifndef GENERAL_GRAPHALG_H
#define GENERAL_GRAPHALG_H
enum Color{
  White,
  Gray,
  Black
};
template <class T>
struct queueElm{
  queueElm *next, *prev;
  T inf;
  queueElm(T t,queueElm* prev, queueElm* next){inf=t;queueElm::next=next;queueElm::prev=prev;}
};

/**
 * The queue class implements a queue by a stack 
 */
template <class T> 
class Queue{
public:
  Queue(){_first = _last = 0x0;}
  void enqueue(T t){
    queueElm<T>* tmp = new queueElm<T>(t,_last,(queueElm<T>*)0x0);
    if(_first == 0x0) {_first = tmp;_last = tmp;}
    else{_last->next = tmp;_last=tmp;} 
  }

  T& dequeue(T& ret){
    queueElm<T>* tmpq = _first;
    _first= _first->next;
    ret = tmpq->inf;
    delete tmpq;
    return ret;
  }

  bool isEmpty(){
    if(_first == 0x0) return true;
    else return false;
  }
  
private:
  queueElm<T> *_first;
  queueElm<T> *_last;
}; 

/**
 * The class includes varius graph algorithms. These are static methods in the class
 */
class GraphAlg{
public:
  /**
   * Breadth first search both d and pi should be initialized by caller
   * @param G the graph 
   * @param s the source Vertex 
   * @param d the distance vector 
   * @param pi the predecessor vector 
   */
  static void BFS(Sparse_Graph& G, const Vertex& s, int*& d,Vertex*& pi){
    //cout << "BFS kaldt " << endl;
    Color* color=new Color[G.getNumNodes()];
    for(Vertex v=G.first_node();v!=NIL;v=G.next_node()){
      color[v.id] = White;d[v.id]=-1;pi[v.id]=NIL;
    }
    color[s.id]=Gray;d[s.id]=0;pi[s.id] = NIL;
    Queue<Vertex> Q;
    Q.enqueue(s);
    //G.print();
    while(!(Q.isEmpty())){
      Vertex u;
      Q.dequeue(u);

      for(Vertex v = G.first_adj_node(u);v!=NIL;v=G.next_adj_node()){
	if(color[v.id] == White){
	  color[v.id] = Gray;
	  d[v.id] = d[u.id] + 1;
	  pi[v.id] = u;	  

	  Q.enqueue(v);
	}	
      }
      color[u.id] = Black;
    }
    
    delete color;
  }
  
  /**
   * The minimum s-t cut will find to sets S,T where the source is in S and the taget is in T. 
   * This algorithme is based on the Edmond-Karp algoritm for Maximum flow, but does not cumpute the flow, just the argumenting path  
   * in the residual network . When no more argumenting path exist we have, for each node v if a argumenting path s,v is found then it's in S else it's in T. 
   * @param G the graph with the capacity as edge information 
   * @todo Resolve hack when building S,T. Waiting for solution in Graph scan. 
   * @param s the source vertex
   * @param t the taget vertex
   * @param S the set of nodes with s 
   * @param T the set of nodes with t
   * @param minval the minimum cut
   */
  static void MinimumSTCut(Sparse_Graph& G, Vertex& s, Vertex& t,vector<Vertex>& S, vector<Vertex>& T, double& minval){

    Sparse_Graph res_net(G);

    int* d = new int[res_net.getNumNodes()];
    Vertex* pi = new Vertex[res_net.getNumNodes()];
    Vertex curr, predecessor;
    double mincap;
    while(1){
      //Calculate argumenting path 
      BFS(res_net,s,d,pi);
      if(pi[t.id] == NIL){break;}
      
      //Find the minimum capacity of argumenting path 
      curr = t;
      predecessor = pi[t.id];
      mincap = res_net.getd(predecessor,curr);  
      while(curr != s){

	if(res_net.getd(predecessor, curr) < mincap) mincap = res_net.getd(predecessor,curr);
	curr = predecessor;predecessor=pi[curr.id];
      }

      //Update the residual network
      curr = t;
      predecessor = pi[t.id];
      while(curr != s){
	if(res_net.getd(predecessor,curr) - mincap < 10e-05) 
	  res_net.deleteEdge(predecessor,curr); 
	else 
	  res_net.setd(predecessor,curr,res_net.getd(predecessor,curr)-mincap);
	res_net.setd(curr,predecessor,res_net.getd(curr,predecessor)+mincap);
	curr = predecessor;predecessor=pi[curr.id];
      }
    }
    //Calculate sets 
    //Hack until Graph support more node scan 

    for(Vertex v=G.first_node();v!=NIL;v=G.next_node()){
      if(v==s){S.push_back(v);continue;}
      if(v==t){T.push_back(v);continue;}
      if(pi[v.id] == NIL) T.push_back(v);
      else S.push_back(v);
    }
    //Calculate minimum s-t cut, Hack since stl vector is not sorted why ?

    minval = 0;    
    for(size_t i=0;i<S.size();i++)
      for(size_t j=0;j<T.size();j++)
	if(G.getd(S[i],T[j]) > 10e-05)
	  minval += G.getd(S[i],T[j]);
    
    delete pi;
    delete d;
  }
};
#endif