/* -*- C++ -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library

 *

 * Copyright (C) 2003-2007

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#ifndef LEMON_CSP_H

#define LEMON_CSP_H

///\ingroup approx

///\file

///\brief Algorithm for the Resource Constrained Shortest Path problem.

///

#include <lemon/list_graph.h>

#include <lemon/graph_utils.h>

#include <lemon/error.h>

#include <lemon/maps.h>

#include <lemon/tolerance.h>

#include <lemon/dijkstra.h>

#include <lemon/path.h>

#include <lemon/counter.h>

namespace lemon {

  ///\ingroup approx

  ///

  ///\brief Algorithms for the Resource Constrained Shortest Path Problem

  ///

  ///The Resource Constrained Shortest (Least Cost) Path problem is the

  ///following. We are given a directed graph with two additive weightings

  ///on the edges, referred as \e cost and \e delay. In addition,

  ///a source and a destination node \e s and \e t and a delay

  ///constraint \e D is given. A path \e p is called \e feasible

  ///if <em>delay(p)\<=D</em>. Then, the task is to find the least cost

  ///feasible path.

  ///

  template<class Graph,

	   class CM=typename Graph:: template EdgeMap<double>,

	   class DM=CM>

  class ConstrainedShortestPath 

  {

  public:

    GRAPH_TYPEDEFS(typename Graph);

    typedef SimplePath<Graph> Path;

  private:

    const Graph &_g;

    Tolerance<double> tol;

    const CM &_cost;

    const DM &_delay;

    class CoMap 

    {

      const CM &_cost;

      const DM &_delay;

      double _lambda;

    public:

      typedef typename CM::Key Key;

      typedef double Value;

      CoMap(const CM &c, const DM &d) :_cost(c), _delay(d), _lambda(0) {}

      double lambda() const { return _lambda; }

      void lambda(double l)  { _lambda=l; }

      Value operator[](Key &e) const 

      {

	return _cost[e]+_lambda*_delay[e];

      }

    };

    CoMap _co_map;

    Dijkstra<Graph, CoMap> _dij;

  public:

    /// \brief Constructor

    ///Constructor

    ///

    ConstrainedShortestPath(const Graph &g, const CM &ct, const DM &dl)

      : _g(g), _cost(ct), _delay(dl),

	_co_map(ct, dl), _dij(_g,_co_map) {}

    ///Compute the cost of a path

    double cost(const Path &p) const

    {

      double s=0;

      //      Path r;  

      for(typename Path::EdgeIt e(p);e!=INVALID;++e) s+=_cost[e];

      return s;

    }

    ///Compute the delay of a path

    double delay(const Path &p) const

    {

      double s=0;

      for(typename Path::EdgeIt e(p);e!=INVALID;++e) s+=_delay[e];

      return s;

    }

    ///Runs the LARAC algorithm

    ///This function runs a Lagrange relaxation based heuristic to find

    ///a delay constrained least cost path.

    ///\param s source node

    ///\param t target node

    ///\param delta upper bound on the delta

    ///\retval lo_bo a lower bound on the optimal solution

    ///\return the found path or an empty 

    Path larac(Node s, Node t, double delta, double &lo_bo) 

    {

      double lambda=0;

      double cp,cq,dp,dq,cr,dr;

      Path p;

      Path q;

      Path r;

      {

	Dijkstra<Graph,CM> dij(_g,_cost);

	dij.run(s,t);

	if(!dij.reached(t)) return Path();

	p=dij.path(t);

	cp=cost(p);

	dp=delay(p);

      }

      if(delay(p)<=delta) return p;

      {

	Dijkstra<Graph,DM> dij(_g,_delay);

	dij.run(s,t);

	q=dij.path(t);

	cq=cost(q);

	dq=delay(q);

      }

      if(delay(q)>delta) return Path();

      while (true) {

	lambda=(cp-cq)/(dq-dp);

	_co_map.lambda(lambda);

	_dij.run(s,t);

	r=_dij.path(t);

	cr=cost(r);

	dr=delay(r);

	if(!tol.less(cr+lambda*dr,cp+lambda*dp)) {

	  lo_bo=cq+lambda*(dq-delta);

	  return q;

	}

	else if(tol.less(dr,delta)) 

	  {

	    q=r;

	    cq=cr;

	    dq=dr;

	  }

	else if(tol.less(delta,dr))

	  {

	    p=r;

	    cp=cr;

	    dp=dr;

	  }

	else return r;

      }

    }

  };

} //END OF NAMESPACE LEMON

#endif