SUMO - Simulation of Urban MObility
CHRouter.h
Go to the documentation of this file.
1 /****************************************************************************/
9 // Shortest Path search using a Contraction Hierarchy
10 /****************************************************************************/
11 // SUMO, Simulation of Urban MObility; see http://sumo.dlr.de/
12 // Copyright (C) 2001-2016 DLR (http://www.dlr.de/) and contributors
13 /****************************************************************************/
14 //
15 // This file is part of SUMO.
16 // SUMO is free software: you can redistribute it and/or modify
17 // it under the terms of the GNU General Public License as published by
18 // the Free Software Foundation, either version 3 of the License, or
19 // (at your option) any later version.
20 //
21 /****************************************************************************/
22 #ifndef CHRouter_h
23 #define CHRouter_h
24 
25 
26 // ===========================================================================
27 // included modules
28 // ===========================================================================
29 #ifdef _MSC_VER
30 #include <windows_config.h>
31 #else
32 #include <config.h>
33 #endif
34 
35 #include <string>
36 #include <functional>
37 #include <vector>
38 #include <set>
39 #include <limits>
40 #include <algorithm>
41 #include <iterator>
42 #include <utils/common/SysUtils.h>
44 #include <utils/common/StdDefs.h>
46 #include "SPTree.h"
47 
48 //#define CHRouter_DEBUG_QUERY
49 //#define CHRouter_DEBUG_QUERY_PERF
50 //#define CHRouter_DEBUG_CONTRACTION
51 //#define CHRouter_DEBUG_CONTRACTION_WITNESSES
52 //#define CHRouter_DEBUG_CONTRACTION_QUEUE
53 //#define CHRouter_DEBUG_CONTRACTION_DEGREE
54 //#define CHRouter_DEBUG_WEIGHTS
55 
56 // ===========================================================================
57 // class definitions
58 // ===========================================================================
73 template<class E, class V, class PF>
74 class CHRouter: public SUMOAbstractRouter<E, V>, public PF {
75 
76 public:
77  class EdgeInfo;
78 
80  typedef SUMOReal(* Operation)(const E* const, const V* const, SUMOReal);
81 
83  typedef std::pair<const EdgeInfo*, const EdgeInfo*> Meeting;
84 
86  typedef std::set<const E*> EdgeSet;
87 
89  typedef std::vector<const E*> Result;
90 
92  // forward connections are used only in forward search
93  // backward connections are used only in backwards search
94  class Connection {
95  public:
100  };
101 
107  class EdgeInfo {
108  public:
110  EdgeInfo(const E* e) :
111  edge(e),
112  traveltime(std::numeric_limits<SUMOReal>::max()),
113  prev(0),
114  visited(false) {
115  }
116 
118  const E* edge;
119 
122 
125 
127  bool visited;
128 
130  std::vector<Connection> upward;
131 
133  int rank;
134 
135  inline void reset() {
136  traveltime = std::numeric_limits<SUMOReal>::max();
137  visited = false;
138  }
139  };
140 
141 
146  class Unidirectional: public PF {
147  public:
149  Unidirectional(const std::vector<E*>& edges, bool forward):
150  myAmForward(forward),
151  myVehicle(0) {
152  for (typename std::vector<E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
153  myEdgeInfos.push_back(EdgeInfo(*i));
154  }
155  }
156 
157  inline bool found(const E* edge) const {
158  return myFound.count(edge) > 0;
159  }
160 
161  inline EdgeInfo* getEdgeInfo(const E* const edge) {
162  return &(myEdgeInfos[edge->getNumericalID()]);
163  }
164 
165  inline const EdgeInfo* getEdgeInfo(const E* const edge) const {
166  return &(myEdgeInfos[edge->getNumericalID()]);
167  }
168 
174  public:
176  bool operator()(const EdgeInfo* nod1, const EdgeInfo* nod2) const {
177  if (nod1->traveltime == nod2->traveltime) {
178  return nod1->edge->getNumericalID() > nod2->edge->getNumericalID();
179  }
180  return nod1->traveltime > nod2->traveltime;
181  }
182  };
183 
184 
185  void init(const E* const start, const V* const vehicle) {
186  assert(vehicle != 0);
187  // all EdgeInfos touched in the previous query are either in myFrontier or myFound: clean those up
188  for (typename std::vector<EdgeInfo*>::iterator i = myFrontier.begin(); i != myFrontier.end(); i++) {
189  (*i)->reset();
190  }
191  myFrontier.clear();
192  for (typename EdgeSet::iterator i = myFound.begin(); i != myFound.end(); i++) {
193  getEdgeInfo(*i)->reset();
194  }
195  myFound.clear();
196  myVehicle = vehicle;
197  EdgeInfo* startInfo = getEdgeInfo(start);
198  startInfo->traveltime = 0;
199  startInfo->prev = 0;
200  myFrontier.push_back(startInfo);
201  }
202 
203 
208  bool step(const Unidirectional& otherSearch, SUMOReal& minTTSeen, Meeting& meeting) {
209  // pop the node with the minimal length
210  EdgeInfo* const minimumInfo = myFrontier.front();
211  pop_heap(myFrontier.begin(), myFrontier.end(), myComparator);
212  myFrontier.pop_back();
213  // check for a meeting with the other search
214  const E* const minEdge = minimumInfo->edge;
215 #ifdef CHRouter_DEBUG_QUERY
216  std::cout << "DEBUG: " << (myAmForward ? "Forward" : "Backward") << " hit '" << minEdge->getID() << "' Q: ";
217  for (typename std::vector<EdgeInfo*>::iterator it = myFrontier.begin(); it != myFrontier.end(); it++) {
218  std::cout << (*it)->traveltime << "," << (*it)->edge->getID() << " ";
219  }
220  std::cout << "\n";
221 #endif
222  if (otherSearch.found(minEdge)) {
223  const EdgeInfo* const otherInfo = otherSearch.getEdgeInfo(minEdge);
224  const SUMOReal ttSeen = minimumInfo->traveltime + otherInfo->traveltime;
225 #ifdef CHRouter_DEBUG_QUERY
226  std::cout << "DEBUG: " << (myAmForward ? "Forward" : "Backward") << "-Search hit other search at '" << minEdge->getID() << "', tt: " << ttSeen << " \n";
227 #endif
228  if (ttSeen < minTTSeen) {
229  minTTSeen = ttSeen;
230  if (myAmForward) {
231  meeting.first = minimumInfo;
232  meeting.second = otherInfo;
233  } else {
234  meeting.first = otherInfo;
235  meeting.second = minimumInfo;
236  }
237  }
238  }
239  // prepare next steps
240  minimumInfo->visited = true;
241  // XXX we only need to keep found elements if they have a higher rank than the lowest rank in the other search queue
242  myFound.insert(minimumInfo->edge);
243  for (typename std::vector<Connection>::iterator it = minimumInfo->upward.begin(); it != minimumInfo->upward.end(); it++) {
244  EdgeInfo* upwardInfo = it->target;
245  const SUMOReal traveltime = minimumInfo->traveltime + it->cost;
246  const SUMOVehicleClass svc = myVehicle->getVClass();
247  // check whether it can be used
248  if ((it->permissions & svc) != svc) {
249  continue;
250  }
251  const SUMOReal oldTraveltime = upwardInfo->traveltime;
252  if (!upwardInfo->visited && traveltime < oldTraveltime) {
253  upwardInfo->traveltime = traveltime;
254  upwardInfo->prev = minimumInfo;
255  if (oldTraveltime == std::numeric_limits<SUMOReal>::max()) {
256  myFrontier.push_back(upwardInfo);
257  push_heap(myFrontier.begin(), myFrontier.end(), myComparator);
258  } else {
259  push_heap(myFrontier.begin(),
260  find(myFrontier.begin(), myFrontier.end(), upwardInfo) + 1,
261  myComparator);
262  }
263  }
264  }
265  // @note: this effectively does a full dijkstra search.
266  // the effort compared to the naive stopping criterion is thus
267  // quadrupled. We could implement a better stopping criterion (Holte)
268  // However since the search shall take place in a contracted graph
269  // it probably does not matter
270  return !myFrontier.empty() && myFrontier.front()->traveltime < minTTSeen;
271  }
272 
273 
274  // reset state before rebuilding the contraction hierarchy
275  void reset() {
276  for (typename std::vector<EdgeInfo>::iterator it = myEdgeInfos.begin(); it != myEdgeInfos.end(); ++it) {
277  it->upward.clear();
278  }
279  }
280 
281  private:
285  std::vector<EdgeInfo*> myFrontier;
287  EdgeSet myFound;
289  std::vector<EdgeInfo> myEdgeInfos;
290 
292 
293  const V* myVehicle;
294 
295  };
296 
297  class CHInfo;
298 
300  class CHConnection {
301  public:
303  target(t), cost(c), permissions(p), underlying(u) {}
309  };
310 
311  typedef std::vector<CHConnection> CHConnections;
312  typedef std::pair<const CHConnection*, const CHConnection*> CHConnectionPair;
313  typedef std::vector<CHConnectionPair> CHConnectionPairs;
314 
321  CHRouter(const std::vector<E*>& edges, bool unbuildIsWarning, Operation operation,
322  const SUMOVehicleClass svc,
323  SUMOTime weightPeriod,
324  bool validatePermissions):
325  SUMOAbstractRouter<E, V>(operation, "CHRouter"),
326  myEdges(edges),
327  myErrorMsgHandler(unbuildIsWarning ? MsgHandler::getWarningInstance() : MsgHandler::getErrorInstance()),
328  myForwardSearch(edges, true),
329  myBackwardSearch(edges, false),
330  mySPTree(new SPTree<CHInfo, CHConnection>(4, validatePermissions)),
331  myWeightPeriod(weightPeriod),
332  myValidUntil(0),
333  mySVC(svc),
334  myUpdateCount(0) {
335  for (typename std::vector<E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
336  myCHInfos.push_back(CHInfo(*i));
337  }
338  }
339 
341  virtual ~CHRouter() {
342  delete mySPTree;
343  }
344 
345 
348  mySVC, myWeightPeriod, mySPTree->validatePermissions());
349  }
350 
355  virtual bool compute(const E* from, const E* to, const V* const vehicle,
356  SUMOTime msTime, Result& into) {
357  assert(from != 0 && to != 0);
358  assert(mySPTree->validatePermissions() || vehicle->getVClass() == mySVC || mySVC == SVC_IGNORING);
359  // do we need to rebuild the hierarchy?
360  if (msTime >= myValidUntil) {
361  while (msTime >= myValidUntil) {
363  }
365  }
366  // ready for routing
367  this->startQuery();
368  myForwardSearch.init(from, vehicle);
369  myBackwardSearch.init(to, vehicle);
371  Meeting meeting(static_cast<EdgeInfo*>(0), static_cast<EdgeInfo*>(0));
372  bool continueForward = true;
373  bool continueBackward = true;
374  int num_visited_fw = 0;
375  int num_visited_bw = 0;
376  bool result = true;
377  while (continueForward || continueBackward) {
378  if (continueForward) {
379  continueForward = myForwardSearch.step(myBackwardSearch, minTTSeen, meeting);
380  num_visited_fw += 1;
381  }
382  if (continueBackward) {
383  continueBackward = myBackwardSearch.step(myForwardSearch, minTTSeen, meeting);
384  num_visited_bw += 1;
385  }
386  }
387  if (minTTSeen < std::numeric_limits<SUMOReal>::max()) {
388  buildPathFromMeeting(meeting, into);
389  } else {
390  myErrorMsgHandler->inform("No connection between edge '" + from->getID() + "' and edge '" + to->getID() + "' found.");
391  result = false;
392  }
393 #ifdef CHRouter_DEBUG_QUERY_PERF
394  std::cout << "visited " << num_visited_fw + num_visited_bw << " edges (" << num_visited_fw << "," << num_visited_bw << ") ,final path length: " + toString(into.size()) + ")\n";
395 #endif
396  this->endQuery(num_visited_bw + num_visited_fw);
397  return result;
398  }
399 
400 
401  SUMOReal recomputeCosts(const std::vector<const E*>& edges, const V* const v, SUMOTime msTime) const {
402  const SUMOReal time = STEPS2TIME(msTime);
403  SUMOReal costs = 0;
404  for (typename std::vector<const E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
405  if (PF::operator()(*i, v)) {
406  return -1;
407  }
408  costs += this->getEffort(*i, v, time + costs);
409  }
410  return costs;
411  }
412 
414 
416  void buildPathFromMeeting(Meeting meeting, Result& into) {
417  std::deque<const E*> tmp;
418  const EdgeInfo* backtrack = meeting.first;
419  while (backtrack != 0) {
420  tmp.push_front((E*) backtrack->edge); // !!!
421  backtrack = backtrack->prev;
422  }
423  backtrack = meeting.second->prev; // don't use central edge twice
424  while (backtrack != 0) {
425  tmp.push_back((E*) backtrack->edge); // !!!
426  backtrack = backtrack->prev;
427  }
428  // expand shortcuts
429  const E* prev = 0;
430  while (!tmp.empty()) {
431  const E* cur = tmp.front();
432  tmp.pop_front();
433  if (prev == 0) {
434  into.push_back(cur);
435  prev = cur;
436  } else {
437  const E* via = getVia(prev, cur);
438  if (via == 0) {
439  into.push_back(cur);
440  prev = cur;
441  } else {
442  tmp.push_front(cur);
443  tmp.push_front(via);
444  }
445  }
446  }
447  }
448 
450  typedef std::pair<const E*, const E*> ConstEdgePair;
451  typedef std::pair<E*, E*> EdgePair;
452 
453  struct Shortcut {
454  Shortcut(EdgePair e, SUMOReal c, int u, SVCPermissions p):
455  edgePair(e), cost(c), underlying(u), permissions(p) {}
456  EdgePair edgePair;
460  };
461 
462  typedef std::vector<Shortcut> Shortcuts;
463  typedef std::map<ConstEdgePair, const E*> ShortcutVia;
464 
465  /* @brief container class to use when building the contraction hierarchy.
466  * instances are reused every time the hierarchy is rebuilt (new time slice)
467  * but they must be synchronized first */
468  class CHInfo {
469  public:
471  CHInfo(E* e) :
472  edge(e),
473  contractedNeighbors(0),
474  rank(-1),
475  level(0),
476  underlyingTotal(0),
477  visited(false),
478  traveltime(std::numeric_limits<SUMOReal>::max()) {
479  }
480 
483  if (spTree != 0) {
484  updateShortcuts(spTree);
485  updateLevel();
486  } else {
487  contractedNeighbors += 1; // called when a connected edge was contracted
488  }
489  const SUMOReal oldPriority = priority;
490  // priority term as used by abraham []
491  const int edge_difference = (int)followers.size() + (int)approaching.size() - 2 * (int)shortcuts.size();
492  priority = (SUMOReal)(2 * edge_difference - contractedNeighbors - underlyingTotal - 5 * level);
493  return priority != oldPriority;
494  }
495 
498  const bool validatePermissions = spTree->validatePermissions();
499 #ifdef CHRouter_DEBUG_CONTRACTION_DEGREE
500  const int degree = approaching.size() + followers.size();
501  std::cout << "computing shortcuts for '" + edge->getID() + "' with degree " + toString(degree) + "\n";
502 #endif
503  shortcuts.clear();
504  underlyingTotal = 0;
505  for (typename CHConnections::iterator it_a = approaching.begin(); it_a != approaching.end(); it_a++) {
506  CHConnection& aInfo = *it_a;
507  // build shortest path tree in a fixed neighborhood
508  spTree->rebuildFrom(aInfo.target, this);
509  for (typename CHConnections::iterator it_f = followers.begin(); it_f != followers.end(); it_f++) {
510  CHConnection& fInfo = *it_f;
511  const SUMOReal viaCost = aInfo.cost + fInfo.cost;
512  const SVCPermissions viaPermissions = (aInfo.permissions & fInfo.permissions);
513  if (fInfo.target->traveltime > viaCost) {
514  // found no faster path -> we need a shortcut via edge
515 #ifdef CHRouter_DEBUG_CONTRACTION_WITNESSES
516  debugNoWitness(aInfo, fInfo);
517 #endif
518  const int underlying = aInfo.underlying + fInfo.underlying;
519  underlyingTotal += underlying;
520  shortcuts.push_back(Shortcut(EdgePair(aInfo.target->edge, fInfo.target->edge),
521  viaCost, underlying, viaPermissions));
522 
523  } else if (validatePermissions) {
524  if ((fInfo.target->permissions & viaPermissions) != viaPermissions) {
525  // witness has weaker restrictions. try to find another witness
526  spTree->registerForValidation(&aInfo, &fInfo);
527  } else {
528 #ifdef CHRouter_DEBUG_CONTRACTION_WITNESSES
529  debugNoWitness(aInfo, fInfo);
530 #endif
531  }
532  } else {
533 #ifdef CHRouter_DEBUG_CONTRACTION_WITNESSES
534  debugNoWitness(aInfo, fInfo);
535 #endif
536  }
537  }
538  }
539  // insert shortcuts needed due to unmet permissions
540  if (validatePermissions) {
541  const CHConnectionPairs& pairs = spTree->getNeededShortcuts(this);
542  for (typename CHConnectionPairs::const_iterator it = pairs.begin(); it != pairs.end(); ++it) {
543  const CHConnection* aInfo = it->first;
544  const CHConnection* fInfo = it->second;
545  const SUMOReal viaCost = aInfo->cost + fInfo->cost;
546  const SVCPermissions viaPermissions = (aInfo->permissions & fInfo->permissions);
547  const int underlying = aInfo->underlying + fInfo->underlying;
548  underlyingTotal += underlying;
549  shortcuts.push_back(Shortcut(EdgePair(aInfo->target->edge, fInfo->target->edge),
550  viaCost, underlying, viaPermissions));
551  }
552  }
553  }
554 
555 
556  // update level as defined by Abraham
557  void updateLevel() {
558  int maxLower = std::numeric_limits<int>::min();
559  int otherRank;
560  for (typename CHConnections::iterator it = approaching.begin(); it != approaching.end(); it++) {
561  otherRank = it->target->rank;
562  if (otherRank < rank) {
563  maxLower = MAX2(rank, maxLower);
564  }
565  }
566  for (typename CHConnections::iterator it = followers.begin(); it != followers.end(); it++) {
567  otherRank = it->target->rank;
568  if (otherRank < rank) {
569  maxLower = MAX2(rank, maxLower);
570  }
571  }
572  if (maxLower == std::numeric_limits<int>::min()) {
573  level = 0;
574  } else {
575  level = maxLower + 1;
576  }
577  }
578 
579  // resets state before rebuilding the hierarchy
581  contractedNeighbors = 0;
582  rank = -1;
583  level = 0;
584  underlyingTotal = 0;
585  shortcuts.clear();
586  followers.clear();
587  approaching.clear();
588  }
589 
590 
592  E* edge;
596  Shortcuts shortcuts;
599  int rank;
600  int level;
602 
604  CHConnections followers;
605  CHConnections approaching;
606 
607 
609  bool visited;
613  int depth;
615  // @note: we may miss some witness paths by making traveltime the only
616  // criteria durinng search
618 
619  inline void reset() {
620  traveltime = std::numeric_limits<SUMOReal>::max();
621  visited = false;
622  }
623 
624 
626  inline void debugNoWitness(const CHConnection& aInfo, const CHConnection& fInfo) {
627  std::cout << "adding shortcut between " << aInfo.target->edge->getID() << ", " << fInfo.target->edge->getID() << " via " << edge->getID() << "\n";
628  }
629 
630  inline void debugWitness(const CHConnection& aInfo, const CHConnection& fInfo) {
631  const SUMOReal viaCost = aInfo.cost + fInfo.cost;
632  std::cout << "found witness with lenght " << fInfo.target->traveltime << " against via " << edge->getID() << " (length " << viaCost << ") for " << aInfo.target->edge->getID() << ", " << fInfo.target->edge->getID() << "\n";
633  }
634 
635  };
636 
637 private:
638 
644  public:
646  bool operator()(const CHInfo* a, const CHInfo* b) const {
647  if (a->priority == b->priority) {
648  return a->edge->getNumericalID() > b->edge->getNumericalID();
649  } else {
650  return a->priority < b->priority;
651  };
652  }
653  };
654 
655 
656  inline CHInfo* getCHInfo(const E* const edge) {
657  return &(myCHInfos[edge->getNumericalID()]);
658  }
659 
660 
662  void synchronize(CHInfo& info, SUMOReal time, const V* const vehicle) {
663  // forward and backward connections are used only in forward search,
664  // thus approaching costs are those of the approaching edge and not of the edge itself
665  const bool prune = !mySPTree->validatePermissions();
666  const E* const edge = info.edge;
667  if (prune && ((edge->getPermissions() & mySVC) != mySVC)) {
668  return;
669  }
670  const SUMOReal cost = this->getEffort(edge, vehicle, time);
671 
672  const std::vector<E*>& successors = edge->getSuccessors(mySVC);
673  for (typename std::vector<E*>::const_iterator it = successors.begin(); it != successors.end(); ++it) {
674  const E* fEdge = *it;
675  if (prune && ((fEdge->getPermissions() & mySVC) != mySVC)) {
676  continue;
677  }
678  CHInfo* follower = getCHInfo(fEdge);
679  SVCPermissions permissions = (edge->getPermissions() & follower->edge->getPermissions());
680  info.followers.push_back(CHConnection(follower, cost, permissions, 1));
681  follower->approaching.push_back(CHConnection(&info, cost, permissions, 1));
682  }
683 #ifdef CHRouter_DEBUG_WEIGHTS
684  std::cout << time << ": " << edge->getID() << " cost: " << cost << "\n";
685 #endif
686  // @todo: check whether we even need to save approaching in ROEdge;
687  }
688 
689 
691  void disconnect(CHConnections& connections, CHInfo* other) {
692  for (typename CHConnections::iterator it = connections.begin(); it != connections.end(); it++) {
693  if (it->target == other) {
694  connections.erase(it);
695  return;
696  }
697  }
698  assert(false);
699  }
700 
701 
702  void buildContractionHierarchy(SUMOTime time, const V* const vehicle) {
703  const int numEdges = (int)myCHInfos.size();
704  const std::string vClass = (mySPTree->validatePermissions() ?
705  "all vehicle classes " : "vClass='" + SumoVehicleClassStrings.getString(mySVC) + "' ");
706  PROGRESS_BEGIN_MESSAGE("Building Contraction Hierarchy for " + vClass
707  + "and time=" + time2string(time) + " (" + toString(numEdges) + " edges)\n");
708  const long startMillis = SysUtils::getCurrentMillis();
709  // init queue
710  std::vector<CHInfo*> queue; // max heap: edge to be contracted is front
711  myShortcuts.clear();
712  // reset previous connections etc
715  for (int i = 0; i < numEdges; i++) {
716  myCHInfos[i].resetContractionState();
717  }
718  // copy connections from the original net
719  const SUMOReal time_seconds = STEPS2TIME(time); // timelines store seconds!
720  for (int i = 0; i < numEdges; i++) {
721  synchronize(myCHInfos[i], time_seconds, vehicle);
722  }
723  // synchronization is finished. now we can compute priorities for the first time
724  for (int i = 0; i < numEdges; i++) {
725  myCHInfos[i].updatePriority(mySPTree);
726  queue.push_back(&(myCHInfos[i]));
727  }
728  make_heap(queue.begin(), queue.end(), myCmp);
729  int contractionRank = 0;
730  // contraction loop
731  while (!queue.empty()) {
732  while (tryUpdateFront(queue)) {}
733  CHInfo* max = queue.front();
734  max->rank = contractionRank;
735 #ifdef CHRouter_DEBUG_CONTRACTION
736  std::cout << "contracting '" << max->edge->getID() << "' with prio: " << max->priority << " (rank " << contractionRank << ")\n";
737 #endif
738  E* edge = max->edge;
739  // add outgoing connections to the forward search
740  EdgeInfo* edgeInfoFW = myForwardSearch.getEdgeInfo(edge);
741  edgeInfoFW->rank = contractionRank;
742  for (typename CHConnections::iterator it = max->followers.begin(); it != max->followers.end(); it++) {
743  CHConnection& con = *it;
744  EdgeInfo* followerInfoFW = myForwardSearch.getEdgeInfo(con.target->edge);
745  edgeInfoFW->upward.push_back(Connection(followerInfoFW, con.cost, con.permissions));
746  disconnect(con.target->approaching, max);
747  con.target->updatePriority(0);
748  }
749  // add incoming connections to the backward search
750  EdgeInfo* edgeInfoBW = myBackwardSearch.getEdgeInfo(edge);
751  edgeInfoBW->rank = contractionRank;
752  for (typename CHConnections::iterator it = max->approaching.begin(); it != max->approaching.end(); it++) {
753  CHConnection& con = *it;
754  EdgeInfo* approachingInfoBW = myBackwardSearch.getEdgeInfo(con.target->edge);
755  edgeInfoBW->upward.push_back(Connection(approachingInfoBW, con.cost, con.permissions));
756  disconnect(con.target->followers, max);
757  con.target->updatePriority(0);
758  }
759  // add shortcuts to the net
760  for (typename Shortcuts::iterator it = max->shortcuts.begin(); it != max->shortcuts.end(); it++) {
761  EdgePair& edgePair = it->edgePair;
762  myShortcuts[edgePair] = edge;
763  CHInfo* from = getCHInfo(edgePair.first);
764  CHInfo* to = getCHInfo(edgePair.second);
765  from->followers.push_back(CHConnection(to, it->cost, it->permissions, it->underlying));
766  to->approaching.push_back(CHConnection(from, it->cost, it->permissions, it->underlying));
767  }
768  // remove from queue
769  pop_heap(queue.begin(), queue.end(), myCmp);
770  queue.pop_back();
771  /*
772  if (contractionRank % 10000 == 0) {
773  // update all and rebuild queue
774  for (typename std::vector<CHInfo*>::iterator it = queue.begin(); it != queue.end(); ++it) {
775  (*it)->updatePriority(mySPTree);
776  }
777  make_heap(queue.begin(), queue.end(), myCmp);
778  }
779  */
780  contractionRank++;
781  }
782  // reporting
783  const long duration = SysUtils::getCurrentMillis() - startMillis;
784  WRITE_MESSAGE("Created " + toString(myShortcuts.size()) + " shortcuts.");
785  WRITE_MESSAGE("Recomputed priority " + toString(myUpdateCount) + " times.");
786  MsgHandler::getMessageInstance()->endProcessMsg("done (" + toString(duration) + "ms).");
788  // declare new validUntil (prevent overflow)
790  myValidUntil = time + myWeightPeriod;
791  } else {
793  }
794  myUpdateCount = 0;
795  }
796 
797  // retrieve the via edge for a shortcut
798  const E* getVia(const E* forwardFrom, const E* forwardTo) {
799  ConstEdgePair forward(forwardFrom, forwardTo);
800  typename ShortcutVia::iterator it = myShortcuts.find(forward);
801  if (it != myShortcuts.end()) {
802  return it->second;
803  } else {
804  return 0;
805  }
806  }
807 
808 
812  bool tryUpdateFront(std::vector<CHInfo*>& queue) {
813  myUpdateCount++;
814  CHInfo* max = queue.front();
815 #ifdef CHRouter_DEBUG_CONTRACTION_QUEUE
816  std::cout << "updating '" << max->edge->getID() << "'\n";
817  debugPrintQueue(queue);
818 #endif
819  if (max->updatePriority(mySPTree)) {
820  pop_heap(queue.begin(), queue.end(), myCmp);
821  push_heap(queue.begin(), queue.end(), myCmp);
822  return true;
823  } else {
824  return false;
825  }
826  }
827 
828  // helper method for debugging
829  void debugPrintQueue(std::vector<CHInfo*>& queue) {
830  for (typename std::vector<CHInfo*>::iterator it = queue.begin(); it != queue.end(); it++) {
831  CHInfo* chInfo = *it;
832  std::cout << "(" << chInfo->edge->getID() << "," << chInfo->priority << ") ";
833  }
834  std::cout << "\n";
835  }
836 
837 private:
839  const std::vector<E*>& myEdges;
840 
843 
847 
849  ShortcutVia myShortcuts;
850 
852  std::vector<CHInfo> myCHInfos;
853 
856 
859 
862 
865 
868 
871 };
872 
873 
874 #endif
875 
876 /****************************************************************************/
877 
Computes the shortest path through a contracted network.
Definition: CHRouter.h:74
void debugWitness(const CHConnection &aInfo, const CHConnection &fInfo)
Definition: CHRouter.h:630
EdgeSet myFound
the set of visited (settled) Edges
Definition: CHRouter.h:287
static MsgHandler * getWarningInstance()
Returns the instance to add warnings to.
Definition: MsgHandler.cpp:71
CHInfoComparator myCmp
Comparator for contraction priority.
Definition: CHRouter.h:855
std::pair< E *, E * > EdgePair
Definition: CHRouter.h:451
std::pair< const E *, const E * > ConstEdgePair
contraction related members
Definition: CHRouter.h:450
int myUpdateCount
counters for performance logging
Definition: CHRouter.h:870
SPTree< CHInfo, CHConnection > * mySPTree
the shortest path tree to use when searching for shortcuts
Definition: CHRouter.h:858
long long int SUMOTime
Definition: SUMOTime.h:43
int depth
number of edges from start
Definition: CHRouter.h:613
const SUMOTime myWeightPeriod
the validity duration of one weight interval
Definition: CHRouter.h:861
EdgeInfo * getEdgeInfo(const E *const edge)
Definition: CHRouter.h:161
CHConnections followers
connections (only valid after synchronization)
Definition: CHRouter.h:604
bool step(const Unidirectional &otherSearch, SUMOReal &minTTSeen, Meeting &meeting)
explore on element from the frontier,update minTTSeen and meeting if an EdgeInfo found by the otherSe...
Definition: CHRouter.h:208
const E * getVia(const E *forwardFrom, const E *forwardTo)
Definition: CHRouter.h:798
#define min(a, b)
Definition: polyfonts.c:66
SUMOVehicleClass
Definition of vehicle classes to differ between different lane usage and authority types...
virtual ~CHRouter()
Destructor.
Definition: CHRouter.h:341
std::set< const E * > EdgeSet
A set of (found) Edges.
Definition: CHRouter.h:86
Unidirectional myForwardSearch
the unidirectional search queues
Definition: CHRouter.h:845
void buildPathFromMeeting(Meeting meeting, Result &into)
normal routing methods
Definition: CHRouter.h:416
SUMOReal traveltime
Effort to reach the edge.
Definition: CHRouter.h:611
int SVCPermissions
void resetContractionState()
Definition: CHRouter.h:580
std::string time2string(SUMOTime t)
Definition: SUMOTime.cpp:59
void synchronize(CHInfo &info, SUMOReal time, const V *const vehicle)
copy connections from the original net (modified destructively during contraction) ...
Definition: CHRouter.h:662
std::vector< EdgeInfo * > myFrontier
the min edge heap
Definition: CHRouter.h:285
SVCPermissions permissions
Definition: CHRouter.h:99
bool visited
Whether the shortest path to this edge is already found.
Definition: CHRouter.h:127
T MAX2(T a, T b)
Definition: StdDefs.h:75
CHInfo * getCHInfo(const E *const edge)
Definition: CHRouter.h:656
bool operator()(const EdgeInfo *nod1, const EdgeInfo *nod2) const
Comparing method.
Definition: CHRouter.h:176
ShortcutVia myShortcuts
map from (forward) shortcut to via-Edge
Definition: CHRouter.h:849
void updateShortcuts(SPTree< CHInfo, CHConnection > *spTree)
compute needed shortcuts when contracting this edge
Definition: CHRouter.h:497
std::vector< const E * > Result
The found route (used as output parameter)
Definition: CHRouter.h:89
int contractedNeighbors
priority subterms
Definition: CHRouter.h:598
EdgeInfoByTTComparator myComparator
Definition: CHRouter.h:291
SUMOReal priority
The contraction priority.
Definition: CHRouter.h:594
int rank
the contraction rank (higher means more important)
Definition: CHRouter.h:133
Shortcut(EdgePair e, SUMOReal c, int u, SVCPermissions p)
Definition: CHRouter.h:454
E * edge
The current edge - not const since it may receive shortcut edges.
Definition: CHRouter.h:592
CHRouter(const std::vector< E *> &edges, bool unbuildIsWarning, Operation operation, const SUMOVehicleClass svc, SUMOTime weightPeriod, bool validatePermissions)
Constructor.
Definition: CHRouter.h:321
Unidirectional myBackwardSearch
Definition: CHRouter.h:846
SVCPermissions permissions
Definition: CHRouter.h:306
std::map< ConstEdgePair, const E * > ShortcutVia
Definition: CHRouter.h:463
#define new
Definition: debug_new.h:121
virtual SUMOAbstractRouter< E, V > * clone()
Definition: CHRouter.h:346
void registerForValidation(const C *aInfo, const C *fInfo)
save source/target pair for later validation
Definition: SPTree.h:142
std::vector< Shortcut > Shortcuts
Definition: CHRouter.h:462
std::vector< CHConnectionPair > CHConnectionPairs
Definition: CHRouter.h:313
std::vector< CHInfo > myCHInfos
static vector for lookup
Definition: CHRouter.h:852
bool operator()(const CHInfo *a, const CHInfo *b) const
Comparing method.
Definition: CHRouter.h:646
#define max(a, b)
Definition: polyfonts.c:65
SUMOTime myValidUntil
the validity duration of the current hierarchy (exclusive)
Definition: CHRouter.h:864
Forward/backward connection with associated FORWARD cost.
Definition: CHRouter.h:300
std::vector< EdgeInfo > myEdgeInfos
The container of edge information.
Definition: CHRouter.h:289
Unidirectional(const std::vector< E *> &edges, bool forward)
Constructor.
Definition: CHRouter.h:149
virtual bool compute(const E *from, const E *to, const V *const vehicle, SUMOTime msTime, Result &into)
Builds the route between the given edges using the minimum traveltime in the contracted graph...
Definition: CHRouter.h:355
const CHConnectionPairs & getNeededShortcuts(const E *excluded)
Definition: SPTree.h:150
EdgeInfo * target
Definition: CHRouter.h:97
void init(const E *const start, const V *const vehicle)
Definition: CHRouter.h:185
#define STEPS2TIME(x)
Definition: SUMOTime.h:65
bool tryUpdateFront(std::vector< CHInfo *> &queue)
tries to update the priority of the first edge
Definition: CHRouter.h:812
SUMOReal traveltime
Effort to reach the edge.
Definition: CHRouter.h:121
std::vector< CHConnection > CHConnections
Definition: CHRouter.h:311
#define PROGRESS_BEGIN_MESSAGE(msg)
Definition: MsgHandler.h:202
static MsgHandler * getMessageInstance()
Returns the instance to add normal messages to.
Definition: MsgHandler.cpp:62
bool updatePriority(SPTree< CHInfo, CHConnection > *spTree)
recompute the contraction priority and report whether it changed
Definition: CHRouter.h:482
bool found(const E *edge) const
Definition: CHRouter.h:157
SUMOReal(* Operation)(const E *const, const V *const, SUMOReal)
Type of the function that is used to retrieve the edge effort.
Definition: CHRouter.h:80
void debugNoWitness(const CHConnection &aInfo, const CHConnection &fInfo)
debugging methods
Definition: CHRouter.h:626
std::pair< const EdgeInfo *, const EdgeInfo * > Meeting
A meeting point of the two search scopes.
Definition: CHRouter.h:83
StringBijection< SUMOVehicleClass > SumoVehicleClassStrings(sumoVehicleClassStringInitializer, SVC_CUSTOM2, false)
Operation myOperation
The object&#39;s operation to perform.
CHConnection(CHInfo *t, SUMOReal c, SVCPermissions p, int u)
Definition: CHRouter.h:302
SUMOReal getEffort(const E *const e, const V *const v, SUMOReal t) const
std::string toString(const T &t, std::streamsize accuracy=OUTPUT_ACCURACY)
Definition: ToString.h:55
SVCPermissions permissions
Definition: CHRouter.h:459
SUMOVehicleClass mySVC
the permissions for which the hierarchy was constructed
Definition: CHRouter.h:867
SUMOReal recomputeCosts(const std::vector< const E *> &edges, const V *const v, SUMOTime msTime) const
Definition: CHRouter.h:401
bool visited
members used in SPTree
Definition: CHRouter.h:609
Definition: SPTree.h:46
Shortcuts shortcuts
The needed shortcuts.
Definition: CHRouter.h:596
const std::vector< E * > & myEdges
all edges with numerical ids
Definition: CHRouter.h:839
MsgHandler *const myErrorMsgHandler
the handler for routing errors
Definition: CHRouter.h:842
Forward/backward connection with associated forward/backward cost.
Definition: CHRouter.h:94
void rebuildFrom(E *start, const E *excluded)
build a shortest path tree from start to a depth of myMaxdepth. The given edge is excluded from this ...
Definition: SPTree.h:95
CHConnections approaching
Definition: CHRouter.h:605
void inform(std::string msg, bool addType=true)
adds a new error to the list
Definition: MsgHandler.cpp:89
const EdgeInfo * getEdgeInfo(const E *const edge) const
Definition: CHRouter.h:165
int underlying
the number of connections underlying this connection
Definition: CHRouter.h:308
void disconnect(CHConnections &connections, CHInfo *other)
remove all connections to/from the given edge (assume it exists only once)
Definition: CHRouter.h:691
EdgePair edgePair
Definition: CHRouter.h:456
SVCPermissions permissions
the permissions when reaching this edge on the fastest path
Definition: CHRouter.h:617
bool myAmForward
the role of this search
Definition: CHRouter.h:283
#define SUMOReal
Definition: config.h:213
void endQuery(int visits)
void debugPrintQueue(std::vector< CHInfo *> &queue)
Definition: CHRouter.h:829
bool validatePermissions()
whether permissions should be validated;
Definition: SPTree.h:137
static long getCurrentMillis()
Returns the current time in milliseconds.
Definition: SysUtils.cpp:50
#define PROGRESS_DONE_MESSAGE()
Definition: MsgHandler.h:203
void updateLevel()
Definition: CHRouter.h:557
std::pair< const CHConnection *, const CHConnection * > CHConnectionPair
Definition: CHRouter.h:312
CHInfo(E *e)
Constructor.
Definition: CHRouter.h:471
#define WRITE_MESSAGE(msg)
Definition: MsgHandler.h:201
Connection(EdgeInfo *t, SUMOReal c, SVCPermissions p)
Definition: CHRouter.h:96
EdgeInfo(const E *e)
Constructor.
Definition: CHRouter.h:110
const E * edge
The current edge.
Definition: CHRouter.h:118
vehicles ignoring classes
void buildContractionHierarchy(SUMOTime time, const V *const vehicle)
Definition: CHRouter.h:702
std::vector< Connection > upward
Connections to higher ranked nodes.
Definition: CHRouter.h:130
EdgeInfo * prev
The previous edge.
Definition: CHRouter.h:124
void endProcessMsg(std::string msg)
Ends a process information.
Definition: MsgHandler.cpp:131