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 /****************************************************************************/
17 // An abstract router base class
18 /****************************************************************************/
19 #ifndef SUMOAbstractRouter_h
20 #define SUMOAbstractRouter_h
21 
22 
23 // ===========================================================================
24 // included modules
25 // ===========================================================================
26 #include <config.h>
27 
28 #include <string>
29 #include <vector>
30 #include <algorithm>
31 #include <iterator>
32 #include <assert.h>
33 #include <utils/common/SysUtils.h>
35 #include <utils/common/SUMOTime.h>
36 #include <utils/common/ToString.h>
37 
38 
39 // ===========================================================================
40 // class definitions
41 // ===========================================================================
46 template<class E, class V>
48 public:
54  class EdgeInfo {
55  public:
57  EdgeInfo(const E* const e)
58  : edge(e), effort(std::numeric_limits<double>::max()),
59  heuristicEffort(std::numeric_limits<double>::max()),
60  leaveTime(0.), prev(nullptr), visited(false) {}
61 
63  const E* const edge;
64 
66  double effort;
67 
69  // only used by A*
71 
73  double leaveTime;
74 
76  const EdgeInfo* prev;
77 
79  bool visited;
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 = nullptr, Operation ttOperation = nullptr) :
98  myErrorMsgHandler(unbuildIsWarning ? MsgHandler::getWarningInstance() : MsgHandler::getErrorInstance()),
99  myOperation(operation), myTTOperation(ttOperation),
100  myBulkMode(false),
101  myType(type),
102  myQueryVisits(0),
103  myNumQueries(0),
104  myQueryStartTime(0),
105  myQueryTimeSum(0) {
106  }
107 
110  if (myNumQueries > 0) {
111  WRITE_MESSAGE(myType + " answered " + toString(myNumQueries) + " queries and explored " + toString(double(myQueryVisits) / myNumQueries) + " edges on average.");
112  WRITE_MESSAGE(myType + " spent " + toString(myQueryTimeSum) + "ms answering queries (" + toString(double(myQueryTimeSum) / myNumQueries) + "ms on average).");
113  }
114  }
115 
116  virtual SUMOAbstractRouter* clone() = 0;
117 
120  virtual bool compute(const E* from, const E* to, const V* const vehicle,
121  SUMOTime msTime, std::vector<const E*>& into, bool silent = false) = 0;
122 
125  bool computeLooped(const E* from, const E* to, const V* const vehicle,
126  SUMOTime msTime, std::vector<const E*>& into, bool silent = false) {
127  if (from != to) {
128  return compute(from, to, vehicle, msTime, into, silent);
129  }
130  double minEffort = std::numeric_limits<double>::max();
131  std::vector<const E*> best;
132  const SUMOVehicleClass vClass = vehicle == 0 ? SVC_IGNORING : vehicle->getVClass();
133  for (const std::pair<const E*, const E*>& follower : from->getViaSuccessors(vClass)) {
134  std::vector<const E*> tmp;
135  compute(follower.first, to, vehicle, msTime, tmp, true);
136  if (tmp.size() > 0) {
137  double effort = recomputeCosts(tmp, vehicle, msTime);
138  if (effort < minEffort) {
139  minEffort = effort;
140  best = tmp;
141  }
142  }
143  }
144  if (minEffort != std::numeric_limits<double>::max()) {
145  into.push_back(from);
146  std::copy(best.begin(), best.end(), std::back_inserter(into));
147  return true;
148  } else if (!silent && myErrorMsgHandler != nullptr) {
149  myErrorMsgHandler->inform("No connection between edge '" + from->getID() + "' and edge '" + to->getID() + "' found.");
150  }
151  return false;
152  }
153 
154  virtual bool isProhibited(const E* const /* edge */, const V* const /* vehicle */) const {
155  return false;
156  }
157 
158 
159  inline double getTravelTime(const E* const e, const V* const v, const double t, const double effort) const {
160  return myTTOperation == nullptr ? effort : (*myTTOperation)(e, v, t);
161  }
162 
163  inline void updateViaEdgeCost(const E* viaEdge, const V* const v, double& time, double& effort, double& length) const {
164  while (viaEdge != nullptr && viaEdge->isInternal()) {
165  const double viaEffortDelta = this->getEffort(viaEdge, v, time);
166  time += getTravelTime(viaEdge, v, time, viaEffortDelta);
167  effort += viaEffortDelta;
168  length += viaEdge->getLength();
169  viaEdge = viaEdge->getViaSuccessors().front().second;
170  }
171  }
172 
173  inline void updateViaCost(const E* const prev, const E* const e, const V* const v, double& time, double& effort, double& length) const {
174  if (prev != nullptr) {
175  for (const std::pair<const E*, const E*>& follower : prev->getViaSuccessors()) {
176  if (follower.first == e) {
177  updateViaEdgeCost(follower.second, v, time, effort, length);
178  break;
179  }
180  }
181  }
182  const double effortDelta = this->getEffort(e, v, time);
183  effort += effortDelta;
184  time += getTravelTime(e, v, time, effortDelta);
185  length += e->getLength();
186  }
187 
188 
189  inline double recomputeCosts(const std::vector<const E*>& edges, const V* const v, SUMOTime msTime, double* lengthp = nullptr) const {
190  double time = STEPS2TIME(msTime);
191  double effort = 0.;
192  double length = 0.;
193  if (lengthp == nullptr) {
194  lengthp = &length;
195  } else {
196  *lengthp = 0.;
197  }
198  const E* prev = nullptr;
199  for (const E* const e : edges) {
200  if (isProhibited(e, v)) {
201  return -1;
202  }
203  updateViaCost(prev, e, v, time, effort, *lengthp);
204  prev = e;
205  }
206  return effort;
207  }
208 
209 
210  inline double getEffort(const E* const e, const V* const v, double t) const {
211  return (*myOperation)(e, v, t);
212  }
213 
214  inline void startQuery() {
215  myNumQueries++;
217  }
218 
219  inline void endQuery(int visits) {
220  myQueryVisits += visits;
222  }
223 
224  void setBulkMode(const bool mode) {
225  myBulkMode = mode;
226  }
227 
228 protected:
231 
234 
237 
240 
241 private:
243  const std::string myType;
244 
246  long long int myQueryVisits;
247  long long int myNumQueries;
249  long long int myQueryStartTime;
250  long long int myQueryTimeSum;
251 private:
254 };
255 
256 
257 template<class E, class V>
259 public:
261  SUMOAbstractRouterPermissions(const std::string& type, bool unbuildIsWarning,
262  typename SUMOAbstractRouter<E, V>::Operation operation = nullptr, typename SUMOAbstractRouter<E, V>::Operation ttOperation = nullptr) :
263  SUMOAbstractRouter<E, V>(type, unbuildIsWarning, operation, ttOperation) {
264  }
265 
268  }
269 
270  bool isProhibited(const E* const edge, const V* const vehicle) const {
271  if (std::find(myProhibited.begin(), myProhibited.end(), edge) != myProhibited.end()) {
272  return true;
273  }
274  return edge->prohibits(vehicle);
275  }
276 
277  void prohibit(const std::vector<E*>& toProhibit) {
278  myProhibited = toProhibit;
279  }
280 
281 protected:
282  std::vector<E*> myProhibited;
283 
284 };
285 
286 
287 #endif
288 
289 /****************************************************************************/
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:246
SUMOVehicleClass
SUMOVehicleClass
Definition of vehicle classes to differ between different lane usage and authority types.
Definition: SUMOVehicleClass.h:134
ToString.h
SUMOAbstractRouter::myType
const std::string myType
the type of this router
Definition: SUMOAbstractRouter.h:243
SUMOAbstractRouter::operator=
SUMOAbstractRouter & operator=(const SUMOAbstractRouter &s)
Invalidated assignment operator.
SUMOTime.h
SUMOAbstractRouter::~SUMOAbstractRouter
virtual ~SUMOAbstractRouter()
Destructor.
Definition: SUMOAbstractRouter.h:109
MsgHandler.h
SUMOAbstractRouterPermissions::isProhibited
bool isProhibited(const E *const edge, const V *const vehicle) const
Definition: SUMOAbstractRouter.h:270
SUMOAbstractRouter::getEffort
double getEffort(const E *const e, const V *const v, double t) const
Definition: SUMOAbstractRouter.h:210
MsgHandler::inform
virtual void inform(std::string msg, bool addType=true)
adds a new error to the list
Definition: MsgHandler.cpp:118
SUMOTime
long long int SUMOTime
Definition: SUMOTime.h:35
SUMOAbstractRouter::EdgeInfo::EdgeInfo
EdgeInfo(const E *const e)
Constructor.
Definition: SUMOAbstractRouter.h:57
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:173
SUMOAbstractRouter::EdgeInfo::leaveTime
double leaveTime
The time the vehicle leaves the edge.
Definition: SUMOAbstractRouter.h:73
SUMOAbstractRouter::startQuery
void startQuery()
Definition: SUMOAbstractRouter.h:214
SUMOAbstractRouter::EdgeInfo::effort
double effort
Effort to reach the edge.
Definition: SUMOAbstractRouter.h:66
SUMOAbstractRouter::myOperation
Operation myOperation
The object's operation to perform.
Definition: SUMOAbstractRouter.h:233
SysUtils::getCurrentMillis
static long getCurrentMillis()
Returns the current time in milliseconds.
Definition: SysUtils.cpp:39
MsgHandler
Definition: MsgHandler.h:44
SUMOAbstractRouter::EdgeInfo::heuristicEffort
double heuristicEffort
Estimated effort to reach the edge (effort + lower bound on remaining effort)
Definition: SUMOAbstractRouter.h:70
SUMOAbstractRouterPermissions
Definition: SUMOAbstractRouter.h:258
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:125
SysUtils.h
STEPS2TIME
#define STEPS2TIME(x)
Definition: SUMOTime.h:57
SUMOAbstractRouter::EdgeInfo::visited
bool visited
The previous edge.
Definition: SUMOAbstractRouter.h:79
SUMOAbstractRouter::EdgeInfo
Definition: SUMOAbstractRouter.h:54
SUMOAbstractRouter::setBulkMode
void setBulkMode(const bool mode)
Definition: SUMOAbstractRouter.h:224
SUMOAbstractRouter::myNumQueries
long long int myNumQueries
Definition: SUMOAbstractRouter.h:247
SUMOAbstractRouter::myQueryTimeSum
long long int myQueryTimeSum
Definition: SUMOAbstractRouter.h:250
SUMOAbstractRouter::EdgeInfo::prev
const EdgeInfo * prev
The previous edge.
Definition: SUMOAbstractRouter.h:76
SUMOAbstractRouter::EdgeInfo::edge
const E *const edge
The current edge.
Definition: SUMOAbstractRouter.h:63
SUMOAbstractRouter::myBulkMode
bool myBulkMode
whether we are currently operating several route queries in a bulk
Definition: SUMOAbstractRouter.h:239
SUMOAbstractRouter::getTravelTime
double getTravelTime(const E *const e, const V *const v, const double t, const double effort) const
Definition: SUMOAbstractRouter.h:159
SUMOAbstractRouter
Definition: SUMOAbstractRouter.h:47
SUMOAbstractRouter::endQuery
void endQuery(int visits)
Definition: SUMOAbstractRouter.h:219
toString
std::string toString(const T &t, std::streamsize accuracy=gPrecision)
Definition: ToString.h:48
SUMOAbstractRouter::clone
virtual SUMOAbstractRouter * clone()=0
SUMOAbstractRouter::SUMOAbstractRouter
SUMOAbstractRouter(const std::string &type, bool unbuildIsWarning, Operation operation=nullptr, Operation ttOperation=nullptr)
Constructor.
Definition: SUMOAbstractRouter.h:97
SUMOAbstractRouter::myErrorMsgHandler
MsgHandler *const myErrorMsgHandler
the handler for routing errors
Definition: SUMOAbstractRouter.h:230
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:189
SUMOAbstractRouter::updateViaEdgeCost
void updateViaEdgeCost(const E *viaEdge, const V *const v, double &time, double &effort, double &length) const
Definition: SUMOAbstractRouter.h:163
SUMOAbstractRouter::EdgeInfo::reset
void reset()
Definition: SUMOAbstractRouter.h:81
config.h
SUMOAbstractRouter::isProhibited
virtual bool isProhibited(const E *const, const V *const) const
Definition: SUMOAbstractRouter.h:154
SUMOAbstractRouterPermissions::prohibit
void prohibit(const std::vector< E * > &toProhibit)
Definition: SUMOAbstractRouter.h:277
SUMOAbstractRouterPermissions::SUMOAbstractRouterPermissions
SUMOAbstractRouterPermissions(const std::string &type, bool unbuildIsWarning, typename SUMOAbstractRouter< E, V >::Operation operation=nullptr, typename SUMOAbstractRouter< E, V >::Operation ttOperation=nullptr)
Constructor.
Definition: SUMOAbstractRouter.h:261
SUMOAbstractRouterPermissions::myProhibited
std::vector< E * > myProhibited
Definition: SUMOAbstractRouter.h:282
SUMOAbstractRouter::myQueryStartTime
long long int myQueryStartTime
the time spent querying in milliseconds
Definition: SUMOAbstractRouter.h:249
SVC_IGNORING
vehicles ignoring classes
Definition: SUMOVehicleClass.h:136
SUMOAbstractRouterPermissions::~SUMOAbstractRouterPermissions
virtual ~SUMOAbstractRouterPermissions()
Destructor.
Definition: SUMOAbstractRouter.h:267
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:94
WRITE_MESSAGE
#define WRITE_MESSAGE(msg)
Definition: MsgHandler.h:240
SUMOAbstractRouter::myTTOperation
Operation myTTOperation
The object's operation to perform for travel times.
Definition: SUMOAbstractRouter.h:236