1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/csp.h Mon Feb 12 17:54:36 2007 +0000
1.3 @@ -0,0 +1,172 @@
1.4 +/* -*- C++ -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library
1.7 + *
1.8 + * Copyright (C) 2003-2006
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +#ifndef LEMON_CSP_H
1.23 +#define LEMON_CSP_H
1.24 +
1.25 +///\ingroup flowalgs
1.26 +///\file
1.27 +///\brief Algorithm for the Resource Constrained Shortest Path problem.
1.28 +///
1.29 +///
1.30 +///\todo dijkstraZero() solution should be revised.
1.31 +
1.32 +#include <lemon/list_graph.h>
1.33 +#include <lemon/graph_utils.h>
1.34 +#include <lemon/error.h>
1.35 +#include <lemon/maps.h>
1.36 +#include <lemon/tolerance.h>
1.37 +#include <lemon/dijkstra.h>
1.38 +#include <lemon/path.h>
1.39 +#include <lemon/counter.h>
1.40 +namespace lemon {
1.41 +
1.42 + ///Algorithms for the Resource Constrained Shortest Path Problem
1.43 +
1.44 + ///\e
1.45 + ///
1.46 + template<class Graph,
1.47 + class CM=typename Graph:: template EdgeMap<double>,
1.48 + class DM=CM>
1.49 + class ConstrainedShortestPath
1.50 + {
1.51 + public:
1.52 +
1.53 + GRAPH_TYPEDEFS(typename Graph);
1.54 +
1.55 + typedef SimplePath<Graph> Path;
1.56 +
1.57 + Graph &_g;
1.58 + Tolerance<double> tol;
1.59 +
1.60 + CM &_cost;
1.61 + DM &_delay;
1.62 +
1.63 + class CoMap
1.64 + {
1.65 + CM &_cost;
1.66 + DM &_delay;
1.67 + double _lambda;
1.68 + public:
1.69 + typedef typename CM::Key Key;
1.70 + typedef double Value;
1.71 + CoMap(CM &c,DM &d) :_cost(c), _delay(d), _lambda(0) {}
1.72 + double lambda() const { return _lambda; }
1.73 + void lambda(double l) { _lambda=l; }
1.74 + Value operator[](Key &e) const
1.75 + {
1.76 + return _cost[e]+_lambda*_delay[e];
1.77 + }
1.78 + } _co_map;
1.79 +
1.80 +
1.81 + Dijkstra<Graph, CoMap> _dij;
1.82 + ///\e
1.83 +
1.84 + ///\e
1.85 + ///
1.86 + ConstrainedShortestPath(Graph &g, CM &cost, DM &delay)
1.87 + : _g(g), _cost(cost), _delay(delay),
1.88 + _co_map(cost,delay), _dij(_g,_co_map) {}
1.89 +
1.90 +
1.91 + ///Compute the cost of a path
1.92 + double cost(const Path &p)
1.93 + {
1.94 + double s=0;
1.95 + // Path r;
1.96 + for(typename Path::EdgeIt e(p);e!=INVALID;++e) s+=_cost[e];
1.97 + return s;
1.98 + }
1.99 +
1.100 + ///Compute the delay of a path
1.101 + double delay(const Path &p)
1.102 + {
1.103 + double s=0;
1.104 + for(typename Path::EdgeIt e(p);e!=INVALID;++e) s+=_delay[e];
1.105 + return s;
1.106 + }
1.107 +
1.108 + ///Runs the LARAC algorithm
1.109 +
1.110 + ///This function runs a Lagrange relaxation based heuristic to find
1.111 + ///a delay constrained least cost path.
1.112 + ///\param s source node
1.113 + ///\param t target node
1.114 + ///\retval lo_bo a lower bound on the optimal solution
1.115 + ///\return the found path or an empty
1.116 + Path larac(Node s, Node t, double delta, double &lo_bo)
1.117 + {
1.118 + NoCounter cnt("LARAC iterations: ");
1.119 + double lambda=0;
1.120 + double cp,cq,dp,dq,cr,dr;
1.121 + Path p;
1.122 + Path q;
1.123 + Path r;
1.124 + {
1.125 + Dijkstra<Graph,CM> dij(_g,_cost);
1.126 + dij.run(s,t);
1.127 + cnt++;
1.128 + if(!dij.reached(t)) return Path();
1.129 + p=dij.path(t);
1.130 + cp=cost(p);
1.131 + dp=delay(p);
1.132 + }
1.133 + if(delay(p)<=delta) return p;
1.134 + {
1.135 + Dijkstra<Graph,DM> dij(_g,_delay);
1.136 + dij.run(s,t);
1.137 + cnt++;
1.138 + q=dij.path(t);
1.139 + cq=cost(q);
1.140 + dq=delay(q);
1.141 + }
1.142 + if(delay(q)>delta) return Path();
1.143 + while (true) {
1.144 + lambda=(cp-cq)/(dq-dp);
1.145 + _co_map.lambda(lambda);
1.146 + _dij.run(s,t);
1.147 + cnt++;
1.148 + r=_dij.path(t);
1.149 + cr=cost(r);
1.150 + dr=delay(r);
1.151 + if(!tol.less(cr+lambda*dr,cp+lambda*dp)) {
1.152 + lo_bo=cq+lambda*(dq-delta);
1.153 + return q;
1.154 + }
1.155 + else if(tol.less(dr,delta))
1.156 + {
1.157 + q=r;
1.158 + cq=cr;
1.159 + dq=dr;
1.160 + }
1.161 + else if(tol.less(delta,dr))
1.162 + {
1.163 + p=r;
1.164 + cp=cr;
1.165 + dp=dr;
1.166 + }
1.167 + else return r;
1.168 + }
1.169 + }
1.170 + };
1.171 +
1.172 +
1.173 +} //END OF NAMESPACE LEMON
1.174 +
1.175 +#endif