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-2018 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 // Dijkstra shortest path algorithm using travel time or other values
18 /****************************************************************************/
19 #ifndef DijkstraRouter_h
20 #define DijkstraRouter_h
21 
22 
23 // ===========================================================================
24 // included modules
25 // ===========================================================================
26 #include <config.h>
27 
28 #include <cassert>
29 #include <string>
30 #include <functional>
31 #include <vector>
32 #include <set>
33 #include <limits>
34 #include <algorithm>
35 #include <iterator>
36 #include <utils/common/ToString.h>
38 #include <utils/common/StdDefs.h>
39 #include "EffortCalculator.h"
40 #include "SUMOAbstractRouter.h"
41 
42 //#define DijkstraRouter_DEBUG_QUERY
43 //#define DijkstraRouter_DEBUG_QUERY_PERF
44 
45 // ===========================================================================
46 // class definitions
47 // ===========================================================================
62 template<class E, class V, class BASE>
63 class DijkstraRouter : public BASE {
64 public:
70  public:
72  bool operator()(const typename BASE::EdgeInfo* nod1, const typename BASE::EdgeInfo* nod2) const {
73  if (nod1->effort == nod2->effort) {
74  return nod1->edge->getNumericalID() > nod2->edge->getNumericalID();
75  }
76  return nod1->effort > nod2->effort;
77  }
78  };
79 
80 
82  DijkstraRouter(const std::vector<E*>& edges, bool unbuildIsWarning, typename BASE::Operation effortOperation,
83  typename BASE::Operation ttOperation = nullptr, bool silent = false, EffortCalculator* calc = nullptr) :
84  BASE("DijkstraRouter", effortOperation, ttOperation),
85  myErrorMsgHandler(unbuildIsWarning ? MsgHandler::getWarningInstance() : MsgHandler::getErrorInstance()),
86  mySilent(silent), myExternalEffort(calc) {
87  for (typename std::vector<E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
88  myEdgeInfos.push_back(typename BASE::EdgeInfo(*i));
89  }
90  }
91 
93  virtual ~DijkstraRouter() { }
94 
96  return new DijkstraRouter<E, V, BASE>(myEdgeInfos, myErrorMsgHandler == MsgHandler::getWarningInstance(), this->myOperation, this->myTTOperation, mySilent, myExternalEffort);
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  virtual bool compute(const E* from, const E* to, const V* const vehicle,
115  SUMOTime msTime, std::vector<const E*>& into) {
116  assert(from != 0 && (vehicle == 0 || to != 0));
117  // check whether from and to can be used
118  if (this->isProhibited(from, vehicle)) {
119  myErrorMsgHandler->inform("Vehicle '" + vehicle->getID() + "' is not allowed on source edge '" + from->getID() + "'.");
120  return false;
121  }
122  if (this->isProhibited(to, vehicle)) {
123  myErrorMsgHandler->inform("Vehicle '" + vehicle->getID() + "' is not allowed on destination edge '" + to->getID() + "'.");
124  return false;
125  }
126  this->startQuery();
127 #ifdef DijkstraRouter_DEBUG_QUERY
128  std::cout << "DEBUG: starting search for '" << vehicle->getID() << "' time: " << STEPS2TIME(msTime) << "\n";
129 #endif
130  const SUMOVehicleClass vClass = vehicle == 0 ? SVC_IGNORING : vehicle->getVClass();
131  if (this->myBulkMode) {
132  const auto& toInfo = myEdgeInfos[to->getNumericalID()];
133  if (toInfo.visited) {
134  buildPathFrom(&toInfo, into);
135  this->endQuery(1);
136  return true;
137  }
138  } else {
139  init();
140  // add begin node
141  auto* const fromInfo = &(myEdgeInfos[from->getNumericalID()]);
142  fromInfo->effort = 0.;
143  fromInfo->prev = nullptr;
144  fromInfo->leaveTime = STEPS2TIME(msTime);
145  myFrontierList.push_back(fromInfo);
146  }
147  // loop
148  int num_visited = 0;
149  while (!myFrontierList.empty()) {
150  num_visited += 1;
151  // use the node with the minimal length
152  auto* const minimumInfo = myFrontierList.front();
153  const E* const minEdge = minimumInfo->edge;
154 #ifdef DijkstraRouter_DEBUG_QUERY
155  std::cout << "DEBUG: hit '" << minEdge->getID() << "' Eff: " << minimumInfo->effort << ", Leave: " << minimumInfo->leaveTime << " Q: ";
156  for (auto& it : myFrontierList) {
157  std::cout << it->effort << "," << it->edge->getID() << " ";
158  }
159  std::cout << "\n";
160 #endif
161  // check whether the destination node was already reached
162  if (minEdge == to) {
163  buildPathFrom(minimumInfo, into);
164  this->endQuery(num_visited);
165 #ifdef DijkstraRouter_DEBUG_QUERY_PERF
166  std::cout << "visited " + toString(num_visited) + " edges (final path length=" + toString(into.size()) + " edges=" + toString(into) + ")\n";
167 #endif
168  return true;
169  }
170  pop_heap(myFrontierList.begin(), myFrontierList.end(), myComparator);
171  myFrontierList.pop_back();
172  myFound.push_back(minimumInfo);
173  minimumInfo->visited = true;
174  const E* viaEdge = minimumInfo->via;
175  double effort = minimumInfo->effort;
176  double leaveTime = minimumInfo->leaveTime;
177  while (viaEdge != nullptr && viaEdge->isInternal()) {
178  const double viaEffortDelta = this->getEffort(viaEdge, vehicle, leaveTime);
179  leaveTime += this->getTravelTime(viaEdge, vehicle, leaveTime, viaEffortDelta);
180  effort += viaEffortDelta;
181  viaEdge = viaEdge->getViaSuccessors().front().first;
182  }
183  const double effortDelta = this->getEffort(minEdge, vehicle, leaveTime);
184  leaveTime += this->getTravelTime(minEdge, vehicle, minimumInfo->leaveTime, effortDelta);
185  effort += effortDelta;
186  if (myExternalEffort != nullptr) {
187  myExternalEffort->update(minEdge->getNumericalID(), minimumInfo->prev->edge->getNumericalID(), minEdge->getLength());
188  }
189  assert(effort >= minimumInfo->effort);
190  assert(leaveTime >= minimumInfo->leaveTime);
191  // check all ways from the node with the minimal length
192  for (const std::pair<const E*, const E*>& follower : minEdge->getViaSuccessors(vClass)) {
193  auto* const followerInfo = &(myEdgeInfos[follower.first->getNumericalID()]);
194  // check whether it can be used
195  if (this->isProhibited(follower.first, vehicle)) {
196  continue;
197  }
198  const double oldEffort = followerInfo->effort;
199  if (!followerInfo->visited && effort < oldEffort) {
200  followerInfo->effort = effort;
201  followerInfo->leaveTime = leaveTime;
202  followerInfo->prev = minimumInfo;
203  followerInfo->via = follower.second;
204  if (oldEffort == std::numeric_limits<double>::max()) {
205  myFrontierList.push_back(followerInfo);
206  push_heap(myFrontierList.begin(), myFrontierList.end(), myComparator);
207  } else {
208  push_heap(myFrontierList.begin(),
209  find(myFrontierList.begin(), myFrontierList.end(), followerInfo) + 1,
210  myComparator);
211  }
212  }
213  }
214  }
215  this->endQuery(num_visited);
216 #ifdef DijkstraRouter_DEBUG_QUERY_PERF
217  std::cout << "visited " + toString(num_visited) + " edges (unsuccessful path length: " + toString(into.size()) + ")\n";
218 #endif
219  if (to != 0 && !mySilent) {
220  myErrorMsgHandler->inform("No connection between edge '" + from->getID() + "' and edge '" + to->getID() + "' found.");
221  }
222  return false;
223  }
224 
225 
227  void buildPathFrom(const typename BASE::EdgeInfo* rbegin, std::vector<const E*>& edges) {
228  std::vector<const E*> tmp;
229  while (rbegin != 0) {
230  tmp.push_back(rbegin->edge);
231  rbegin = rbegin->prev;
232  }
233  std::copy(tmp.rbegin(), tmp.rend(), std::back_inserter(edges));
234  }
235 
236  const typename BASE::EdgeInfo& getEdgeInfo(int index) const {
237  return myEdgeInfos[index];
238  }
239 
240 private:
241  DijkstraRouter(const std::vector<typename BASE::EdgeInfo>& edgeInfos, bool unbuildIsWarning,
242  typename BASE::Operation effortOperation, typename BASE::Operation ttOperation, bool silent, EffortCalculator* calc) :
243  BASE("DijkstraRouter", effortOperation, ttOperation),
244  myErrorMsgHandler(unbuildIsWarning ? MsgHandler::getWarningInstance() : MsgHandler::getErrorInstance()),
245  mySilent(silent),
246  myExternalEffort(calc) {
247  for (const auto& edgeInfo : edgeInfos) {
248  myEdgeInfos.push_back(typename BASE::EdgeInfo(edgeInfo.edge));
249  }
250  }
251 
252 private:
255 
257  bool mySilent;
258 
260 
262  std::vector<typename BASE::EdgeInfo> myEdgeInfos;
263 
265  std::vector<typename BASE::EdgeInfo*> myFrontierList;
267  std::vector<typename BASE::EdgeInfo*> myFound;
268 
270 };
271 
272 
273 #endif
274 
275 /****************************************************************************/
static MsgHandler * getWarningInstance()
Returns the instance to add warnings to.
Definition: MsgHandler.cpp:67
long long int SUMOTime
Definition: SUMOTime.h:36
std::vector< typename BASE::EdgeInfo * > myFound
list of visited Edges (for resetting)
SUMOVehicleClass
Definition of vehicle classes to differ between different lane usage and authority types...
void buildPathFrom(const typename BASE::EdgeInfo *rbegin, std::vector< const E *> &edges)
Builds the path from marked edges.
DijkstraRouter(const std::vector< typename BASE::EdgeInfo > &edgeInfos, bool unbuildIsWarning, typename BASE::Operation effortOperation, typename BASE::Operation ttOperation, bool silent, EffortCalculator *calc)
bool operator()(const typename BASE::EdgeInfo *nod1, const typename BASE::EdgeInfo *nod2) const
Comparing method.
virtual bool compute(const E *from, const E *to, const V *const vehicle, SUMOTime msTime, std::vector< const E *> &into)
Builds the route between the given edges using the minimum effort at the given time The definition of...
MsgHandler *const myErrorMsgHandler
the handler for routing errors
virtual SUMOAbstractRouter< E, V > * clone()
std::vector< typename BASE::EdgeInfo * > myFrontierList
A container for reusage of the min edge heap.
the effort calculator interface
EffortCalculator *const myExternalEffort
std::string toString(const T &t, std::streamsize accuracy=gPrecision)
Definition: ToString.h:49
virtual void update(const int edge, const int prev, const double length)=0
Computes the shortest path through a network using the Dijkstra algorithm.
std::vector< typename BASE::EdgeInfo > myEdgeInfos
The container of edge information.
#define STEPS2TIME(x)
Definition: SUMOTime.h:58
double getTravelTime(const ROEdge *const edge, const ROVehicle *const, double)
EdgeInfoByEffortComparator myComparator
const BASE::EdgeInfo & getEdgeInfo(int index) const
DijkstraRouter(const std::vector< E *> &edges, bool unbuildIsWarning, typename BASE::Operation effortOperation, typename BASE::Operation ttOperation=nullptr, bool silent=false, EffortCalculator *calc=nullptr)
Constructor.
virtual ~DijkstraRouter()
Destructor.
void inform(std::string msg, bool addType=true)
adds a new error to the list
Definition: MsgHandler.cpp:113
bool mySilent
whether to supress warning/error if no route was found
vehicles ignoring classes