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-2022 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 //#define ROUTER_DEBUG_HINT
35 //#define ROUTER_DEBUG_COND (true)
36 
37 
38 // ===========================================================================
39 // class definitions
40 // ===========================================================================
45 template<class E, class V>
47 public:
53  class EdgeInfo {
54  public:
56  EdgeInfo(const E* const e)
57  : edge(e), effort(std::numeric_limits<double>::max()),
58  heuristicEffort(std::numeric_limits<double>::max()),
59  leaveTime(0.), prev(nullptr), visited(false), prohibited(false) {}
60 
62  const E* const edge;
63 
65  double effort;
66 
68  // only used by A*
70 
72  double leaveTime;
73 
75  const EdgeInfo* prev;
76 
78  bool visited;
79 
81  bool prohibited;
82 
83  inline void reset() {
84  effort = std::numeric_limits<double>::max();
85  heuristicEffort = std::numeric_limits<double>::max();
86  visited = false;
87  }
88 
89  private:
91  EdgeInfo& operator=(const EdgeInfo& s) = delete;
92 
93  };
94 
96  typedef double(* Operation)(const E* const, const V* const, double);
97 
99  SUMOAbstractRouter(const std::string& type, bool unbuildIsWarning, Operation operation, Operation ttOperation,
100  const bool havePermissions, const bool haveRestrictions) :
101  myErrorMsgHandler(unbuildIsWarning ? MsgHandler::getWarningInstance() : MsgHandler::getErrorInstance()),
102  myOperation(operation), myTTOperation(ttOperation),
103  myBulkMode(false),
104  myAutoBulkMode(false),
105  myHavePermissions(havePermissions),
106  myHaveRestrictions(haveRestrictions),
107  myType(type),
108  myQueryVisits(0),
109  myNumQueries(0),
110  myQueryStartTime(0),
111  myQueryTimeSum(0) {
112  }
113 
118  myBulkMode(false),
119  myAutoBulkMode(false),
122  myType(other->myType),
123  myQueryVisits(0),
124  myNumQueries(0),
125  myQueryStartTime(0),
126  myQueryTimeSum(0) { }
127 
128 
129 
132  if (myNumQueries > 0) {
133  WRITE_MESSAGE(myType + " answered " + toString(myNumQueries) + " queries and explored " + toString(double(myQueryVisits) / myNumQueries) + " edges on average.");
134  WRITE_MESSAGE(myType + " spent " + elapsedMs2string(myQueryTimeSum) + " answering queries (" + toString(double(myQueryTimeSum) / myNumQueries) + "ms on average).");
135  }
136  }
137 
138  virtual SUMOAbstractRouter* clone() = 0;
139 
140  inline void init(const int edgeID, const SUMOTime msTime) {
141 // if (!myAmClean) {
142  // all EdgeInfos touched in the previous query are either in myFrontierList or myFound: clean those up
143  for (auto& edgeInfo : myFrontierList) {
144  edgeInfo->reset();
145  }
146  myFrontierList.clear();
147  for (auto& edgeInfo : myFound) {
148  edgeInfo->reset();
149  }
150  myFound.clear();
151  if (edgeID > -1) {
152  // add begin node
153  auto& fromInfo = myEdgeInfos[edgeID];
154  fromInfo.effort = 0.;
155  fromInfo.heuristicEffort = 0.;
156  fromInfo.prev = nullptr;
157  fromInfo.leaveTime = STEPS2TIME(msTime);
158  myFrontierList.push_back(&fromInfo);
159  }
160  myAmClean = true;
161 // }
162  }
163 
165  virtual void reset(const V* const vehicle) {
166  UNUSED_PARAMETER(vehicle);
167  }
168 
169  const std::string& getType() const {
170  return myType;
171  }
172 
173  inline const typename SUMOAbstractRouter<E, V>::EdgeInfo& getEdgeInfo(int index) const {
174  return myEdgeInfos[index];
175  }
176 
179  virtual bool compute(const E* from, const E* to, const V* const vehicle,
180  SUMOTime msTime, std::vector<const E*>& into, bool silent = false) = 0;
181 
182 
187  inline bool compute(
188  const E* from, double fromPos,
189  const E* to, double toPos,
190  const V* const vehicle,
191  SUMOTime msTime, std::vector<const E*>& into, bool silent = false) {
192  if (from != to || fromPos <= toPos) {
193  return compute(from, to, vehicle, msTime, into, silent);
194  } else {
195  return computeLooped(from, to, vehicle, msTime, into, silent);
196  }
197  }
198 
199 
202  inline bool computeLooped(const E* from, const E* to, const V* const vehicle,
203  SUMOTime msTime, std::vector<const E*>& into, bool silent = false) {
204  if (from != to) {
205  return compute(from, to, vehicle, msTime, into, silent);
206  }
207  double minEffort = std::numeric_limits<double>::max();
208  std::vector<const E*> best;
209  const SUMOVehicleClass vClass = vehicle == 0 ? SVC_IGNORING : vehicle->getVClass();
210  for (const std::pair<const E*, const E*>& follower : from->getViaSuccessors(vClass)) {
211  std::vector<const E*> tmp;
212  compute(follower.first, to, vehicle, msTime, tmp, true);
213  if (tmp.size() > 0) {
214  double effort = recomputeCosts(tmp, vehicle, msTime);
215  if (effort < minEffort) {
216  minEffort = effort;
217  best = tmp;
218  }
219  }
220  }
221  if (minEffort != std::numeric_limits<double>::max()) {
222  into.push_back(from);
223  std::copy(best.begin(), best.end(), std::back_inserter(into));
224  return true;
225  } else if (!silent && myErrorMsgHandler != nullptr) {
226  myErrorMsgHandler->informf("No connection between edge '%' and edge '%' found.", from->getID(), to->getID());
227  }
228  return false;
229  }
230 
231  inline bool isProhibited(const E* const edge, const V* const vehicle) const {
232  return (myHavePermissions && edge->prohibits(vehicle)) || (myHaveRestrictions && edge->restricts(vehicle));
233  }
234 
235  inline double getTravelTime(const E* const e, const V* const v, const double t, const double effort) const {
236  return myTTOperation == nullptr ? effort : (*myTTOperation)(e, v, t);
237  }
238 
239  inline void updateViaEdgeCost(const E* viaEdge, const V* const v, double& time, double& effort, double& length) const {
240  while (viaEdge != nullptr && viaEdge->isInternal()) {
241  const double viaEffortDelta = this->getEffort(viaEdge, v, time);
242  time += getTravelTime(viaEdge, v, time, viaEffortDelta);
243  effort += viaEffortDelta;
244  length += viaEdge->getLength();
245  viaEdge = viaEdge->getViaSuccessors().front().second;
246  }
247  }
248 
249  inline void updateViaCost(const E* const prev, const E* const e, const V* const v, double& time, double& effort, double& length) const {
250  if (prev != nullptr) {
251  for (const std::pair<const E*, const E*>& follower : prev->getViaSuccessors()) {
252  if (follower.first == e) {
253  updateViaEdgeCost(follower.second, v, time, effort, length);
254  break;
255  }
256  }
257  }
258  const double effortDelta = this->getEffort(e, v, time);
259  effort += effortDelta;
260  time += getTravelTime(e, v, time, effortDelta);
261  length += e->getLength();
262  }
263 
264 
265  inline double recomputeCosts(const std::vector<const E*>& edges, const V* const v, SUMOTime msTime, double* lengthp = nullptr) const {
266  double time = STEPS2TIME(msTime);
267  double effort = 0.;
268  double length = 0.;
269  if (lengthp == nullptr) {
270  lengthp = &length;
271  } else {
272  *lengthp = 0.;
273  }
274  const E* prev = nullptr;
275  for (const E* const e : edges) {
276  if (isProhibited(e, v)) {
277  return -1;
278  }
279  updateViaCost(prev, e, v, time, effort, *lengthp);
280  prev = e;
281  }
282  return effort;
283  }
284 
285 
286  inline double recomputeCosts(const std::vector<const E*>& edges, const V* const v, double fromPos, double toPos, SUMOTime msTime, double* lengthp = nullptr) const {
287  double effort = recomputeCosts(edges, v, msTime, lengthp);
288  if (!edges.empty()) {
289  double firstEffort = this->getEffort(edges.front(), v, STEPS2TIME(msTime));
290  double lastEffort = this->getEffort(edges.back(), v, STEPS2TIME(msTime));
291  effort -= firstEffort * fromPos / edges.front()->getLength();
292  effort -= lastEffort * (edges.back()->getLength() - toPos) / edges.back()->getLength();
293  }
294  return effort;
295  }
296 
297 
298  inline double setHint(const typename std::vector<const E*>::const_iterator routeBegin, const typename std::vector<const E*>::const_iterator routeEnd, const V* const v, SUMOTime msTime) {
299  double time = STEPS2TIME(msTime);
300  double effort = 0.;
301  double length = 0.;
302  const EdgeInfo* prev = &myEdgeInfos[(*routeBegin)->getNumericalID()];
303  init((*routeBegin)->getNumericalID(), msTime);
304  for (auto e = routeBegin + 1; e != routeEnd; ++e) {
305  if (isProhibited(*e, v)) {
306  return -1;
307  }
308  auto& edgeInfo = myEdgeInfos[(*e)->getNumericalID()];
309  edgeInfo.heuristicEffort = effort;
310  edgeInfo.prev = prev;
311  updateViaCost(prev->edge, *e, v, time, effort, length);
312  edgeInfo.effort = effort;
313  edgeInfo.leaveTime = time;
314  myFound.push_back(&edgeInfo);
315  prev = &edgeInfo;
316 #ifdef ROUTER_DEBUG_HINT
317  if (ROUTER_DEBUG_COND) {
318  std::cout << "DEBUG: hit=" << (*e)->getID()
319  << " TT=" << edgeInfo.effort
320  << " EF=" << this->getEffort(*e, v, edgeInfo.leaveTime)
321  << " HT=" << edgeInfo.heuristicEffort << "\n";
322  }
323 #endif
324  }
325  return effort;
326  }
327 
328 
329  inline double getEffort(const E* const e, const V* const v, double t) const {
330  return (*myOperation)(e, v, t);
331  }
332 
333  inline void startQuery() {
334  myNumQueries++;
336  }
337 
338  inline void endQuery(int visits) {
339  myQueryVisits += visits;
341  }
342 
343  virtual void setBulkMode(const bool mode) {
344  myBulkMode = mode;
345  }
346 
347  inline void setAutoBulkMode(const bool mode) {
348  myAutoBulkMode = mode;
349  }
350 
351  virtual void prohibit(const std::vector<E*>& toProhibit) {
352  for (E* const edge : this->myProhibited) {
353  myEdgeInfos[edge->getNumericalID()].prohibited = false;
354  }
355  for (E* const edge : toProhibit) {
356  myEdgeInfos[edge->getNumericalID()].prohibited = true;
357  }
358  this->myProhibited = toProhibit;
359  }
360 
361 
363  void buildPathFrom(const typename SUMOAbstractRouter<E, V>::EdgeInfo* rbegin, std::vector<const E*>& edges) {
364  std::vector<const E*> tmp;
365  while (rbegin != nullptr) {
366  tmp.push_back(rbegin->edge);
367  rbegin = rbegin->prev;
368  }
369  std::copy(tmp.rbegin(), tmp.rend(), std::back_inserter(edges));
370  }
371 
372 protected:
375 
378 
381 
384 
387 
389  bool myAmClean;
390 
392  const bool myHavePermissions;
393 
395  const bool myHaveRestrictions;
396 
398  std::vector<E*> myProhibited;
399 
401  std::vector<typename SUMOAbstractRouter<E, V>::EdgeInfo> myEdgeInfos;
402 
404  std::vector<typename SUMOAbstractRouter<E, V>::EdgeInfo*> myFrontierList;
406  std::vector<typename SUMOAbstractRouter<E, V>::EdgeInfo*> myFound;
407 
408 private:
410  const std::string myType;
411 
413  long long int myQueryVisits;
414  long long int myNumQueries;
416  long long int myQueryStartTime;
417  long long int myQueryTimeSum;
418 
419 private:
422 };
#define WRITE_MESSAGE(msg)
Definition: MsgHandler.h:282
std::string elapsedMs2string(long long int t)
convert ms to string for log output
Definition: SUMOTime.cpp:110
#define STEPS2TIME(x)
Definition: SUMOTime.h:53
long long int SUMOTime
Definition: SUMOTime.h:32
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:30
std::string toString(const T &t, std::streamsize accuracy=gPrecision)
Definition: ToString.h:46
void informf(const std::string &format, T value, Targs... Fargs)
adds a new formatted message
Definition: MsgHandler.h:114
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
The list of explicitly prohibited edges.
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
virtual void setBulkMode(const bool mode)
std::vector< typename SUMOAbstractRouter< E, V >::EdgeInfo > myEdgeInfos
The container of edge information.
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
virtual void prohibit(const std::vector< E * > &toProhibit)
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
const SUMOAbstractRouter< E, V >::EdgeInfo & getEdgeInfo(int index) 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 setHint(const typename std::vector< const E * >::const_iterator routeBegin, const typename std::vector< const E * >::const_iterator routeEnd, const V *const v, SUMOTime msTime)
void init(const int edgeID, const SUMOTime msTime)
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)
bool myAmClean
whether we are already initialized
const bool myHaveRestrictions
whether edge restrictions need to be considered
void buildPathFrom(const typename SUMOAbstractRouter< E, V >::EdgeInfo *rbegin, std::vector< const E * > &edges)
Builds the path from marked edges.
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...
SUMOAbstractRouter & operator=(const SUMOAbstractRouter &s)=delete
Invalidated assignment operator.
void endQuery(int visits)
virtual ~SUMOAbstractRouter()
Destructor.
std::vector< typename SUMOAbstractRouter< E, V >::EdgeInfo * > myFrontierList
A container for reusage of the min edge heap.
std::vector< typename SUMOAbstractRouter< E, V >::EdgeInfo * > myFound
list of visited Edges (for resetting)
const std::string myType
the type of this router
static long getCurrentMillis()
Returns the current time in milliseconds.
Definition: SysUtils.cpp:39