# HG changeset patch
# User alpar
# Date 1171302876 0
# Node ID 72c7075ad5ba219f441f67dfa0653b326daab34a
# Parent  97a5cd10ca16b699d03e63b5103f53cc2a9aa817
Lagrange relaxation based algorithm for the delay constrained least cost
path problem.

diff -r 97a5cd10ca16 -r 72c7075ad5ba demo/Makefile.am
--- a/demo/Makefile.am	Mon Feb 12 10:27:03 2007 +0000
+++ b/demo/Makefile.am	Mon Feb 12 17:54:36 2007 +0000
@@ -5,6 +5,7 @@
 if WANT_DEMO
 
 noinst_PROGRAMS += \
+	demo/csp_demo \
 	demo/dim_to_dot \
 	demo/dijkstra_demo \
 	demo/reader_writer_demo \
@@ -36,6 +37,8 @@
 
 endif WANT_DEMO
 
+demo_csp_demo_SOURCES = demo/csp_demo.cc
+
 demo_dim_to_dot_SOURCES = demo/dim_to_dot.cc
 
 demo_dijkstra_demo_SOURCES = demo/dijkstra_demo.cc
diff -r 97a5cd10ca16 -r 72c7075ad5ba demo/csp_demo.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/demo/csp_demo.cc	Mon Feb 12 17:54:36 2007 +0000
@@ -0,0 +1,84 @@
+/* -*- C++ -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2003-2006
+ * 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.
+ *
+ */
+
+///\ingroup demos
+///\file
+///\brief Demonstrating the usage of LEMON's Dijkstra algorithm
+///
+/// Dijkstra's algorithm computes shortest paths between two nodes in
+/// a graph with edge lengths. Here we only show some of the
+/// facilities supplied by our implementation: for the detailed
+/// documentation of the LEMON Dijkstra class read \ref lemon::Dijkstra "this".
+///
+/// \include dijkstra_demo.cc
+
+#include <iostream>
+#include <lemon/list_graph.h>
+#include <lemon/csp.h>
+#include <lemon/random.h>
+
+
+using namespace lemon;
+
+
+int main (int, char*[])
+{
+
+    typedef ListGraph Graph;
+    typedef Graph::Node Node;
+    typedef Graph::Edge Edge;
+    typedef Graph::EdgeIt EdgeIt;
+    typedef Graph::EdgeMap<double> LengthMap;
+
+    Graph g;
+
+    const int N=100;
+    const int M=20000;
+    std::vector<Node> nodes;
+    std::vector<Edge> edges;
+    
+    for(int i=0;i<N;i++) nodes.push_back(g.addNode());
+
+    for(int i=0;i<M;i++)
+      edges.push_back(g.addEdge(nodes[rnd[N]],nodes[rnd[N]]));
+    
+    LengthMap cost(g);
+    LengthMap delay(g);
+    for(EdgeIt e(g);e!=INVALID;++e)
+      {
+	cost[e]=0.01+rnd(.99);
+	delay[e]=0.01+rnd(.99);
+      }
+    
+    ConstrainedShortestPath<Graph,LengthMap,LengthMap> csp(g,cost,delay);
+    for(double d=0;d<2;d+=.01)
+      {
+	double lo_bo;
+	std::cout << d << ": ";
+	SimplePath<Graph> r = csp.larac(nodes[0],nodes[1],d,lo_bo);
+	if(r.empty()) std::cout << "INFEASIBLE\n";
+	else std::cout << "delay: " << csp.delay(r)
+		       << " cost: " << csp.cost(r)
+		       << " (lb: " << lo_bo
+		       << " gap: " << csp.cost(r)-lo_bo
+		       << " , " << (csp.cost(r)-lo_bo)/csp.cost(r)*100
+		       << "%)" << std::endl;
+      }
+    			
+    return 0;
+}
diff -r 97a5cd10ca16 -r 72c7075ad5ba lemon/Makefile.am
--- a/lemon/Makefile.am	Mon Feb 12 10:27:03 2007 +0000
+++ b/lemon/Makefile.am	Mon Feb 12 17:54:36 2007 +0000
@@ -44,6 +44,7 @@
 	lemon/config.h \
 	lemon/concept_check.h \
 	lemon/counter.h \
+	lemon/csp.h \
 	lemon/dag_shortest_path.h \
 	lemon/dfs.h \
 	lemon/dijkstra.h \
diff -r 97a5cd10ca16 -r 72c7075ad5ba lemon/csp.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/csp.h	Mon Feb 12 17:54:36 2007 +0000
@@ -0,0 +1,172 @@
+/* -*- C++ -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2003-2006
+ * 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 flowalgs
+///\file
+///\brief Algorithm for the Resource Constrained Shortest Path problem.
+///
+///
+///\todo dijkstraZero() solution should be revised.
+
+#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 {
+  
+  ///Algorithms for the Resource Constrained Shortest Path Problem
+  
+  ///\e
+  ///
+  template<class Graph,
+	   class CM=typename Graph:: template EdgeMap<double>,
+	   class DM=CM>
+  class ConstrainedShortestPath 
+  {
+  public:
+    
+    GRAPH_TYPEDEFS(typename Graph);
+    
+    typedef SimplePath<Graph> Path;
+    
+    Graph &_g;
+    Tolerance<double> tol;
+
+    CM &_cost;
+    DM &_delay;
+
+    class CoMap 
+    {
+      CM &_cost;
+      DM &_delay;
+      double _lambda;
+    public:
+      typedef typename CM::Key Key;
+      typedef double Value;
+      CoMap(CM &c,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];
+      }
+    } _co_map;
+    
+    
+    Dijkstra<Graph, CoMap> _dij;
+    ///\e
+    
+    ///\e
+    ///
+    ConstrainedShortestPath(Graph &g, CM &cost, DM &delay)
+      : _g(g), _cost(cost), _delay(delay),
+	_co_map(cost,delay), _dij(_g,_co_map) {}
+    
+
+    ///Compute the cost of a path
+    double cost(const Path &p) 
+    {
+      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) 
+    {
+      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
+    ///\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) 
+    {
+      NoCounter cnt("LARAC iterations: ");
+      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);
+	cnt++;
+	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);
+	cnt++;
+	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);
+	cnt++;
+	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