COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/csp.h @ 2487:568ff3572a96

Last change on this file since 2487:568ff3572a96 was 2487:568ff3572a96, checked in by Balazs Dezso, 12 years ago

Removing other occurences of cnt

File size: 4.2 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
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.
12 *
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
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_CSP_H
20#define LEMON_CSP_H
21
22///\ingroup approx
23///\file
24///\brief Algorithm for the Resource Constrained Shortest Path problem.
25///
26
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>
35namespace lemon {
36
37  ///\ingroup approx
38  ///
39  ///\brief Algorithms for the Resource Constrained Shortest Path Problem
40  ///
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
47  ///feasible path.
48  ///
49  template<class Graph,
50           class CM=typename Graph:: template EdgeMap<double>,
51           class DM=CM>
52  class ConstrainedShortestPath
53  {
54  public:
55   
56    GRAPH_TYPEDEFS(typename Graph);
57   
58    typedef SimplePath<Graph> Path;
59   
60  private:
61   
62    const Graph &_g;
63    Tolerance<double> tol;
64
65    const CM &_cost;
66    const DM &_delay;
67
68    class CoMap
69    {
70      const CM &_cost;
71      const DM &_delay;
72      double _lambda;
73    public:
74      typedef typename CM::Key Key;
75      typedef double Value;
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
80      {
81        return _cost[e]+_lambda*_delay[e];
82      }
83    };
84
85    CoMap _co_map;
86   
87   
88    Dijkstra<Graph, CoMap> _dij;
89
90  public:
91   
92    /// \brief Constructor
93   
94    ///Constructor
95    ///
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) {}
99   
100
101    ///Compute the cost of a path
102    double cost(const Path &p) const
103    {
104      double s=0;
105      //      Path r; 
106      for(typename Path::EdgeIt e(p);e!=INVALID;++e) s+=_cost[e];
107      return s;
108    }
109
110    ///Compute the delay of a path
111    double delay(const Path &p) const
112    {
113      double s=0;
114      for(typename Path::EdgeIt e(p);e!=INVALID;++e) s+=_delay[e];
115      return s;
116    }
117   
118    ///Runs the LARAC algorithm
119   
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)
128    {
129      double lambda=0;
130      double cp,cq,dp,dq,cr,dr;
131      Path p;
132      Path q;
133      Path r;
134      {
135        Dijkstra<Graph,CM> dij(_g,_cost);
136        dij.run(s,t);
137        if(!dij.reached(t)) return Path();
138        p=dij.path(t);
139        cp=cost(p);
140        dp=delay(p);
141      }
142      if(delay(p)<=delta) return p;
143      {
144        Dijkstra<Graph,DM> dij(_g,_delay);
145        dij.run(s,t);
146        q=dij.path(t);
147        cq=cost(q);
148        dq=delay(q);
149      }
150      if(delay(q)>delta) return Path();
151      while (true) {
152        lambda=(cp-cq)/(dq-dp);
153        _co_map.lambda(lambda);
154        _dij.run(s,t);
155        r=_dij.path(t);
156        cr=cost(r);
157        dr=delay(r);
158        if(!tol.less(cr+lambda*dr,cp+lambda*dp)) {
159          lo_bo=cq+lambda*(dq-delta);
160          return q;
161        }
162        else if(tol.less(dr,delta))
163          {
164            q=r;
165            cq=cr;
166            dq=dr;
167          }
168        else if(tol.less(delta,dr))
169          {
170            p=r;
171            cp=cr;
172            dp=dr;
173          }
174        else return r;
175      }
176    }
177  };
178 
179
180} //END OF NAMESPACE LEMON
181
182#endif
Note: See TracBrowser for help on using the repository browser.