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-2019 German Aerospace Center (DLR) and others.
4 // This program and the accompanying materials
5 // are made available under the terms of the Eclipse Public License v2.0
6 // which accompanies this distribution, and is available at
7 // http://www.eclipse.org/legal/epl-v20.html
8 // SPDX-License-Identifier: EPL-2.0
9 /****************************************************************************/
16 // An abstract router base class
17 /****************************************************************************/
18 #ifndef SUMOAbstractRouter_h
19 #define SUMOAbstractRouter_h
20 
21 
22 // ===========================================================================
23 // included modules
24 // ===========================================================================
25 #include <config.h>
26 
27 #include <string>
28 #include <vector>
29 #include <algorithm>
30 #include <iterator>
31 #include <assert.h>
32 #include <utils/common/SysUtils.h>
34 #include <utils/common/SUMOTime.h>
35 #include <utils/common/ToString.h>
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  myHavePermissions(havePermissions),
105  myHaveRestrictions(haveRestrictions),
106  myType(type),
107  myQueryVisits(0),
108  myNumQueries(0),
109  myQueryStartTime(0),
110  myQueryTimeSum(0) {
111  }
112 
115  if (myNumQueries > 0) {
116  WRITE_MESSAGE(myType + " answered " + toString(myNumQueries) + " queries and explored " + toString(double(myQueryVisits) / myNumQueries) + " edges on average.");
117  WRITE_MESSAGE(myType + " spent " + toString(myQueryTimeSum) + "ms answering queries (" + toString(double(myQueryTimeSum) / myNumQueries) + "ms on average).");
118  }
119  }
120 
121  virtual SUMOAbstractRouter* clone() = 0;
122 
125  virtual bool compute(const E* from, const E* to, const V* const vehicle,
126  SUMOTime msTime, std::vector<const E*>& into, bool silent = false) = 0;
127 
130  inline bool computeLooped(const E* from, const E* to, const V* const vehicle,
131  SUMOTime msTime, std::vector<const E*>& into, bool silent = false) {
132  if (from != to) {
133  return compute(from, to, vehicle, msTime, into, silent);
134  }
135  double minEffort = std::numeric_limits<double>::max();
136  std::vector<const E*> best;
137  const SUMOVehicleClass vClass = vehicle == 0 ? SVC_IGNORING : vehicle->getVClass();
138  for (const std::pair<const E*, const E*>& follower : from->getViaSuccessors(vClass)) {
139  std::vector<const E*> tmp;
140  compute(follower.first, to, vehicle, msTime, tmp, true);
141  if (tmp.size() > 0) {
142  double effort = recomputeCosts(tmp, vehicle, msTime);
143  if (effort < minEffort) {
144  minEffort = effort;
145  best = tmp;
146  }
147  }
148  }
149  if (minEffort != std::numeric_limits<double>::max()) {
150  into.push_back(from);
151  std::copy(best.begin(), best.end(), std::back_inserter(into));
152  return true;
153  } else if (!silent && myErrorMsgHandler != nullptr) {
154  myErrorMsgHandler->informf("No connection between edge '%' and edge '%' found.", from->getID(), to->getID());
155  }
156  return false;
157  }
158 
159  inline bool isProhibited(const E* const edge, const V* const vehicle) const {
160  return (myHavePermissions && edge->prohibits(vehicle)) || (myHaveRestrictions && edge->restricts(vehicle));
161  }
162 
163  virtual void prohibit(const std::vector<E*>& /* toProhibit */) {}
164 
165  inline double getTravelTime(const E* const e, const V* const v, const double t, const double effort) const {
166  return myTTOperation == nullptr ? effort : (*myTTOperation)(e, v, t);
167  }
168 
169  inline void updateViaEdgeCost(const E* viaEdge, const V* const v, double& time, double& effort, double& length) const {
170  while (viaEdge != nullptr && viaEdge->isInternal()) {
171  const double viaEffortDelta = this->getEffort(viaEdge, v, time);
172  time += getTravelTime(viaEdge, v, time, viaEffortDelta);
173  effort += viaEffortDelta;
174  length += viaEdge->getLength();
175  viaEdge = viaEdge->getViaSuccessors().front().second;
176  }
177  }
178 
179  inline void updateViaCost(const E* const prev, const E* const e, const V* const v, double& time, double& effort, double& length) const {
180  if (prev != nullptr) {
181  for (const std::pair<const E*, const E*>& follower : prev->getViaSuccessors()) {
182  if (follower.first == e) {
183  updateViaEdgeCost(follower.second, v, time, effort, length);
184  break;
185  }
186  }
187  }
188  const double effortDelta = this->getEffort(e, v, time);
189  effort += effortDelta;
190  time += getTravelTime(e, v, time, effortDelta);
191  length += e->getLength();
192  }
193 
194 
195  inline double recomputeCosts(const std::vector<const E*>& edges, const V* const v, SUMOTime msTime, double* lengthp = nullptr) const {
196  double time = STEPS2TIME(msTime);
197  double effort = 0.;
198  double length = 0.;
199  if (lengthp == nullptr) {
200  lengthp = &length;
201  } else {
202  *lengthp = 0.;
203  }
204  const E* prev = nullptr;
205  for (const E* const e : edges) {
206  if (isProhibited(e, v)) {
207  return -1;
208  }
209  updateViaCost(prev, e, v, time, effort, *lengthp);
210  prev = e;
211  }
212  return effort;
213  }
214 
215 
216  inline double getEffort(const E* const e, const V* const v, double t) const {
217  return (*myOperation)(e, v, t);
218  }
219 
220  inline void startQuery() {
221  myNumQueries++;
223  }
224 
225  inline void endQuery(int visits) {
226  myQueryVisits += visits;
228  }
229 
230  inline void setBulkMode(const bool mode) {
231  myBulkMode = mode;
232  }
233 
234 protected:
237 
240 
243 
246 
248  const bool myHavePermissions;
249 
251  const bool myHaveRestrictions;
252 
253  std::vector<E*> myProhibited;
254 
255 private:
257  const std::string myType;
258 
260  long long int myQueryVisits;
261  long long int myNumQueries;
263  long long int myQueryStartTime;
264  long long int myQueryTimeSum;
265 private:
268 };
269 
270 
271 #endif
272 
273 /****************************************************************************/
SUMOAbstractRouter::compute
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::myQueryVisits
long long int myQueryVisits
counters for performance logging
Definition: SUMOAbstractRouter.h:260
SUMOVehicleClass
SUMOVehicleClass
Definition of vehicle classes to differ between different lane usage and authority types.
Definition: SUMOVehicleClass.h:133
ToString.h
SUMOAbstractRouter::myType
const std::string myType
the type of this router
Definition: SUMOAbstractRouter.h:257
SUMOAbstractRouter::operator=
SUMOAbstractRouter & operator=(const SUMOAbstractRouter &s)
Invalidated assignment operator.
SUMOTime.h
SUMOAbstractRouter::Operation
double(* Operation)(const E *const, const V *const, double)
Type of the function that is used to retrieve the edge effort.
Definition: SUMOAbstractRouter.h:96
SUMOAbstractRouter::myHavePermissions
const bool myHavePermissions
whether edge permissions need to be considered
Definition: SUMOAbstractRouter.h:248
SUMOAbstractRouter::~SUMOAbstractRouter
virtual ~SUMOAbstractRouter()
Destructor.
Definition: SUMOAbstractRouter.h:114
MsgHandler.h
SUMOAbstractRouter::getEffort
double getEffort(const E *const e, const V *const v, double t) const
Definition: SUMOAbstractRouter.h:216
SUMOTime
long long int SUMOTime
Definition: SUMOTime.h:34
SUMOAbstractRouter::myProhibited
std::vector< E * > myProhibited
Definition: SUMOAbstractRouter.h:253
SUMOAbstractRouter::EdgeInfo::EdgeInfo
EdgeInfo(const E *const e)
Constructor.
Definition: SUMOAbstractRouter.h:56
SUMOAbstractRouter::updateViaCost
void updateViaCost(const E *const prev, const E *const e, const V *const v, double &time, double &effort, double &length) const
Definition: SUMOAbstractRouter.h:179
SUMOAbstractRouter::EdgeInfo::leaveTime
double leaveTime
The time the vehicle leaves the edge.
Definition: SUMOAbstractRouter.h:72
SUMOAbstractRouter::startQuery
void startQuery()
Definition: SUMOAbstractRouter.h:220
SUMOAbstractRouter::EdgeInfo::prohibited
bool prohibited
whether the edge is currently not allowed
Definition: SUMOAbstractRouter.h:81
SUMOAbstractRouter::EdgeInfo::effort
double effort
Effort to reach the edge.
Definition: SUMOAbstractRouter.h:65
SUMOAbstractRouter::myOperation
Operation myOperation
The object's operation to perform.
Definition: SUMOAbstractRouter.h:239
SysUtils::getCurrentMillis
static long getCurrentMillis()
Returns the current time in milliseconds.
Definition: SysUtils.cpp:38
MsgHandler
Definition: MsgHandler.h:38
SUMOAbstractRouter::EdgeInfo::heuristicEffort
double heuristicEffort
Estimated effort to reach the edge (effort + lower bound on remaining effort)
Definition: SUMOAbstractRouter.h:69
SUMOAbstractRouter::computeLooped
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,...
Definition: SUMOAbstractRouter.h:130
SysUtils.h
STEPS2TIME
#define STEPS2TIME(x)
Definition: SUMOTime.h:56
SUMOAbstractRouter::isProhibited
bool isProhibited(const E *const edge, const V *const vehicle) const
Definition: SUMOAbstractRouter.h:159
SUMOAbstractRouter::myHaveRestrictions
const bool myHaveRestrictions
whether edge restrictions need to be considered
Definition: SUMOAbstractRouter.h:251
SUMOAbstractRouter::EdgeInfo::visited
bool visited
whether the edge was already evaluated
Definition: SUMOAbstractRouter.h:78
SUMOAbstractRouter::EdgeInfo
Definition: SUMOAbstractRouter.h:53
SUMOAbstractRouter::setBulkMode
void setBulkMode(const bool mode)
Definition: SUMOAbstractRouter.h:230
SUMOAbstractRouter::myNumQueries
long long int myNumQueries
Definition: SUMOAbstractRouter.h:261
SUMOAbstractRouter::myQueryTimeSum
long long int myQueryTimeSum
Definition: SUMOAbstractRouter.h:264
SUMOAbstractRouter::EdgeInfo::prev
const EdgeInfo * prev
The previous edge.
Definition: SUMOAbstractRouter.h:75
SUMOAbstractRouter::prohibit
virtual void prohibit(const std::vector< E * > &)
Definition: SUMOAbstractRouter.h:163
SUMOAbstractRouter::EdgeInfo::edge
const E *const edge
The current edge.
Definition: SUMOAbstractRouter.h:62
SUMOAbstractRouter::myBulkMode
bool myBulkMode
whether we are currently operating several route queries in a bulk
Definition: SUMOAbstractRouter.h:245
SUMOAbstractRouter::getTravelTime
double getTravelTime(const E *const e, const V *const v, const double t, const double effort) const
Definition: SUMOAbstractRouter.h:165
SUMOAbstractRouter::SUMOAbstractRouter
SUMOAbstractRouter(const std::string &type, bool unbuildIsWarning, Operation operation, Operation ttOperation, const bool havePermissions, const bool haveRestrictions)
Constructor.
Definition: SUMOAbstractRouter.h:99
SUMOAbstractRouter
Definition: SUMOAbstractRouter.h:46
SUMOAbstractRouter::endQuery
void endQuery(int visits)
Definition: SUMOAbstractRouter.h:225
toString
std::string toString(const T &t, std::streamsize accuracy=gPrecision)
Definition: ToString.h:47
SUMOAbstractRouter::clone
virtual SUMOAbstractRouter * clone()=0
SUMOAbstractRouter::myErrorMsgHandler
MsgHandler *const myErrorMsgHandler
the handler for routing errors
Definition: SUMOAbstractRouter.h:236
SUMOAbstractRouter::EdgeInfo::operator=
EdgeInfo & operator=(const EdgeInfo &s)=delete
Invalidated assignment operator.
SUMOAbstractRouter::recomputeCosts
double recomputeCosts(const std::vector< const E * > &edges, const V *const v, SUMOTime msTime, double *lengthp=nullptr) const
Definition: SUMOAbstractRouter.h:195
SUMOAbstractRouter::updateViaEdgeCost
void updateViaEdgeCost(const E *viaEdge, const V *const v, double &time, double &effort, double &length) const
Definition: SUMOAbstractRouter.h:169
SUMOAbstractRouter::EdgeInfo::reset
void reset()
Definition: SUMOAbstractRouter.h:83
MsgHandler::informf
void informf(const std::string &format, T value, Targs... Fargs)
adds a new formatted message
Definition: MsgHandler.h:115
config.h
SUMOAbstractRouter::myQueryStartTime
long long int myQueryStartTime
the time spent querying in milliseconds
Definition: SUMOAbstractRouter.h:263
SVC_IGNORING
@ SVC_IGNORING
vehicles ignoring classes
Definition: SUMOVehicleClass.h:135
WRITE_MESSAGE
#define WRITE_MESSAGE(msg)
Definition: MsgHandler.h:277
SUMOAbstractRouter::myTTOperation
Operation myTTOperation
The object's operation to perform for travel times.
Definition: SUMOAbstractRouter.h:242