Eclipse SUMO - Simulation of Urban MObility
DijkstraRouter.h
Go to the documentation of this file.
1 /****************************************************************************/
2 // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.org/sumo
3 // Copyright (C) 2001-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 // Dijkstra shortest path algorithm using travel time or other values
21 /****************************************************************************/
22 #pragma once
23 #include <config.h>
24 
25 #include <cassert>
26 #include <string>
27 #include <functional>
28 #include <vector>
29 #include <set>
30 #include <limits>
31 #include <algorithm>
32 #include <iterator>
33 #include <utils/common/ToString.h>
35 #include <utils/common/StdDefs.h>
36 #include "EffortCalculator.h"
37 #include "SUMOAbstractRouter.h"
38 
39 //#define DijkstraRouter_DEBUG_QUERY
40 //#define DijkstraRouter_DEBUG_QUERY_PERF
41 
42 // ===========================================================================
43 // class definitions
44 // ===========================================================================
58 template<class E, class V>
59 class DijkstraRouter : public SUMOAbstractRouter<E, V> {
60 public:
66  public:
68  bool operator()(const typename SUMOAbstractRouter<E, V>::EdgeInfo* nod1, const typename SUMOAbstractRouter<E, V>::EdgeInfo* nod2) const {
69  if (nod1->effort == nod2->effort) {
70  return nod1->edge->getNumericalID() > nod2->edge->getNumericalID();
71  }
72  return nod1->effort > nod2->effort;
73  }
74  };
75 
76 
78  DijkstraRouter(const std::vector<E*>& edges, bool unbuildIsWarning, typename SUMOAbstractRouter<E, V>::Operation effortOperation,
79  typename SUMOAbstractRouter<E, V>::Operation ttOperation = nullptr, bool silent = false, EffortCalculator* calc = nullptr,
80  const bool havePermissions = false, const bool haveRestrictions = false) :
81  SUMOAbstractRouter<E, V>("DijkstraRouter", unbuildIsWarning, effortOperation, ttOperation, havePermissions, haveRestrictions),
82  mySilent(silent), myExternalEffort(calc) {
83  for (typename std::vector<E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
84  myEdgeInfos.push_back(typename SUMOAbstractRouter<E, V>::EdgeInfo(*i));
85  }
86  }
87 
89  virtual ~DijkstraRouter() { }
90 
95  clone->setAutoBulkMode(this->myAutoBulkMode);
96  return clone;
97  }
98 
99  void init() {
100  // all EdgeInfos touched in the previous query are either in myFrontierList or myFound: clean those up
101  for (auto& edgeInfo : myFrontierList) {
102  edgeInfo->reset();
103  }
104  myFrontierList.clear();
105  for (auto& edgeInfo : myFound) {
106  edgeInfo->reset();
107  }
108  myFound.clear();
109  }
110 
111 
114  bool compute(const E* from, const E* to, const V* const vehicle,
115  SUMOTime msTime, std::vector<const E*>& into, bool silent = false) {
116  assert(from != nullptr && (vehicle == nullptr || to != nullptr));
117  // check whether from and to can be used
118  if (myEdgeInfos[from->getNumericalID()].prohibited || this->isProhibited(from, vehicle)) {
119  if (!silent) {
120  this->myErrorMsgHandler->inform("Vehicle '" + Named::getIDSecure(vehicle) + "' is not allowed on source edge '" + from->getID() + "'.");
121  }
122  return false;
123  }
124  if (to != nullptr && (myEdgeInfos[to->getNumericalID()].prohibited || this->isProhibited(to, vehicle))) {
125  if (!silent) {
126  this->myErrorMsgHandler->inform("Vehicle '" + Named::getIDSecure(vehicle) + "' is not allowed on destination edge '" + to->getID() + "'.");
127  }
128  return false;
129  }
130  double length = 0.; // dummy for the via edge cost update
131  this->startQuery();
132 #ifdef DijkstraRouter_DEBUG_QUERY
133  std::cout << "DEBUG: starting search for '" << Named::getIDSecure(vehicle) << "' time: " << STEPS2TIME(msTime) << "\n";
134 #endif
135  const SUMOVehicleClass vClass = vehicle == nullptr ? SVC_IGNORING : vehicle->getVClass();
136  std::tuple<const E*, const V*, SUMOTime> query = std::make_tuple(from, vehicle, msTime);
137  if (this->myBulkMode || (this->myAutoBulkMode && query == myLastQuery)) {
138  const auto& toInfo = myEdgeInfos[to->getNumericalID()];
139  if (toInfo.visited) {
140  buildPathFrom(&toInfo, into);
141  this->endQuery(1);
142  return true;
143  }
144  } else {
145  init();
146  // add begin node
147  auto* const fromInfo = &(myEdgeInfos[from->getNumericalID()]);
148  fromInfo->effort = 0.;
149  fromInfo->prev = nullptr;
150  fromInfo->leaveTime = STEPS2TIME(msTime);
151  if (myExternalEffort != nullptr) {
152  myExternalEffort->setInitialState(fromInfo->edge->getNumericalID());
153  }
154  myFrontierList.push_back(fromInfo);
155  }
156  myLastQuery = query;
157  // loop
158  int num_visited = 0;
159  while (!myFrontierList.empty()) {
160  num_visited += 1;
161  // use the node with the minimal length
162  auto* const minimumInfo = myFrontierList.front();
163  const E* const minEdge = minimumInfo->edge;
164 #ifdef DijkstraRouter_DEBUG_QUERY
165  std::cout << "DEBUG: hit '" << minEdge->getID() << "' Eff: " << minimumInfo->effort << ", Leave: " << minimumInfo->leaveTime << " Q: ";
166  for (auto& it : myFrontierList) {
167  std::cout << it->effort << "," << it->edge->getID() << " ";
168  }
169  std::cout << "\n";
170 #endif
171  // check whether the destination node was already reached
172  if (minEdge == to) {
173  //propagate last external effort state to destination edge
174  if (myExternalEffort != nullptr) {
175  myExternalEffort->update(minEdge->getNumericalID(), minimumInfo->prev->edge->getNumericalID(), minEdge->getLength());
176  }
177  buildPathFrom(minimumInfo, into);
178  this->endQuery(num_visited);
179 #ifdef DijkstraRouter_DEBUG_QUERY_PERF
180  std::cout << "visited " + toString(num_visited) + " edges (final path length=" + toString(into.size()) + " edges=" + toString(into) + ")\n";
181 #endif
182  return true;
183  }
184  std::pop_heap(myFrontierList.begin(), myFrontierList.end(), myComparator);
185  myFrontierList.pop_back();
186  myFound.push_back(minimumInfo);
187  minimumInfo->visited = true;
188  const double effortDelta = this->getEffort(minEdge, vehicle, minimumInfo->leaveTime);
189  const double leaveTime = minimumInfo->leaveTime + this->getTravelTime(minEdge, vehicle, minimumInfo->leaveTime, effortDelta);
190  if (myExternalEffort != nullptr) {
191  myExternalEffort->update(minEdge->getNumericalID(), minimumInfo->prev->edge->getNumericalID(), minEdge->getLength());
192  }
193  // check all ways from the node with the minimal length
194  for (const std::pair<const E*, const E*>& follower : minEdge->getViaSuccessors(vClass)) {
195  auto* const followerInfo = &(myEdgeInfos[follower.first->getNumericalID()]);
196  // check whether it can be used
197  if (followerInfo->prohibited || this->isProhibited(follower.first, vehicle)) {
198  continue;
199  }
200  double effort = minimumInfo->effort + effortDelta;
201  double time = leaveTime;
202  this->updateViaEdgeCost(follower.second, vehicle, time, effort, length);
203  assert(effort >= minimumInfo->effort);
204  assert(time >= minimumInfo->leaveTime);
205  const double oldEffort = followerInfo->effort;
206  if (!followerInfo->visited && effort < oldEffort) {
207  followerInfo->effort = effort;
208  followerInfo->leaveTime = time;
209  followerInfo->prev = minimumInfo;
210  if (oldEffort == std::numeric_limits<double>::max()) {
211  myFrontierList.push_back(followerInfo);
212  std::push_heap(myFrontierList.begin(), myFrontierList.end(), myComparator);
213  } else {
214  std::push_heap(myFrontierList.begin(),
215  std::find(myFrontierList.begin(), myFrontierList.end(), followerInfo) + 1,
216  myComparator);
217  }
218  }
219  }
220  }
221  this->endQuery(num_visited);
222 #ifdef DijkstraRouter_DEBUG_QUERY_PERF
223  std::cout << "visited " + toString(num_visited) + " edges (unsuccessful path length: " + toString(into.size()) + ")\n";
224 #endif
225  if (to != nullptr && !mySilent && !silent) {
226  this->myErrorMsgHandler->informf("No connection between edge '%' and edge '%' found.", from->getID(), to->getID());
227  }
228  return false;
229  }
230 
231 
232  void prohibit(const std::vector<E*>& toProhibit) {
233  for (E* const edge : this->myProhibited) {
234  myEdgeInfos[edge->getNumericalID()].prohibited = false;
235  }
236  for (E* const edge : toProhibit) {
237  myEdgeInfos[edge->getNumericalID()].prohibited = true;
238  }
239  this->myProhibited = toProhibit;
240  }
241 
242 
244  void buildPathFrom(const typename SUMOAbstractRouter<E, V>::EdgeInfo* rbegin, std::vector<const E*>& edges) {
245  std::vector<const E*> tmp;
246  while (rbegin != 0) {
247  tmp.push_back(rbegin->edge);
248  rbegin = rbegin->prev;
249  }
250  std::copy(tmp.rbegin(), tmp.rend(), std::back_inserter(edges));
251  }
252 
253  const typename SUMOAbstractRouter<E, V>::EdgeInfo& getEdgeInfo(int index) const {
254  return myEdgeInfos[index];
255  }
256 
257 private:
258  DijkstraRouter(const std::vector<typename SUMOAbstractRouter<E, V>::EdgeInfo>& edgeInfos, bool unbuildIsWarning,
259  typename SUMOAbstractRouter<E, V>::Operation effortOperation, typename SUMOAbstractRouter<E, V>::Operation ttOperation, bool silent, EffortCalculator* calc,
260  const bool havePermissions, const bool haveRestrictions) :
261  SUMOAbstractRouter<E, V>("DijkstraRouter", unbuildIsWarning, effortOperation, ttOperation, havePermissions, haveRestrictions),
262  mySilent(silent),
263  myExternalEffort(calc) {
264  for (const auto& edgeInfo : edgeInfos) {
265  myEdgeInfos.push_back(typename SUMOAbstractRouter<E, V>::EdgeInfo(edgeInfo.edge));
266  }
267  }
268 
269 private:
271  bool mySilent;
272 
274  std::tuple<const E*, const V*, SUMOTime> myLastQuery;
275 
277 
279  std::vector<typename SUMOAbstractRouter<E, V>::EdgeInfo> myEdgeInfos;
280 
282  std::vector<typename SUMOAbstractRouter<E, V>::EdgeInfo*> myFrontierList;
284  std::vector<typename SUMOAbstractRouter<E, V>::EdgeInfo*> myFound;
285 
287 };
#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
std::string toString(const T &t, std::streamsize accuracy=gPrecision)
Definition: ToString.h:44
bool operator()(const typename SUMOAbstractRouter< E, V >::EdgeInfo *nod1, const typename SUMOAbstractRouter< E, V >::EdgeInfo *nod2) const
Comparing method.
Computes the shortest path through a network using the Dijkstra algorithm.
void buildPathFrom(const typename SUMOAbstractRouter< E, V >::EdgeInfo *rbegin, std::vector< const E * > &edges)
Builds the path from marked edges.
std::vector< typename SUMOAbstractRouter< E, V >::EdgeInfo * > myFound
list of visited Edges (for resetting)
bool mySilent
whether to suppress warning/error if no route was found
std::tuple< const E *, const V *, SUMOTime > myLastQuery
cache of the last query to enable automated bulk routing
EffortCalculator *const myExternalEffort
const SUMOAbstractRouter< E, V >::EdgeInfo & getEdgeInfo(int index) const
bool compute(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 The definition of...
void prohibit(const std::vector< E * > &toProhibit)
DijkstraRouter(const std::vector< E * > &edges, bool unbuildIsWarning, typename SUMOAbstractRouter< E, V >::Operation effortOperation, typename SUMOAbstractRouter< E, V >::Operation ttOperation=nullptr, bool silent=false, EffortCalculator *calc=nullptr, const bool havePermissions=false, const bool haveRestrictions=false)
Constructor.
EdgeInfoByEffortComparator myComparator
std::vector< typename SUMOAbstractRouter< E, V >::EdgeInfo > myEdgeInfos
The container of edge information.
virtual ~DijkstraRouter()
Destructor.
std::vector< typename SUMOAbstractRouter< E, V >::EdgeInfo * > myFrontierList
A container for reusage of the min edge heap.
virtual SUMOAbstractRouter< E, V > * clone()
DijkstraRouter(const std::vector< typename SUMOAbstractRouter< E, V >::EdgeInfo > &edgeInfos, bool unbuildIsWarning, typename SUMOAbstractRouter< E, V >::Operation effortOperation, typename SUMOAbstractRouter< E, V >::Operation ttOperation, bool silent, EffortCalculator *calc, const bool havePermissions, const bool haveRestrictions)
the effort calculator interface
virtual void setInitialState(const int edge)=0
virtual void update(const int edge, const int prev, const double length)=0
virtual void inform(std::string msg, bool addType=true)
adds a new error to the list
Definition: MsgHandler.cpp:117
static MsgHandler * getWarningInstance()
Returns the instance to add warnings to.
Definition: MsgHandler.cpp:67
void informf(const std::string &format, T value, Targs... Fargs)
adds a new formatted message
Definition: MsgHandler.h:113
static std::string getIDSecure(const T *obj, const std::string &fallBack="NULL")
get an identifier for Named-like object which may be Null
Definition: Named.h:66
const E *const edge
The current edge.
double effort
Effort to reach the edge.
const EdgeInfo * prev
The previous edge.
Operation myTTOperation
The object's operation to perform for travel times.
MsgHandler *const myErrorMsgHandler
the handler for routing errors
std::vector< E * > myProhibited
const bool myHavePermissions
whether edge permissions need to be considered
bool myBulkMode
whether we are currently operating several route queries in a bulk
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
double getEffort(const E *const e, const V *const v, double t) const
void updateViaEdgeCost(const E *viaEdge, const V *const v, double &time, double &effort, double &length) const
const bool myHaveRestrictions
whether edge restrictions need to be considered
bool myAutoBulkMode
whether we are currently trying to detect bulk mode automatically
void endQuery(int visits)