// -*- 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