COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/csp.h @ 2476:059dcdda37c5

Last change on this file since 2476:059dcdda37c5 was 2401:7f20ec638bc2, checked in by Balazs Dezso, 13 years ago

Data hiding
Const members

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///\todo dijkstraZero() solution should be revised.
28
29#include <lemon/list_graph.h>
30#include <lemon/graph_utils.h>
31#include <lemon/error.h>
32#include <lemon/maps.h>
33#include <lemon/tolerance.h>
34#include <lemon/dijkstra.h>
35#include <lemon/path.h>
36#include <lemon/counter.h>
37namespace lemon {
38
39  ///\ingroup approx
40 
41  ///Algorithms for the Resource Constrained Shortest Path Problem
42 
43  ///The Resource Constrained Shortest (Least Cost) Path problem is the
44  ///following. We are given a directed graph with two additive weightings
45  ///on the edges, referred as \e cost and \e delay. In addition,
46  ///a source and a destination node \e s and \e t and a delay
47  ///constraint \e D is given. A path \e p is called \e feasible
48  ///if <em>delay(p)\<=D</em>. Then, the task is to find the least cost
49  ///feasible path.
50  ///
51  template<class Graph,
52           class CM=typename Graph:: template EdgeMap<double>,
53           class DM=CM>
54  class ConstrainedShortestPath
55  {
56  public:
57   
58    GRAPH_TYPEDEFS(typename Graph);
59   
60    typedef SimplePath<Graph> Path;
61   
62  private:
63   
64    const Graph &_g;
65    Tolerance<double> tol;
66
67    const CM &_cost;
68    const DM &_delay;
69
70    class CoMap
71    {
72      const CM &_cost;
73      const DM &_delay;
74      double _lambda;
75    public:
76      typedef typename CM::Key Key;
77      typedef double Value;
78      CoMap(const CM &c, const DM &d) :_cost(c), _delay(d), _lambda(0) {}
79      double lambda() const { return _lambda; }
80      void lambda(double l)  { _lambda=l; }
81      Value operator[](Key &e) const
82      {
83        return _cost[e]+_lambda*_delay[e];
84      }
85    };
86
87    CoMap _co_map;
88   
89   
90    Dijkstra<Graph, CoMap> _dij;
91
92  public:
93   
94    ///\e
95   
96    ///\e
97    ///
98    ConstrainedShortestPath(const Graph &g, const CM &ct, const DM &dl)
99      : _g(g), _cost(ct), _delay(dl),
100        _co_map(ct, dl), _dij(_g,_co_map) {}
101   
102
103    ///Compute the cost of a path
104    double cost(const Path &p) const
105    {
106      double s=0;
107      //      Path r; 
108      for(typename Path::EdgeIt e(p);e!=INVALID;++e) s+=_cost[e];
109      return s;
110    }
111
112    ///Compute the delay of a path
113    double delay(const Path &p) const
114    {
115      double s=0;
116      for(typename Path::EdgeIt e(p);e!=INVALID;++e) s+=_delay[e];
117      return s;
118    }
119   
120    ///Runs the LARAC algorithm
121   
122    ///This function runs a Lagrange relaxation based heuristic to find
123    ///a delay constrained least cost path.
124    ///\param s source node
125    ///\param t target node
126    ///\retval lo_bo a lower bound on the optimal solution
127    ///\return the found path or an empty
128    Path larac(Node s, Node t, double delta, double &lo_bo)
129    {
130      NoCounter cnt("LARAC iterations: ");
131      double lambda=0;
132      double cp,cq,dp,dq,cr,dr;
133      Path p;
134      Path q;
135      Path r;
136      {
137        Dijkstra<Graph,CM> dij(_g,_cost);
138        dij.run(s,t);
139        cnt++;
140        if(!dij.reached(t)) return Path();
141        p=dij.path(t);
142        cp=cost(p);
143        dp=delay(p);
144      }
145      if(delay(p)<=delta) return p;
146      {
147        Dijkstra<Graph,DM> dij(_g,_delay);
148        dij.run(s,t);
149        cnt++;
150        q=dij.path(t);
151        cq=cost(q);
152        dq=delay(q);
153      }
154      if(delay(q)>delta) return Path();
155      while (true) {
156        lambda=(cp-cq)/(dq-dp);
157        _co_map.lambda(lambda);
158        _dij.run(s,t);
159        cnt++;
160        r=_dij.path(t);
161        cr=cost(r);
162        dr=delay(r);
163        if(!tol.less(cr+lambda*dr,cp+lambda*dp)) {
164          lo_bo=cq+lambda*(dq-delta);
165          return q;
166        }
167        else if(tol.less(dr,delta))
168          {
169            q=r;
170            cq=cr;
171            dq=dr;
172          }
173        else if(tol.less(delta,dr))
174          {
175            p=r;
176            cp=cr;
177            dp=dr;
178          }
179        else return r;
180      }
181    }
182  };
183 
184
185} //END OF NAMESPACE LEMON
186
187#endif
Note: See TracBrowser for help on using the repository browser.