Eclipse SUMO - Simulation of Urban MObility
SUMOAbstractRouter.h
Go to the documentation of this file.
1 /****************************************************************************/
2 // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.org/sumo
3 // Copyright (C) 2006-2020 German Aerospace Center (DLR) and others.
4 // This program and the accompanying materials are made available under the
5 // terms of the Eclipse Public License 2.0 which is available at
6 // https://www.eclipse.org/legal/epl-2.0/
7 // This Source Code may also be made available under the following Secondary
8 // Licenses when the conditions for such availability set forth in the Eclipse
9 // Public License 2.0 are satisfied: GNU General Public License, version 2
10 // or later which is available at
11 // https://www.gnu.org/licenses/old-licenses/gpl-2.0-standalone.html
12 // SPDX-License-Identifier: EPL-2.0 OR GPL-2.0-or-later
13 /****************************************************************************/
20 // An abstract router base class
21 /****************************************************************************/
22 #pragma once
23 #include <config.h>
24 
25 #include <string>
26 #include <vector>
27 #include <algorithm>
28 #include <iterator>
29 #include <assert.h>
30 #include <utils/common/SysUtils.h>
32 #include <utils/common/SUMOTime.h>
33 #include <utils/common/ToString.h>
34 
35 
36 // ===========================================================================
37 // class definitions
38 // ===========================================================================
43 template<class E, class V>
45 public:
51  class EdgeInfo {
52  public:
54  EdgeInfo(const E* const e)
55  : edge(e), effort(std::numeric_limits<double>::max()),
56  heuristicEffort(std::numeric_limits<double>::max()),
57  leaveTime(0.), prev(nullptr), visited(false), prohibited(false) {}
58 
60  const E* const edge;
61 
63  double effort;
64 
66  // only used by A*
68 
70  double leaveTime;
71 
73  const EdgeInfo* prev;
74 
76  bool visited;
77 
79  bool prohibited;
80 
81  inline void reset() {
82  effort = std::numeric_limits<double>::max();
83  heuristicEffort = std::numeric_limits<double>::max();
84  visited = false;
85  }
86 
87  private:
89  EdgeInfo& operator=(const EdgeInfo& s) = delete;
90 
91  };
92 
94  typedef double(* Operation)(const E* const, const V* const, double);
95 
97  SUMOAbstractRouter(const std::string& type, bool unbuildIsWarning, Operation operation, Operation ttOperation,
98  const bool havePermissions, const bool haveRestrictions) :
99  myErrorMsgHandler(unbuildIsWarning ? MsgHandler::getWarningInstance() : MsgHandler::getErrorInstance()),
100  myOperation(operation), myTTOperation(ttOperation),
101  myBulkMode(false),
102  myAutoBulkMode(false),
103  myHavePermissions(havePermissions),
104  myHaveRestrictions(haveRestrictions),
105  myType(type),
106  myQueryVisits(0),
107  myNumQueries(0),
108  myQueryStartTime(0),
109  myQueryTimeSum(0) {
110  }
111 
116  myBulkMode(false),
117  myAutoBulkMode(false),
120  myType(other->myType),
121  myQueryVisits(0),
122  myNumQueries(0),
123  myQueryStartTime(0),
124  myQueryTimeSum(0) { }
125 
126 
127 
130  if (myNumQueries > 0) {
131  WRITE_MESSAGE(myType + " answered " + toString(myNumQueries) + " queries and explored " + toString(double(myQueryVisits) / myNumQueries) + " edges on average.");
132  WRITE_MESSAGE(myType + " spent " + elapsedMs2string(myQueryTimeSum) + " answering queries (" + toString(double(myQueryTimeSum) / myNumQueries) + "ms on average).");
133  }
134  }
135 
136  virtual SUMOAbstractRouter* clone() = 0;
137 
139  virtual void reset(const V* const vehicle) {
140  UNUSED_PARAMETER(vehicle);
141  }
142 
143  const std::string& getType() const {
144  return myType;
145  }
146 
149  virtual bool compute(const E* from, const E* to, const V* const vehicle,
150  SUMOTime msTime, std::vector<const E*>& into, bool silent = false) = 0;
151 
152 
157  inline bool compute(
158  const E* from, double fromPos,
159  const E* to, double toPos,
160  const V* const vehicle,
161  SUMOTime msTime, std::vector<const E*>& into, bool silent = false) {
162  if (from != to || fromPos <= toPos) {
163  return compute(from, to, vehicle, msTime, into, silent);
164  } else {
165  return computeLooped(from, to, vehicle, msTime, into, silent);
166  }
167  }
168 
169 
172  inline bool computeLooped(const E* from, const E* to, const V* const vehicle,
173  SUMOTime msTime, std::vector<const E*>& into, bool silent = false) {
174  if (from != to) {
175  return compute(from, to, vehicle, msTime, into, silent);
176  }
177  double minEffort = std::numeric_limits<double>::max();
178  std::vector<const E*> best;
179  const SUMOVehicleClass vClass = vehicle == 0 ? SVC_IGNORING : vehicle->getVClass();
180  for (const std::pair<const E*, const E*>& follower : from->getViaSuccessors(vClass)) {
181  std::vector<const E*> tmp;
182  compute(follower.first, to, vehicle, msTime, tmp, true);
183  if (tmp.size() > 0) {
184  double effort = recomputeCosts(tmp, vehicle, msTime);
185  if (effort < minEffort) {
186  minEffort = effort;
187  best = tmp;
188  }
189  }
190  }
191  if (minEffort != std::numeric_limits<double>::max()) {
192  into.push_back(from);
193  std::copy(best.begin(), best.end(), std::back_inserter(into));
194  return true;
195  } else if (!silent && myErrorMsgHandler != nullptr) {
196  myErrorMsgHandler->informf("No connection between edge '%' and edge '%' found.", from->getID(), to->getID());
197  }
198  return false;
199  }
200 
201  inline bool isProhibited(const E* const edge, const V* const vehicle) const {
202  return (myHavePermissions && edge->prohibits(vehicle)) || (myHaveRestrictions && edge->restricts(vehicle));
203  }
204 
205  virtual void prohibit(const std::vector<E*>& /* toProhibit */) {}
206 
207  inline double getTravelTime(const E* const e, const V* const v, const double t, const double effort) const {
208  return myTTOperation == nullptr ? effort : (*myTTOperation)(e, v, t);
209  }
210 
211  inline void updateViaEdgeCost(const E* viaEdge, const V* const v, double& time, double& effort, double& length) const {
212  while (viaEdge != nullptr && viaEdge->isInternal()) {
213  const double viaEffortDelta = this->getEffort(viaEdge, v, time);
214  time += getTravelTime(viaEdge, v, time, viaEffortDelta);
215  effort += viaEffortDelta;
216  length += viaEdge->getLength();
217  viaEdge = viaEdge->getViaSuccessors().front().second;
218  }
219  }
220 
221  inline void updateViaCost(const E* const prev, const E* const e, const V* const v, double& time, double& effort, double& length) const {
222  if (prev != nullptr) {
223  for (const std::pair<const E*, const E*>& follower : prev->getViaSuccessors()) {
224  if (follower.first == e) {
225  updateViaEdgeCost(follower.second, v, time, effort, length);
226  break;
227  }
228  }
229  }
230  const double effortDelta = this->getEffort(e, v, time);
231  effort += effortDelta;
232  time += getTravelTime(e, v, time, effortDelta);
233  length += e->getLength();
234  }
235 
236 
237  inline double recomputeCosts(const std::vector<const E*>& edges, const V* const v, SUMOTime msTime, double* lengthp = nullptr) const {
238  double time = STEPS2TIME(msTime);
239  double effort = 0.;
240  double length = 0.;
241  if (lengthp == nullptr) {
242  lengthp = &length;
243  } else {
244  *lengthp = 0.;
245  }
246  const E* prev = nullptr;
247  for (const E* const e : edges) {
248  if (isProhibited(e, v)) {
249  return -1;
250  }
251  updateViaCost(prev, e, v, time, effort, *lengthp);
252  prev = e;
253  }
254  return effort;
255  }
256 
257 
258  inline double recomputeCosts(const std::vector<const E*>& edges, const V* const v, double fromPos, double toPos, SUMOTime msTime, double* lengthp = nullptr) const {
259  double effort = recomputeCosts(edges, v, msTime, lengthp);
260  if (!edges.empty()) {
261  double firstEffort = this->getEffort(edges.front(), v, STEPS2TIME(msTime));
262  double lastEffort = this->getEffort(edges.back(), v, STEPS2TIME(msTime));
263  effort -= firstEffort * fromPos / edges.front()->getLength();
264  effort -= lastEffort * (edges.back()->getLength() - toPos) / edges.back()->getLength();
265  }
266  return effort;
267  }
268 
269 
270  inline double getEffort(const E* const e, const V* const v, double t) const {
271  return (*myOperation)(e, v, t);
272  }
273 
274  inline void startQuery() {
275  myNumQueries++;
277  }
278 
279  inline void endQuery(int visits) {
280  myQueryVisits += visits;
282  }
283 
284  inline void setBulkMode(const bool mode) {
285  myBulkMode = mode;
286  }
287 
288  inline void setAutoBulkMode(const bool mode) {
289  myAutoBulkMode = mode;
290  }
291 
292 protected:
295 
298 
301 
304 
307 
309  const bool myHavePermissions;
310 
312  const bool myHaveRestrictions;
313 
314  std::vector<E*> myProhibited;
315 
316 private:
318  const std::string myType;
319 
321  long long int myQueryVisits;
322  long long int myNumQueries;
324  long long int myQueryStartTime;
325  long long int myQueryTimeSum;
326 private:
329 };
#define WRITE_MESSAGE(msg)
Definition: MsgHandler.h:278
std::string elapsedMs2string(long long int t)
convert ms to string for log output
Definition: SUMOTime.cpp:109
#define STEPS2TIME(x)
Definition: SUMOTime.h:53
long long int SUMOTime
Definition: SUMOTime.h:31
SUMOVehicleClass
Definition of vehicle classes to differ between different lane usage and authority types.
@ SVC_IGNORING
vehicles ignoring classes
#define UNUSED_PARAMETER(x)
Definition: StdDefs.h:29
std::string toString(const T &t, std::streamsize accuracy=gPrecision)
Definition: ToString.h:44
void informf(const std::string &format, T value, Targs... Fargs)
adds a new formatted message
Definition: MsgHandler.h:113
bool visited
whether the edge was already evaluated
EdgeInfo(const E *const e)
Constructor.
const E *const edge
The current edge.
double leaveTime
The time the vehicle leaves the edge.
double effort
Effort to reach the edge.
bool prohibited
whether the edge is currently not allowed
const EdgeInfo * prev
The previous edge.
double heuristicEffort
Estimated effort to reach the edge (effort + lower bound on remaining effort)
EdgeInfo & operator=(const EdgeInfo &s)=delete
Invalidated assignment operator.
virtual SUMOAbstractRouter * clone()=0
Operation myTTOperation
The object's operation to perform for travel times.
long long int myNumQueries
MsgHandler *const myErrorMsgHandler
the handler for routing errors
const std::string & getType() const
std::vector< E * > myProhibited
bool isProhibited(const E *const edge, const V *const vehicle) const
const bool myHavePermissions
whether edge permissions need to be considered
bool myBulkMode
whether we are currently operating several route queries in a bulk
long long int myQueryVisits
counters for performance logging
bool computeLooped(const E *from, const E *to, const V *const vehicle, SUMOTime msTime, std::vector< const E * > &into, bool silent=false)
Builds the route between the given edges using the minimum effort at the given time if from == to,...
double recomputeCosts(const std::vector< const E * > &edges, const V *const v, SUMOTime msTime, double *lengthp=nullptr) const
long long int myQueryStartTime
the time spent querying in milliseconds
SUMOAbstractRouter & operator=(const SUMOAbstractRouter &s)
Invalidated assignment operator.
bool compute(const E *from, double fromPos, const E *to, double toPos, const V *const vehicle, SUMOTime msTime, std::vector< const E * > &into, bool silent=false)
Builds the route between the given edges using the minimum effort at the given time,...
SUMOAbstractRouter(SUMOAbstractRouter *other)
Copy Constructor.
double(* Operation)(const E *const, const V *const, double)
Type of the function that is used to retrieve the edge effort.
Operation myOperation
The object's operation to perform.
double getTravelTime(const E *const e, const V *const v, const double t, const double effort) const
long long int myQueryTimeSum
void updateViaCost(const E *const prev, const E *const e, const V *const v, double &time, double &effort, double &length) const
virtual void reset(const V *const vehicle)
reset internal caches, used by CHRouter
double getEffort(const E *const e, const V *const v, double t) const
SUMOAbstractRouter(const std::string &type, bool unbuildIsWarning, Operation operation, Operation ttOperation, const bool havePermissions, const bool haveRestrictions)
Constructor.
void updateViaEdgeCost(const E *viaEdge, const V *const v, double &time, double &effort, double &length) const
double recomputeCosts(const std::vector< const E * > &edges, const V *const v, double fromPos, double toPos, SUMOTime msTime, double *lengthp=nullptr) const
void setAutoBulkMode(const bool mode)
virtual void prohibit(const std::vector< E * > &)
const bool myHaveRestrictions
whether edge restrictions need to be considered
void setBulkMode(const bool mode)
bool myAutoBulkMode
whether we are currently trying to detect bulk mode automatically
virtual bool compute(const E *from, const E *to, const V *const vehicle, SUMOTime msTime, std::vector< const E * > &into, bool silent=false)=0
Builds the route between the given edges using the minimum effort at the given time The definition of...
void endQuery(int visits)
virtual ~SUMOAbstractRouter()
Destructor.
const std::string myType
the type of this router
static long getCurrentMillis()
Returns the current time in milliseconds.
Definition: SysUtils.cpp:39