57 |
57 |
58 GRAPH_TYPEDEFS(typename Graph); |
58 GRAPH_TYPEDEFS(typename Graph); |
59 |
59 |
60 typedef SimplePath<Graph> Path; |
60 typedef SimplePath<Graph> Path; |
61 |
61 |
62 Graph &_g; |
62 private: |
|
63 |
|
64 const Graph &_g; |
63 Tolerance<double> tol; |
65 Tolerance<double> tol; |
64 |
66 |
65 CM &_cost; |
67 const CM &_cost; |
66 DM &_delay; |
68 const DM &_delay; |
67 |
69 |
68 class CoMap |
70 class CoMap |
69 { |
71 { |
70 CM &_cost; |
72 const CM &_cost; |
71 DM &_delay; |
73 const DM &_delay; |
72 double _lambda; |
74 double _lambda; |
73 public: |
75 public: |
74 typedef typename CM::Key Key; |
76 typedef typename CM::Key Key; |
75 typedef double Value; |
77 typedef double Value; |
76 CoMap(CM &c,DM &d) :_cost(c), _delay(d), _lambda(0) {} |
78 CoMap(const CM &c, const DM &d) :_cost(c), _delay(d), _lambda(0) {} |
77 double lambda() const { return _lambda; } |
79 double lambda() const { return _lambda; } |
78 void lambda(double l) { _lambda=l; } |
80 void lambda(double l) { _lambda=l; } |
79 Value operator[](Key &e) const |
81 Value operator[](Key &e) const |
80 { |
82 { |
81 return _cost[e]+_lambda*_delay[e]; |
83 return _cost[e]+_lambda*_delay[e]; |
82 } |
84 } |
83 } _co_map; |
85 }; |
|
86 |
|
87 CoMap _co_map; |
84 |
88 |
85 |
89 |
86 Dijkstra<Graph, CoMap> _dij; |
90 Dijkstra<Graph, CoMap> _dij; |
|
91 |
|
92 public: |
|
93 |
87 ///\e |
94 ///\e |
88 |
95 |
89 ///\e |
96 ///\e |
90 /// |
97 /// |
91 ConstrainedShortestPath(Graph &g, CM &ct, DM &dl) |
98 ConstrainedShortestPath(const Graph &g, const CM &ct, const DM &dl) |
92 : _g(g), _cost(ct), _delay(dl), |
99 : _g(g), _cost(ct), _delay(dl), |
93 _co_map(ct,dl), _dij(_g,_co_map) {} |
100 _co_map(ct, dl), _dij(_g,_co_map) {} |
94 |
101 |
95 |
102 |
96 ///Compute the cost of a path |
103 ///Compute the cost of a path |
97 double cost(const Path &p) |
104 double cost(const Path &p) const |
98 { |
105 { |
99 double s=0; |
106 double s=0; |
100 // Path r; |
107 // Path r; |
101 for(typename Path::EdgeIt e(p);e!=INVALID;++e) s+=_cost[e]; |
108 for(typename Path::EdgeIt e(p);e!=INVALID;++e) s+=_cost[e]; |
102 return s; |
109 return s; |
103 } |
110 } |
104 |
111 |
105 ///Compute the delay of a path |
112 ///Compute the delay of a path |
106 double delay(const Path &p) |
113 double delay(const Path &p) const |
107 { |
114 { |
108 double s=0; |
115 double s=0; |
109 for(typename Path::EdgeIt e(p);e!=INVALID;++e) s+=_delay[e]; |
116 for(typename Path::EdgeIt e(p);e!=INVALID;++e) s+=_delay[e]; |
110 return s; |
117 return s; |
111 } |
118 } |