Eclipse SUMO - Simulation of Urban MObility
CHBuilder.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-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 // Contraction Hierarchy Builder for the shortest path search
17 /****************************************************************************/
18 #ifndef CHBuilder_h
19 #define CHBuilder_h
20 
21 
22 // ===========================================================================
23 // included modules
24 // ===========================================================================
25 #include <config.h>
26 
27 #include <string>
28 #include <functional>
29 #include <vector>
30 #include <set>
31 #include <limits>
32 #include <algorithm>
33 #include <iterator>
34 #include <utils/common/SysUtils.h>
36 #include <utils/common/StdDefs.h>
38 #include "SPTree.h"
39 
40 //#define CHRouter_DEBUG_CONTRACTION
41 //#define CHRouter_DEBUG_CONTRACTION_WITNESSES
42 //#define CHRouter_DEBUG_CONTRACTION_QUEUE
43 //#define CHRouter_DEBUG_CONTRACTION_DEGREE
44 //#define CHRouter_DEBUG_WEIGHTS
45 
46 // ===========================================================================
47 // class definitions
48 // ===========================================================================
63 template<class E, class V>
64 class CHBuilder {
65 
66 public:
68  // forward connections are used only in forward search
69  // backward connections are used only in backwards search
70  class Connection {
71  public:
72  Connection(int t, double c, SVCPermissions p): target(t), cost(c), permissions(p) {}
73  int target;
74  double cost;
76  };
77 
78  typedef std::pair<const E*, const E*> ConstEdgePair;
79  typedef std::map<ConstEdgePair, const E*> ShortcutVia;
80  struct Hierarchy {
82  std::vector<std::vector<Connection> > forwardUplinks;
83  std::vector<std::vector<Connection> > backwardUplinks;
84  };
85 
91  CHBuilder(const std::vector<E*>& edges, bool unbuildIsWarning,
92  const SUMOVehicleClass svc,
93  bool validatePermissions):
94  myEdges(edges),
95  myErrorMsgHandler(unbuildIsWarning ? MsgHandler::getWarningInstance() : MsgHandler::getErrorInstance()),
96  mySPTree(new SPTree<CHInfo, CHConnection>(4, validatePermissions)),
97  mySVC(svc),
98  myUpdateCount(0) {
99  for (typename std::vector<E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
100  myCHInfos.push_back(CHInfo(*i));
101  }
102  }
103 
105  virtual ~CHBuilder() {
106  delete mySPTree;
107  }
108 
109 
110  const Hierarchy* buildContractionHierarchy(SUMOTime time, const V* const vehicle, const SUMOAbstractRouter<E, V>* effortProvider) {
111  Hierarchy* result = new Hierarchy();
112  const int numEdges = (int)myCHInfos.size();
113  const std::string vClass = (mySPTree->validatePermissions() ?
114  "all vehicle classes " : "vClass='" + SumoVehicleClassStrings.getString(mySVC) + "' ");
115  PROGRESS_BEGIN_MESSAGE("Building Contraction Hierarchy for " + vClass
116  + "and time=" + time2string(time) + " (" + toString(numEdges) + " edges)\n");
117  const long startMillis = SysUtils::getCurrentMillis();
118  // init queue
119  std::vector<CHInfo*> queue; // max heap: edge to be contracted is front
120  // reset previous connections etc
121  for (int i = 0; i < numEdges; i++) {
122  myCHInfos[i].resetContractionState();
123  result->forwardUplinks.push_back(std::vector<Connection>());
124  result->backwardUplinks.push_back(std::vector<Connection>());
125  }
126  // copy connections from the original net
127  const double time_seconds = STEPS2TIME(time); // timelines store seconds!
128  for (int i = 0; i < numEdges; i++) {
129  synchronize(myCHInfos[i], time_seconds, vehicle, effortProvider);
130  }
131  // synchronization is finished. now we can compute priorities for the first time
132  for (int i = 0; i < numEdges; i++) {
133  myCHInfos[i].updatePriority(mySPTree);
134  queue.push_back(&(myCHInfos[i]));
135  }
136  std::make_heap(queue.begin(), queue.end(), myCmp);
137  int contractionRank = 0;
138  // contraction loop
139  while (!queue.empty()) {
140  while (tryUpdateFront(queue)) {}
141  CHInfo* max = queue.front();
142  max->rank = contractionRank;
143 #ifdef CHRouter_DEBUG_CONTRACTION
144  std::cout << "contracting '" << max->edge->getID() << "' with prio: " << max->priority << " (rank " << contractionRank << ")\n";
145 #endif
146  const E* const edge = max->edge;
147  // add outgoing connections to the forward search
148  const int edgeID = edge->getNumericalID();
149  for (typename CHConnections::const_iterator it = max->followers.begin(); it != max->followers.end(); it++) {
150  const CHConnection& con = *it;
151  result->forwardUplinks[edgeID].push_back(Connection(con.target->edge->getNumericalID(), con.cost, con.permissions));
152  disconnect(con.target->approaching, max);
153  con.target->updatePriority(0);
154  }
155  // add incoming connections to the backward search
156  for (typename CHConnections::const_iterator it = max->approaching.begin(); it != max->approaching.end(); it++) {
157  const CHConnection& con = *it;
158  result->backwardUplinks[edgeID].push_back(Connection(con.target->edge->getNumericalID(), con.cost, con.permissions));
159  disconnect(con.target->followers, max);
160  con.target->updatePriority(0);
161  }
162  // add shortcuts to the net
163  for (typename std::vector<Shortcut>::const_iterator it = max->shortcuts.begin(); it != max->shortcuts.end(); it++) {
164  const ConstEdgePair& edgePair = it->edgePair;
165  result->shortcuts[edgePair] = edge;
166  CHInfo* from = getCHInfo(edgePair.first);
167  CHInfo* to = getCHInfo(edgePair.second);
168  from->followers.push_back(CHConnection(to, it->cost, it->permissions, it->underlying));
169  to->approaching.push_back(CHConnection(from, it->cost, it->permissions, it->underlying));
170  }
171  // if you need to debug the chrouter with MSVC uncomment the following line, hierarchy building will get slower and the hierarchy may change though
172  //std::make_heap(queue.begin(), queue.end(), myCmp);
173  // remove from queue
174  std::pop_heap(queue.begin(), queue.end(), myCmp);
175  queue.pop_back();
176  /*
177  if (contractionRank % 10000 == 0) {
178  // update all and rebuild queue
179  for (typename std::vector<CHInfo*>::iterator it = queue.begin(); it != queue.end(); ++it) {
180  (*it)->updatePriority(mySPTree);
181  }
182  std::make_heap(queue.begin(), queue.end(), myCmp);
183  }
184  */
185  contractionRank++;
186  }
187  // reporting
188  const long duration = SysUtils::getCurrentMillis() - startMillis;
189  WRITE_MESSAGE("Created " + toString(result->shortcuts.size()) + " shortcuts.");
190  WRITE_MESSAGE("Recomputed priority " + toString(myUpdateCount) + " times.");
191  MsgHandler::getMessageInstance()->endProcessMsg("done (" + toString(duration) + "ms).");
193  myUpdateCount = 0;
194  return result;
195  }
196 
197 private:
198  struct Shortcut {
199  Shortcut(ConstEdgePair e, double c, int u, SVCPermissions p):
200  edgePair(e), cost(c), underlying(u), permissions(p) {}
202  double cost;
205  };
206 
207 
208  class CHInfo;
209 
211  class CHConnection {
212  public:
213  CHConnection(CHInfo* t, double c, SVCPermissions p, int u):
214  target(t), cost(c), permissions(p), underlying(u) {}
216  double cost;
220  };
221 
222  typedef std::vector<CHConnection> CHConnections;
223  typedef std::pair<const CHConnection*, const CHConnection*> CHConnectionPair;
224  typedef std::vector<CHConnectionPair> CHConnectionPairs;
225 
226  /* @brief container class to use when building the contraction hierarchy.
227  * instances are reused every time the hierarchy is rebuilt (new time slice)
228  * but they must be synchronized first */
229  class CHInfo {
230  public:
232  CHInfo(const E* e) :
233  edge(e),
234  priority(0.),
236  rank(-1),
237  level(0),
238  underlyingTotal(0),
239  visited(false),
240  traveltime(std::numeric_limits<double>::max()),
241  depth(0),
243  }
244 
247  if (spTree != 0) {
248  updateShortcuts(spTree);
249  updateLevel();
250  } else {
251  contractedNeighbors += 1; // called when a connected edge was contracted
252  }
253  const double oldPriority = priority;
254  // priority term as used by abraham []
255  const int edge_difference = (int)followers.size() + (int)approaching.size() - 2 * (int)shortcuts.size();
256  priority = (double)(2 * edge_difference - contractedNeighbors - underlyingTotal - 5 * level);
257  return priority != oldPriority;
258  }
259 
262  const bool validatePermissions = spTree->validatePermissions();
263 #ifdef CHRouter_DEBUG_CONTRACTION_DEGREE
264  const int degree = (int)approaching.size() + (int)followers.size();
265  std::cout << "computing shortcuts for '" + edge->getID() + "' with degree " + toString(degree) + "\n";
266 #endif
267  shortcuts.clear();
268  underlyingTotal = 0;
269  for (typename CHConnections::iterator it_a = approaching.begin(); it_a != approaching.end(); it_a++) {
270  CHConnection& aInfo = *it_a;
271  // build shortest path tree in a fixed neighborhood
272  spTree->rebuildFrom(aInfo.target, this);
273  for (typename CHConnections::iterator it_f = followers.begin(); it_f != followers.end(); it_f++) {
274  CHConnection& fInfo = *it_f;
275  const double viaCost = aInfo.cost + fInfo.cost;
276  const SVCPermissions viaPermissions = (aInfo.permissions & fInfo.permissions);
277  if (fInfo.target->traveltime > viaCost) {
278  // found no faster path -> we need a shortcut via edge
279 #ifdef CHRouter_DEBUG_CONTRACTION_WITNESSES
280  debugNoWitness(aInfo, fInfo);
281 #endif
282  const int underlying = aInfo.underlying + fInfo.underlying;
283  underlyingTotal += underlying;
284  shortcuts.push_back(Shortcut(ConstEdgePair(aInfo.target->edge, fInfo.target->edge),
285  viaCost, underlying, viaPermissions));
286 
287  } else if (validatePermissions) {
288  if ((fInfo.target->permissions & viaPermissions) != viaPermissions) {
289  // witness has weaker restrictions. try to find another witness
290  spTree->registerForValidation(&aInfo, &fInfo);
291  } else {
292 #ifdef CHRouter_DEBUG_CONTRACTION_WITNESSES
293  debugNoWitness(aInfo, fInfo);
294 #endif
295  }
296  } else {
297 #ifdef CHRouter_DEBUG_CONTRACTION_WITNESSES
298  debugNoWitness(aInfo, fInfo);
299 #endif
300  }
301  }
302  }
303  // insert shortcuts needed due to unmet permissions
304  if (validatePermissions) {
305  const CHConnectionPairs& pairs = spTree->getNeededShortcuts(this);
306  for (typename CHConnectionPairs::const_iterator it = pairs.begin(); it != pairs.end(); ++it) {
307  const CHConnection* aInfo = it->first;
308  const CHConnection* fInfo = it->second;
309  const double viaCost = aInfo->cost + fInfo->cost;
310  const SVCPermissions viaPermissions = (aInfo->permissions & fInfo->permissions);
311  const int underlying = aInfo->underlying + fInfo->underlying;
312  underlyingTotal += underlying;
313  shortcuts.push_back(Shortcut(ConstEdgePair(aInfo->target->edge, fInfo->target->edge),
314  viaCost, underlying, viaPermissions));
315  }
316  }
317  }
318 
319 
320  // update level as defined by Abraham
321  void updateLevel() {
322  int maxLower = std::numeric_limits<int>::min();
323  int otherRank;
324  for (typename CHConnections::iterator it = approaching.begin(); it != approaching.end(); it++) {
325  otherRank = it->target->rank;
326  if (otherRank < rank) {
327  maxLower = MAX2(rank, maxLower);
328  }
329  }
330  for (typename CHConnections::iterator it = followers.begin(); it != followers.end(); it++) {
331  otherRank = it->target->rank;
332  if (otherRank < rank) {
333  maxLower = MAX2(rank, maxLower);
334  }
335  }
336  if (maxLower == std::numeric_limits<int>::min()) {
337  level = 0;
338  } else {
339  level = maxLower + 1;
340  }
341  }
342 
343  // resets state before rebuilding the hierarchy
346  rank = -1;
347  level = 0;
348  underlyingTotal = 0;
349  shortcuts.clear();
350  followers.clear();
351  approaching.clear();
352  }
353 
354 
356  const E* edge;
358  double priority;
360  std::vector<Shortcut> shortcuts;
363  int rank;
364  int level;
366 
370 
371 
373  bool visited;
375  double traveltime;
377  int depth;
379  // @note: we may miss some witness paths by making traveltime the only
380  // criteria durinng search
382 
383  inline void reset() {
384  traveltime = std::numeric_limits<double>::max();
385  visited = false;
386  }
387 
388 
390  inline void debugNoWitness(const CHConnection& aInfo, const CHConnection& fInfo) {
391  std::cout << "adding shortcut between " << aInfo.target->edge->getID() << ", " << fInfo.target->edge->getID() << " via " << edge->getID() << "\n";
392  }
393 
394  inline void debugWitness(const CHConnection& aInfo, const CHConnection& fInfo) {
395  const double viaCost = aInfo.cost + fInfo.cost;
396  std::cout << "found witness with length " << fInfo.target->traveltime << " against via " << edge->getID() << " (length " << viaCost << ") for " << aInfo.target->edge->getID() << ", " << fInfo.target->edge->getID() << "\n";
397  }
398 
399  };
400 
401 
407  public:
409  bool operator()(const CHInfo* a, const CHInfo* b) const {
410  if (a->priority == b->priority) {
411  return a->edge->getNumericalID() > b->edge->getNumericalID();
412  } else {
413  return a->priority < b->priority;
414  };
415  }
416  };
417 
418 
419  inline CHInfo* getCHInfo(const E* const edge) {
420  return &(myCHInfos[edge->getNumericalID()]);
421  }
422 
423 
425  void synchronize(CHInfo& info, double time, const V* const vehicle, const SUMOAbstractRouter<E, V>* effortProvider) {
426  // forward and backward connections are used only in forward search,
427  // thus approaching costs are those of the approaching edge and not of the edge itself
428  const bool prune = !mySPTree->validatePermissions();
429  const E* const edge = info.edge;
430  if (prune && ((edge->getPermissions() & mySVC) != mySVC)) {
431  return;
432  }
433  const double baseCost = effortProvider->getEffort(edge, vehicle, time);
434 
435  for (const std::pair<const E*, const E*>& successor : edge->getViaSuccessors(mySVC)) {
436  const E* fEdge = successor.first;
437  if (prune && ((fEdge->getPermissions() & mySVC) != mySVC)) {
438  continue;
439  }
440  CHInfo* const follower = getCHInfo(fEdge);
441  const SVCPermissions permissions = (edge->getPermissions() & fEdge->getPermissions());
442  double cost = baseCost;
443  const E* viaEdge = successor.second;
444  while (viaEdge != nullptr && viaEdge->isInternal()) {
445  cost += effortProvider->getEffort(viaEdge, vehicle, time);
446  viaEdge = viaEdge->getViaSuccessors().front().first;
447  }
448  info.followers.push_back(CHConnection(follower, cost, permissions, 1));
449  follower->approaching.push_back(CHConnection(&info, cost, permissions, 1));
450  }
451 #ifdef CHRouter_DEBUG_WEIGHTS
452  std::cout << time << ": " << edge->getID() << " cost: " << cost << "\n";
453 #endif
454  // @todo: check whether we even need to save approaching in ROEdge;
455  }
456 
457 
459  void disconnect(CHConnections& connections, CHInfo* other) {
460  for (typename CHConnections::iterator it = connections.begin(); it != connections.end(); it++) {
461  if (it->target == other) {
462  connections.erase(it);
463  return;
464  }
465  }
466  assert(false);
467  }
468 
472  bool tryUpdateFront(std::vector<CHInfo*>& queue) {
473  myUpdateCount++;
474  CHInfo* max = queue.front();
475 #ifdef CHRouter_DEBUG_CONTRACTION_QUEUE
476  std::cout << "updating '" << max->edge->getID() << "'\n";
477  debugPrintQueue(queue);
478 #endif
479  if (max->updatePriority(mySPTree)) {
480  std::pop_heap(queue.begin(), queue.end(), myCmp);
481  std::push_heap(queue.begin(), queue.end(), myCmp);
482  return true;
483  } else {
484  return false;
485  }
486  }
487 
488  // helper method for debugging
489  void debugPrintQueue(std::vector<CHInfo*>& queue) {
490  for (typename std::vector<CHInfo*>::iterator it = queue.begin(); it != queue.end(); it++) {
491  CHInfo* chInfo = *it;
492  std::cout << "(" << chInfo->edge->getID() << "," << chInfo->priority << ") ";
493  }
494  std::cout << "\n";
495  }
496 
497 private:
499  const std::vector<E*>& myEdges;
500 
503 
505  std::vector<CHInfo> myCHInfos;
506 
509 
512 
515 
518 
519 private:
521  CHBuilder& operator=(const CHBuilder& s);
522 };
523 
524 
525 #endif
526 
527 /****************************************************************************/
528 
CHBuilder::Shortcut
Definition: CHBuilder.h:198
CHBuilder::ConstEdgePair
std::pair< const E *, const E * > ConstEdgePair
Definition: CHBuilder.h:78
CHBuilder::Connection::permissions
SVCPermissions permissions
Definition: CHBuilder.h:75
CHBuilder::CHConnection::permissions
SVCPermissions permissions
Definition: CHBuilder.h:217
SUMOVehicleClass
SUMOVehicleClass
Definition of vehicle classes to differ between different lane usage and authority types.
Definition: SUMOVehicleClass.h:133
CHBuilder
Definition: CHBuilder.h:64
CHBuilder::CHInfo::shortcuts
std::vector< Shortcut > shortcuts
The needed shortcuts.
Definition: CHBuilder.h:360
CHBuilder::CHConnection::target
CHInfo * target
Definition: CHBuilder.h:215
CHBuilder::tryUpdateFront
bool tryUpdateFront(std::vector< CHInfo * > &queue)
tries to update the priority of the first edge
Definition: CHBuilder.h:472
CHBuilder::ShortcutVia
std::map< ConstEdgePair, const E * > ShortcutVia
Definition: CHBuilder.h:79
CHBuilder::debugPrintQueue
void debugPrintQueue(std::vector< CHInfo * > &queue)
Definition: CHBuilder.h:489
CHBuilder::CHConnectionPairs
std::vector< CHConnectionPair > CHConnectionPairs
Definition: CHBuilder.h:224
MsgHandler.h
CHBuilder::CHInfo::reset
void reset()
Definition: CHBuilder.h:383
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
CHBuilder::CHInfo::depth
int depth
number of edges from start
Definition: CHBuilder.h:377
CHBuilder::Connection
Forward/backward connection with associated forward/backward cost.
Definition: CHBuilder.h:70
CHBuilder::CHInfo::level
int level
Definition: CHBuilder.h:364
CHBuilder::CHBuilder
CHBuilder(const std::vector< E * > &edges, bool unbuildIsWarning, const SUMOVehicleClass svc, bool validatePermissions)
Constructor.
Definition: CHBuilder.h:91
CHBuilder::mySVC
const SUMOVehicleClass mySVC
the permissions for which the hierarchy was constructed
Definition: CHBuilder.h:514
CHBuilder::Connection::target
int target
Definition: CHBuilder.h:73
SPTree::rebuildFrom
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:87
CHBuilder::Shortcut::edgePair
ConstEdgePair edgePair
Definition: CHBuilder.h:201
CHBuilder::Hierarchy
Definition: CHBuilder.h:80
CHBuilder::myEdges
const std::vector< E * > & myEdges
all edges with numerical ids
Definition: CHBuilder.h:499
SumoVehicleClassStrings
StringBijection< SUMOVehicleClass > SumoVehicleClassStrings(sumoVehicleClassStringInitializer, SVC_CUSTOM2, false)
SysUtils::getCurrentMillis
static long getCurrentMillis()
Returns the current time in milliseconds.
Definition: SysUtils.cpp:38
CHBuilder::Hierarchy::shortcuts
ShortcutVia shortcuts
Definition: CHBuilder.h:81
CHBuilder::CHConnections
std::vector< CHConnection > CHConnections
Definition: CHBuilder.h:222
MAX2
T MAX2(T a, T b)
Definition: StdDefs.h:79
CHBuilder::Shortcut::cost
double cost
Definition: CHBuilder.h:202
MsgHandler
Definition: MsgHandler.h:38
CHBuilder::myCHInfos
std::vector< CHInfo > myCHInfos
static vector for lookup
Definition: CHBuilder.h:505
SVCPermissions
int SVCPermissions
bitset where each bit declares whether a certain SVC may use this edge/lane
Definition: SUMOVehicleClass.h:218
CHBuilder::Hierarchy::backwardUplinks
std::vector< std::vector< Connection > > backwardUplinks
Definition: CHBuilder.h:83
SysUtils.h
CHBuilder::CHInfo::debugWitness
void debugWitness(const CHConnection &aInfo, const CHConnection &fInfo)
Definition: CHBuilder.h:394
CHBuilder::CHInfo::rank
int rank
Definition: CHBuilder.h:363
MsgHandler::endProcessMsg
virtual void endProcessMsg(std::string msg)
Ends a process information.
Definition: MsgHandler.cpp:148
CHBuilder::CHInfo::resetContractionState
void resetContractionState()
Definition: CHBuilder.h:344
STEPS2TIME
#define STEPS2TIME(x)
Definition: SUMOTime.h:56
CHBuilder::CHInfo::permissions
SVCPermissions permissions
the permissions when reaching this edge on the fastest path
Definition: CHBuilder.h:381
CHBuilder::Hierarchy::forwardUplinks
std::vector< std::vector< Connection > > forwardUplinks
Definition: CHBuilder.h:82
time2string
std::string time2string(SUMOTime t)
Definition: SUMOTime.cpp:67
CHBuilder::CHInfo::traveltime
double traveltime
Effort to reach the edge.
Definition: CHBuilder.h:375
CHBuilder::CHInfoComparator
Definition: CHBuilder.h:406
CHBuilder::CHInfo::CHInfo
CHInfo(const E *e)
Constructor.
Definition: CHBuilder.h:232
CHBuilder::~CHBuilder
virtual ~CHBuilder()
Destructor.
Definition: CHBuilder.h:105
SPTree::getNeededShortcuts
const CHConnectionPairs & getNeededShortcuts(const E *excluded)
Definition: SPTree.h:142
CHBuilder::CHInfo
Definition: CHBuilder.h:229
CHBuilder::myCmp
CHInfoComparator myCmp
Comparator for contraction priority.
Definition: CHBuilder.h:508
CHBuilder::Shortcut::Shortcut
Shortcut(ConstEdgePair e, double c, int u, SVCPermissions p)
Definition: CHBuilder.h:199
CHBuilder::CHInfo::visited
bool visited
members used in SPTree
Definition: CHBuilder.h:373
CHBuilder::getCHInfo
CHInfo * getCHInfo(const E *const edge)
Definition: CHBuilder.h:419
SUMOAbstractRouter
Definition: SUMOAbstractRouter.h:46
CHBuilder::CHInfo::edge
const E * edge
The current edge - not const since it may receive shortcut edges.
Definition: CHBuilder.h:356
toString
std::string toString(const T &t, std::streamsize accuracy=gPrecision)
Definition: ToString.h:47
CHBuilder::Shortcut::permissions
SVCPermissions permissions
Definition: CHBuilder.h:204
SPTree::validatePermissions
bool validatePermissions()
whether permissions should be validated;
Definition: SPTree.h:129
CHBuilder::CHConnection::underlying
int underlying
the number of connections underlying this connection
Definition: CHBuilder.h:219
CHBuilder::CHInfoComparator::operator()
bool operator()(const CHInfo *a, const CHInfo *b) const
Comparing method.
Definition: CHBuilder.h:409
CHBuilder::CHInfo::underlyingTotal
int underlyingTotal
Definition: CHBuilder.h:365
PROGRESS_BEGIN_MESSAGE
#define PROGRESS_BEGIN_MESSAGE(msg)
Definition: MsgHandler.h:278
CHBuilder::CHInfo::priority
double priority
The contraction priority.
Definition: CHBuilder.h:358
CHBuilder::CHConnection
Forward/backward connection with associated FORWARD cost.
Definition: CHBuilder.h:211
CHBuilder::operator=
CHBuilder & operator=(const CHBuilder &s)
Invalidated assignment operator.
CHBuilder::myErrorMsgHandler
MsgHandler *const myErrorMsgHandler
the handler for routing errors
Definition: CHBuilder.h:502
CHBuilder::Connection::cost
double cost
Definition: CHBuilder.h:74
CHBuilder::CHInfo::debugNoWitness
void debugNoWitness(const CHConnection &aInfo, const CHConnection &fInfo)
debugging methods
Definition: CHBuilder.h:390
CHBuilder::buildContractionHierarchy
const Hierarchy * buildContractionHierarchy(SUMOTime time, const V *const vehicle, const SUMOAbstractRouter< E, V > *effortProvider)
Definition: CHBuilder.h:110
PROGRESS_DONE_MESSAGE
#define PROGRESS_DONE_MESSAGE()
Definition: MsgHandler.h:279
CHBuilder::Connection::Connection
Connection(int t, double c, SVCPermissions p)
Definition: CHBuilder.h:72
CHBuilder::disconnect
void disconnect(CHConnections &connections, CHInfo *other)
remove all connections to/from the given edge (assume it exists only once)
Definition: CHBuilder.h:459
CHBuilder::Shortcut::underlying
int underlying
Definition: CHBuilder.h:203
CHBuilder::CHInfo::contractedNeighbors
int contractedNeighbors
priority subterms
Definition: CHBuilder.h:362
SPTree
Definition: SPTree.h:38
SPTree.h
CHBuilder::synchronize
void synchronize(CHInfo &info, double time, const V *const vehicle, const SUMOAbstractRouter< E, V > *effortProvider)
copy connections from the original net (modified destructively during contraction)
Definition: CHBuilder.h:425
config.h
CHBuilder::CHInfo::updatePriority
bool updatePriority(SPTree< CHInfo, CHConnection > *spTree)
recompute the contraction priority and report whether it changed
Definition: CHBuilder.h:246
SPTree::registerForValidation
void registerForValidation(const C *aInfo, const C *fInfo)
save source/target pair for later validation
Definition: SPTree.h:134
StdDefs.h
CHBuilder::CHInfo::approaching
CHConnections approaching
Definition: CHBuilder.h:369
CHBuilder::CHInfo::updateLevel
void updateLevel()
Definition: CHBuilder.h:321
CHBuilder::CHConnectionPair
std::pair< const CHConnection *, const CHConnection * > CHConnectionPair
Definition: CHBuilder.h:223
SVC_IGNORING
@ SVC_IGNORING
vehicles ignoring classes
Definition: SUMOVehicleClass.h:135
SUMOAbstractRouter.h
CHBuilder::CHInfo::updateShortcuts
void updateShortcuts(SPTree< CHInfo, CHConnection > *spTree)
compute needed shortcuts when contracting this edge
Definition: CHBuilder.h:261
CHBuilder::CHConnection::CHConnection
CHConnection(CHInfo *t, double c, SVCPermissions p, int u)
Definition: CHBuilder.h:213
WRITE_MESSAGE
#define WRITE_MESSAGE(msg)
Definition: MsgHandler.h:277
CHBuilder::myUpdateCount
int myUpdateCount
counters for performance logging
Definition: CHBuilder.h:517
CHBuilder::CHConnection::cost
double cost
Definition: CHBuilder.h:216
CHBuilder::mySPTree
SPTree< CHInfo, CHConnection > * mySPTree
the shortest path tree to use when searching for shortcuts
Definition: CHBuilder.h:511
MsgHandler::getMessageInstance
static MsgHandler * getMessageInstance()
Returns the instance to add normal messages to.
Definition: MsgHandler.cpp:55
CHBuilder::CHInfo::followers
CHConnections followers
connections (only valid after synchronization)
Definition: CHBuilder.h:368