Redesigned CapacityScaling algorithm with almost the same interface.
The new version does not use the ResidualGraphAdaptor for performance reasons.
Scaling can be enabled and disabled with a parameter of the run() function.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
24 ///\brief Algorithm for the Resource Constrained Shortest Path problem.
27 #include <lemon/list_graph.h>
28 #include <lemon/graph_utils.h>
29 #include <lemon/error.h>
30 #include <lemon/maps.h>
31 #include <lemon/tolerance.h>
32 #include <lemon/dijkstra.h>
33 #include <lemon/path.h>
34 #include <lemon/counter.h>
39 ///\brief Algorithms for the Resource Constrained Shortest Path Problem
41 ///The Resource Constrained Shortest (Least Cost) Path problem is the
42 ///following. We are given a directed graph with two additive weightings
43 ///on the edges, referred as \e cost and \e delay. In addition,
44 ///a source and a destination node \e s and \e t and a delay
45 ///constraint \e D is given. A path \e p is called \e feasible
46 ///if <em>delay(p)\<=D</em>. Then, the task is to find the least cost
50 class CM=typename Graph:: template EdgeMap<double>,
52 class ConstrainedShortestPath
56 GRAPH_TYPEDEFS(typename Graph);
58 typedef SimplePath<Graph> Path;
63 Tolerance<double> tol;
74 typedef typename CM::Key Key;
76 CoMap(const CM &c, const DM &d) :_cost(c), _delay(d), _lambda(0) {}
77 double lambda() const { return _lambda; }
78 void lambda(double l) { _lambda=l; }
79 Value operator[](Key &e) const
81 return _cost[e]+_lambda*_delay[e];
88 Dijkstra<Graph, CoMap> _dij;
92 /// \brief Constructor
96 ConstrainedShortestPath(const Graph &g, const CM &ct, const DM &dl)
97 : _g(g), _cost(ct), _delay(dl),
98 _co_map(ct, dl), _dij(_g,_co_map) {}
101 ///Compute the cost of a path
102 double cost(const Path &p) const
106 for(typename Path::EdgeIt e(p);e!=INVALID;++e) s+=_cost[e];
110 ///Compute the delay of a path
111 double delay(const Path &p) const
114 for(typename Path::EdgeIt e(p);e!=INVALID;++e) s+=_delay[e];
118 ///Runs the LARAC algorithm
120 ///This function runs a Lagrange relaxation based heuristic to find
121 ///a delay constrained least cost path.
122 ///\param s source node
123 ///\param t target node
124 ///\param delta upper bound on the delta
125 ///\retval lo_bo a lower bound on the optimal solution
126 ///\return the found path or an empty
127 Path larac(Node s, Node t, double delta, double &lo_bo)
130 double cp,cq,dp,dq,cr,dr;
135 Dijkstra<Graph,CM> dij(_g,_cost);
137 if(!dij.reached(t)) return Path();
142 if(delay(p)<=delta) return p;
144 Dijkstra<Graph,DM> dij(_g,_delay);
150 if(delay(q)>delta) return Path();
152 lambda=(cp-cq)/(dq-dp);
153 _co_map.lambda(lambda);
158 if(!tol.less(cr+lambda*dr,cp+lambda*dp)) {
159 lo_bo=cq+lambda*(dq-delta);
162 else if(tol.less(dr,delta))
168 else if(tol.less(delta,dr))
180 } //END OF NAMESPACE LEMON