// -*- c++ -*-
#ifndef HUGO_SUURBALLE_H
#define HUGO_SUURBALLE_H

///\file
///\brief Suurballe algorithm.

#include <iostream>
#include <dijkstra.h>
#include <graph_wrapper.h>
namespace hugo {


///\brief Implementation of Suurballe's algorithm
///
/// The class \ref hugo::Suurballe "Suurballe" implements
/// Suurballe's algorithm which seeks for k edge-disjoint paths
/// from a given source node to a given target node in an
/// edge-weighted directed graph having minimal total cost.
/// 
/// 

  template <typename Graph, typename T, 
    typename LengthMap=typename Graph::EdgeMap<T> >
  class Suurballe {


    //Writing maps 
    class ConstMap {
    public :
      typedef int ValueType;
      typedef typename Graph::Edge KeyType;

      int operator[](typename Graph::Edge e) const { 
	return 1;
      } 
    };
    /*
    //    template <typename Graph, typename T>
    class ModLengthMap {   
      typedef typename Graph::EdgeMap<T> EdgeMap;
      typedef typename Graph::NodeMap<T> NodeMap;

      const EdgeMap &ol;   
      const NodeMap &pot;     
    public :
      typedef typename EdgeMap::KeyType KeyType;
      typedef typename EdgeMap::ValueType ValueType;

      double operator[](typename Graph::EdgeIt e) const {     
	return 10;//ol.get(e)-pot.get(v)-pot.get(u);   
      }     

      ModLengthMap(const EdgeMap &o,
		   const NodeMap &p) : 
	ol(o), pot(p){}; 
    };
    */


    typedef typename Graph::Node Node;
    typedef typename Graph::NodeIt NodeIt;
    typedef typename Graph::Edge Edge;
    typedef typename Graph::OutEdgeIt OutEdgeIt;
    typedef TrivGraphWrapper<const Graph> TrivGraphType;
    typedef ResGraphWrapper<TrivGraphType,int,typename Graph::EdgeMap<int>,
      ConstMap> ResGraphType;

    const Graph& G;
    const LengthMap& length;


    //auxiliary variables
    
    typename Graph::EdgeMap<int> reversed; 
    typename Graph::NodeMap<T> dijkstra_dist; 
    
  public :
    

    Suurballe(Graph& _G, LengthMap& _length) : G(_G), 
      length(_length), reversed(_G), dijkstra_dist(_G){ }

    ///Runs Suurballe's algorithm
    
    ///Runs Suurballe's algorithm
    ///Returns true iff there are k edge-disjoint paths from s to t
    bool run(Node s, Node t, int k) {

      LengthMap mod_length_c = length;
      ConstMap const1map;
      //ResGraphWrapper< Graph,T,typename Graph::EdgeMap<int>, ConstMap> 
      TrivGraphType ize(G);
      ResGraphType res_graph(ize, reversed, const1map);
      //ModLengthMap modified_length(length, dijkstra_dist);
      //Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, modified_length);
      //ResGraphWrapper< Graph,T,typename Graph::EdgeMap<int>, ConstMap>
      Dijkstra<ResGraphType, LengthMap> dijkstra(res_graph, mod_length_c);
      
      for (int i=0; i<k; ++i){
	dijkstra.run(s);
	if (!dijkstra.reached(t)){
	  //There is no k path from s to t
	  return false;
	};
	{
	  //We have to copy the potential
	  typename ResGraphType::EdgeIt e;
	  for ( res_graph.first(e) ; res_graph.valid(e) ; res_graph.next(e) ) {
	    //dijkstra_dist[e] = dijkstra.distMap()[e];
	    mod_length_c[Edge(e)] = mod_length_c[Edge(e)] - 
	      dijkstra.distMap()[res_graph.head(e)] +  
	      dijkstra.distMap()[res_graph.tail(e)];
	  }
	}
	
	//Reversing the sortest path
	Node n=t;
	Edge e;
	while (n!=s){
	  e = dijkstra.pred(n);
	  n = dijkstra.predNode(n);
	  reversed[e] = 1-reversed[e];
	}

	  
      }
      return true;
    }
           
      



  };//class Suurballe




} //namespace hugo

#endif //HUGO_SUURBALLE_H