SUMO - Simulation of Urban MObility
CHBuilder.h
Go to the documentation of this file.
1 /****************************************************************************/
9 // Contraction Hierarchy Builder for the shortest path search
10 /****************************************************************************/
11 // SUMO, Simulation of Urban MObility; see http://sumo.dlr.de/
12 // Copyright (C) 2001-2017 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 CHBuilder_h
23 #define CHBuilder_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_CONTRACTION
49 //#define CHRouter_DEBUG_CONTRACTION_WITNESSES
50 //#define CHRouter_DEBUG_CONTRACTION_QUEUE
51 //#define CHRouter_DEBUG_CONTRACTION_DEGREE
52 //#define CHRouter_DEBUG_WEIGHTS
53 
54 // ===========================================================================
55 // class definitions
56 // ===========================================================================
71 template<class E, class V>
72 class CHBuilder {
73 
74 public:
76  // forward connections are used only in forward search
77  // backward connections are used only in backwards search
78  class Connection {
79  public:
80  Connection(int t, double c, SVCPermissions p): target(t), cost(c), permissions(p) {}
81  int target;
82  double cost;
84  };
85 
86  typedef std::pair<const E*, const E*> ConstEdgePair;
87  typedef std::map<ConstEdgePair, const E*> ShortcutVia;
88  struct Hierarchy {
89  ShortcutVia shortcuts;
90  std::vector<std::vector<Connection> > forwardUplinks;
91  std::vector<std::vector<Connection> > backwardUplinks;
92  };
93 
99  CHBuilder(const std::vector<E*>& edges, bool unbuildIsWarning,
100  const SUMOVehicleClass svc,
101  bool validatePermissions):
102  myEdges(edges),
103  myErrorMsgHandler(unbuildIsWarning ? MsgHandler::getWarningInstance() : MsgHandler::getErrorInstance()),
104  mySPTree(new SPTree<CHInfo, CHConnection>(4, validatePermissions)),
105  mySVC(svc),
106  myUpdateCount(0) {
107  for (typename std::vector<E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
108  myCHInfos.push_back(CHInfo(*i));
109  }
110  }
111 
113  virtual ~CHBuilder() {
114  delete mySPTree;
115  }
116 
117 
118  const Hierarchy* buildContractionHierarchy(SUMOTime time, const V* const vehicle, const SUMOAbstractRouter<E, V>* effortProvider) {
119  Hierarchy* result = new Hierarchy();
120  const int numEdges = (int)myCHInfos.size();
121  const std::string vClass = (mySPTree->validatePermissions() ?
122  "all vehicle classes " : "vClass='" + SumoVehicleClassStrings.getString(mySVC) + "' ");
123  PROGRESS_BEGIN_MESSAGE("Building Contraction Hierarchy for " + vClass
124  + "and time=" + time2string(time) + " (" + toString(numEdges) + " edges)\n");
125  const long startMillis = SysUtils::getCurrentMillis();
126  // init queue
127  std::vector<CHInfo*> queue; // max heap: edge to be contracted is front
128  // reset previous connections etc
129  for (int i = 0; i < numEdges; i++) {
130  myCHInfos[i].resetContractionState();
131  result->forwardUplinks.push_back(std::vector<Connection>());
132  result->backwardUplinks.push_back(std::vector<Connection>());
133  }
134  // copy connections from the original net
135  const double time_seconds = STEPS2TIME(time); // timelines store seconds!
136  for (int i = 0; i < numEdges; i++) {
137  synchronize(myCHInfos[i], time_seconds, vehicle, effortProvider);
138  }
139  // synchronization is finished. now we can compute priorities for the first time
140  for (int i = 0; i < numEdges; i++) {
141  myCHInfos[i].updatePriority(mySPTree);
142  queue.push_back(&(myCHInfos[i]));
143  }
144  make_heap(queue.begin(), queue.end(), myCmp);
145  int contractionRank = 0;
146  // contraction loop
147  while (!queue.empty()) {
148  while (tryUpdateFront(queue)) {}
149  CHInfo* max = queue.front();
150  max->rank = contractionRank;
151 #ifdef CHRouter_DEBUG_CONTRACTION
152  std::cout << "contracting '" << max->edge->getID() << "' with prio: " << max->priority << " (rank " << contractionRank << ")\n";
153 #endif
154  const E* const edge = max->edge;
155  // add outgoing connections to the forward search
156  const int edgeID = edge->getNumericalID();
157  for (typename CHConnections::const_iterator it = max->followers.begin(); it != max->followers.end(); it++) {
158  const CHConnection& con = *it;
159  result->forwardUplinks[edgeID].push_back(Connection(con.target->edge->getNumericalID(), con.cost, con.permissions));
160  disconnect(con.target->approaching, max);
161  con.target->updatePriority(0);
162  }
163  // add incoming connections to the backward search
164  for (typename CHConnections::const_iterator it = max->approaching.begin(); it != max->approaching.end(); it++) {
165  const CHConnection& con = *it;
166  result->backwardUplinks[edgeID].push_back(Connection(con.target->edge->getNumericalID(), con.cost, con.permissions));
167  disconnect(con.target->followers, max);
168  con.target->updatePriority(0);
169  }
170  // add shortcuts to the net
171  for (typename std::vector<Shortcut>::const_iterator it = max->shortcuts.begin(); it != max->shortcuts.end(); it++) {
172  const ConstEdgePair& edgePair = it->edgePair;
173  result->shortcuts[edgePair] = edge;
174  CHInfo* from = getCHInfo(edgePair.first);
175  CHInfo* to = getCHInfo(edgePair.second);
176  from->followers.push_back(CHConnection(to, it->cost, it->permissions, it->underlying));
177  to->approaching.push_back(CHConnection(from, it->cost, it->permissions, it->underlying));
178  }
179  // if you need to debug the chrouter with MSVC uncomment the following line, hierarchy building will get slower and the hierarchy may change though
180  //make_heap(queue.begin(), queue.end(), myCmp);
181  // remove from queue
182  pop_heap(queue.begin(), queue.end(), myCmp);
183  queue.pop_back();
184  /*
185  if (contractionRank % 10000 == 0) {
186  // update all and rebuild queue
187  for (typename std::vector<CHInfo*>::iterator it = queue.begin(); it != queue.end(); ++it) {
188  (*it)->updatePriority(mySPTree);
189  }
190  make_heap(queue.begin(), queue.end(), myCmp);
191  }
192  */
193  contractionRank++;
194  }
195  // reporting
196  const long duration = SysUtils::getCurrentMillis() - startMillis;
197  WRITE_MESSAGE("Created " + toString(result->shortcuts.size()) + " shortcuts.");
198  WRITE_MESSAGE("Recomputed priority " + toString(myUpdateCount) + " times.");
199  MsgHandler::getMessageInstance()->endProcessMsg("done (" + toString(duration) + "ms).");
201  myUpdateCount = 0;
202  return result;
203  }
204 
205 private:
206  struct Shortcut {
207  Shortcut(ConstEdgePair e, double c, int u, SVCPermissions p):
208  edgePair(e), cost(c), underlying(u), permissions(p) {}
209  ConstEdgePair edgePair;
210  double cost;
213  };
214 
215 
216  class CHInfo;
217 
219  class CHConnection {
220  public:
221  CHConnection(CHInfo* t, double c, SVCPermissions p, int u):
222  target(t), cost(c), permissions(p), underlying(u) {}
224  double cost;
228  };
229 
230  typedef std::vector<CHConnection> CHConnections;
231  typedef std::pair<const CHConnection*, const CHConnection*> CHConnectionPair;
232  typedef std::vector<CHConnectionPair> CHConnectionPairs;
233 
234  /* @brief container class to use when building the contraction hierarchy.
235  * instances are reused every time the hierarchy is rebuilt (new time slice)
236  * but they must be synchronized first */
237  class CHInfo {
238  public:
240  CHInfo(const E* e) :
241  edge(e),
242  contractedNeighbors(0),
243  rank(-1),
244  level(0),
245  underlyingTotal(0),
246  visited(false),
247  traveltime(std::numeric_limits<double>::max()) {
248  }
249 
252  if (spTree != 0) {
253  updateShortcuts(spTree);
254  updateLevel();
255  } else {
256  contractedNeighbors += 1; // called when a connected edge was contracted
257  }
258  const double oldPriority = priority;
259  // priority term as used by abraham []
260  const int edge_difference = (int)followers.size() + (int)approaching.size() - 2 * (int)shortcuts.size();
261  priority = (double)(2 * edge_difference - contractedNeighbors - underlyingTotal - 5 * level);
262  return priority != oldPriority;
263  }
264 
267  const bool validatePermissions = spTree->validatePermissions();
268 #ifdef CHRouter_DEBUG_CONTRACTION_DEGREE
269  const int degree = (int)approaching.size() + (int)followers.size();
270  std::cout << "computing shortcuts for '" + edge->getID() + "' with degree " + toString(degree) + "\n";
271 #endif
272  shortcuts.clear();
273  underlyingTotal = 0;
274  for (typename CHConnections::iterator it_a = approaching.begin(); it_a != approaching.end(); it_a++) {
275  CHConnection& aInfo = *it_a;
276  // build shortest path tree in a fixed neighborhood
277  spTree->rebuildFrom(aInfo.target, this);
278  for (typename CHConnections::iterator it_f = followers.begin(); it_f != followers.end(); it_f++) {
279  CHConnection& fInfo = *it_f;
280  const double viaCost = aInfo.cost + fInfo.cost;
281  const SVCPermissions viaPermissions = (aInfo.permissions & fInfo.permissions);
282  if (fInfo.target->traveltime > viaCost) {
283  // found no faster path -> we need a shortcut via edge
284 #ifdef CHRouter_DEBUG_CONTRACTION_WITNESSES
285  debugNoWitness(aInfo, fInfo);
286 #endif
287  const int underlying = aInfo.underlying + fInfo.underlying;
288  underlyingTotal += underlying;
289  shortcuts.push_back(Shortcut(ConstEdgePair(aInfo.target->edge, fInfo.target->edge),
290  viaCost, underlying, viaPermissions));
291 
292  } else if (validatePermissions) {
293  if ((fInfo.target->permissions & viaPermissions) != viaPermissions) {
294  // witness has weaker restrictions. try to find another witness
295  spTree->registerForValidation(&aInfo, &fInfo);
296  } else {
297 #ifdef CHRouter_DEBUG_CONTRACTION_WITNESSES
298  debugNoWitness(aInfo, fInfo);
299 #endif
300  }
301  } else {
302 #ifdef CHRouter_DEBUG_CONTRACTION_WITNESSES
303  debugNoWitness(aInfo, fInfo);
304 #endif
305  }
306  }
307  }
308  // insert shortcuts needed due to unmet permissions
309  if (validatePermissions) {
310  const CHConnectionPairs& pairs = spTree->getNeededShortcuts(this);
311  for (typename CHConnectionPairs::const_iterator it = pairs.begin(); it != pairs.end(); ++it) {
312  const CHConnection* aInfo = it->first;
313  const CHConnection* fInfo = it->second;
314  const double viaCost = aInfo->cost + fInfo->cost;
315  const SVCPermissions viaPermissions = (aInfo->permissions & fInfo->permissions);
316  const int underlying = aInfo->underlying + fInfo->underlying;
317  underlyingTotal += underlying;
318  shortcuts.push_back(Shortcut(ConstEdgePair(aInfo->target->edge, fInfo->target->edge),
319  viaCost, underlying, viaPermissions));
320  }
321  }
322  }
323 
324 
325  // update level as defined by Abraham
326  void updateLevel() {
327  int maxLower = std::numeric_limits<int>::min();
328  int otherRank;
329  for (typename CHConnections::iterator it = approaching.begin(); it != approaching.end(); it++) {
330  otherRank = it->target->rank;
331  if (otherRank < rank) {
332  maxLower = MAX2(rank, maxLower);
333  }
334  }
335  for (typename CHConnections::iterator it = followers.begin(); it != followers.end(); it++) {
336  otherRank = it->target->rank;
337  if (otherRank < rank) {
338  maxLower = MAX2(rank, maxLower);
339  }
340  }
341  if (maxLower == std::numeric_limits<int>::min()) {
342  level = 0;
343  } else {
344  level = maxLower + 1;
345  }
346  }
347 
348  // resets state before rebuilding the hierarchy
350  contractedNeighbors = 0;
351  rank = -1;
352  level = 0;
353  underlyingTotal = 0;
354  shortcuts.clear();
355  followers.clear();
356  approaching.clear();
357  }
358 
359 
361  const E* edge;
363  double priority;
365  std::vector<Shortcut> shortcuts;
368  int rank;
369  int level;
371 
373  CHConnections followers;
374  CHConnections approaching;
375 
376 
378  bool visited;
380  double traveltime;
382  int depth;
384  // @note: we may miss some witness paths by making traveltime the only
385  // criteria durinng search
387 
388  inline void reset() {
389  traveltime = std::numeric_limits<double>::max();
390  visited = false;
391  }
392 
393 
395  inline void debugNoWitness(const CHConnection& aInfo, const CHConnection& fInfo) {
396  std::cout << "adding shortcut between " << aInfo.target->edge->getID() << ", " << fInfo.target->edge->getID() << " via " << edge->getID() << "\n";
397  }
398 
399  inline void debugWitness(const CHConnection& aInfo, const CHConnection& fInfo) {
400  const double viaCost = aInfo.cost + fInfo.cost;
401  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";
402  }
403 
404  };
405 
406 
412  public:
414  bool operator()(const CHInfo* a, const CHInfo* b) const {
415  if (a->priority == b->priority) {
416  return a->edge->getNumericalID() > b->edge->getNumericalID();
417  } else {
418  return a->priority < b->priority;
419  };
420  }
421  };
422 
423 
424  inline CHInfo* getCHInfo(const E* const edge) {
425  return &(myCHInfos[edge->getNumericalID()]);
426  }
427 
428 
430  void synchronize(CHInfo& info, double time, const V* const vehicle, const SUMOAbstractRouter<E, V>* effortProvider) {
431  // forward and backward connections are used only in forward search,
432  // thus approaching costs are those of the approaching edge and not of the edge itself
433  const bool prune = !mySPTree->validatePermissions();
434  const E* const edge = info.edge;
435  if (prune && ((edge->getPermissions() & mySVC) != mySVC)) {
436  return;
437  }
438  const double cost = effortProvider->getEffort(edge, vehicle, time);
439 
440  const std::vector<E*>& successors = edge->getSuccessors(mySVC);
441  for (typename std::vector<E*>::const_iterator it = successors.begin(); it != successors.end(); ++it) {
442  const E* fEdge = *it;
443  if (prune && ((fEdge->getPermissions() & mySVC) != mySVC)) {
444  continue;
445  }
446  CHInfo* follower = getCHInfo(fEdge);
447  SVCPermissions permissions = (edge->getPermissions() & follower->edge->getPermissions());
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  pop_heap(queue.begin(), queue.end(), myCmp);
481  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 
bool operator()(const CHInfo *a, const CHInfo *b) const
Comparing method.
Definition: CHBuilder.h:414
CHInfoComparator myCmp
Comparator for contraction priority.
Definition: CHBuilder.h:508
bool tryUpdateFront(std::vector< CHInfo *> &queue)
tries to update the priority of the first edge
Definition: CHBuilder.h:472
double getEffort(const E *const e, const V *const v, double t) const
int depth
number of edges from start
Definition: CHBuilder.h:382
#define min(a, b)
Definition: polyfonts.c:66
SUMOVehicleClass
Definition of vehicle classes to differ between different lane usage and authority types...
int contractedNeighbors
priority subterms
Definition: CHBuilder.h:367
Connection(int t, double c, SVCPermissions p)
Definition: CHBuilder.h:80
CHInfo * getCHInfo(const E *const edge)
Definition: CHBuilder.h:424
void resetContractionState()
Definition: CHBuilder.h:349
std::map< ConstEdgePair, const E * > ShortcutVia
Definition: CHBuilder.h:87
SVCPermissions permissions
Definition: CHBuilder.h:83
void debugWitness(const CHConnection &aInfo, const CHConnection &fInfo)
Definition: CHBuilder.h:399
Shortcut(ConstEdgePair e, double c, int u, SVCPermissions p)
Definition: CHBuilder.h:207
int SVCPermissions
bitset where each bit declares whether a certain SVC may use this edge/lane
const std::vector< E * > & myEdges
all edges with numerical ids
Definition: CHBuilder.h:499
MsgHandler *const myErrorMsgHandler
the handler for routing errors
Definition: CHBuilder.h:502
std::string time2string(SUMOTime t)
Definition: SUMOTime.cpp:60
void debugPrintQueue(std::vector< CHInfo *> &queue)
Definition: CHBuilder.h:489
T MAX2(T a, T b)
Definition: StdDefs.h:70
SVCPermissions permissions
Definition: CHBuilder.h:225
int underlying
the number of connections underlying this connection
Definition: CHBuilder.h:227
bool updatePriority(SPTree< CHInfo, CHConnection > *spTree)
recompute the contraction priority and report whether it changed
Definition: CHBuilder.h:251
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:430
CHConnections approaching
Definition: CHBuilder.h:374
const SUMOVehicleClass mySVC
the permissions for which the hierarchy was constructed
Definition: CHBuilder.h:514
CHConnections followers
connections (only valid after synchronization)
Definition: CHBuilder.h:373
int myUpdateCount
counters for performance logging
Definition: CHBuilder.h:517
void debugNoWitness(const CHConnection &aInfo, const CHConnection &fInfo)
debugging methods
Definition: CHBuilder.h:395
SPTree< CHInfo, CHConnection > * mySPTree
the shortest path tree to use when searching for shortcuts
Definition: CHBuilder.h:511
double traveltime
Effort to reach the edge.
Definition: CHBuilder.h:380
void registerForValidation(const C *aInfo, const C *fInfo)
save source/target pair for later validation
Definition: SPTree.h:142
std::vector< std::vector< Connection > > backwardUplinks
Definition: CHBuilder.h:91
#define max(a, b)
Definition: polyfonts.c:65
ConstEdgePair edgePair
Definition: CHBuilder.h:209
std::string toString(const T &t, std::streamsize accuracy=gPrecision)
Definition: ToString.h:56
SVCPermissions permissions
Definition: CHBuilder.h:212
const CHConnectionPairs & getNeededShortcuts(const E *excluded)
Definition: SPTree.h:150
#define STEPS2TIME(x)
Definition: SUMOTime.h:65
#define PROGRESS_BEGIN_MESSAGE(msg)
Definition: MsgHandler.h:202
static MsgHandler * getMessageInstance()
Returns the instance to add normal messages to.
Definition: MsgHandler.cpp:58
std::vector< CHConnectionPair > CHConnectionPairs
Definition: CHBuilder.h:232
std::pair< const E *, const E * > ConstEdgePair
Definition: CHBuilder.h:86
StringBijection< SUMOVehicleClass > SumoVehicleClassStrings(sumoVehicleClassStringInitializer, SVC_CUSTOM2, false)
virtual ~CHBuilder()
Destructor.
Definition: CHBuilder.h:113
std::vector< std::vector< Connection > > forwardUplinks
Definition: CHBuilder.h:90
void disconnect(CHConnections &connections, CHInfo *other)
remove all connections to/from the given edge (assume it exists only once)
Definition: CHBuilder.h:459
Definition: SPTree.h:46
CHConnection(CHInfo *t, double c, SVCPermissions p, int u)
Definition: CHBuilder.h:221
double priority
The contraction priority.
Definition: CHBuilder.h:363
CHBuilder(const std::vector< E *> &edges, bool unbuildIsWarning, const SUMOVehicleClass svc, bool validatePermissions)
Constructor.
Definition: CHBuilder.h:99
bool visited
members used in SPTree
Definition: CHBuilder.h:378
const E * edge
The current edge - not const since it may receive shortcut edges.
Definition: CHBuilder.h:361
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
CHBuilder & operator=(const CHBuilder &s)
Invalidated assignment operator.
const Hierarchy * buildContractionHierarchy(SUMOTime time, const V *const vehicle, const SUMOAbstractRouter< E, V > *effortProvider)
Definition: CHBuilder.h:118
std::pair< const CHConnection *, const CHConnection * > CHConnectionPair
Definition: CHBuilder.h:231
SVCPermissions permissions
the permissions when reaching this edge on the fastest path
Definition: CHBuilder.h:386
Forward/backward connection with associated FORWARD cost.
Definition: CHBuilder.h:219
CHInfo(const E *e)
Constructor.
Definition: CHBuilder.h:240
std::vector< CHInfo > myCHInfos
static vector for lookup
Definition: CHBuilder.h:505
long long int SUMOTime
Definition: TraCIDefs.h:52
std::vector< CHConnection > CHConnections
Definition: CHBuilder.h:230
bool validatePermissions()
whether permissions should be validated;
Definition: SPTree.h:137
static long getCurrentMillis()
Returns the current time in milliseconds.
Definition: SysUtils.cpp:46
#define PROGRESS_DONE_MESSAGE()
Definition: MsgHandler.h:203
Forward/backward connection with associated forward/backward cost.
Definition: CHBuilder.h:78
#define WRITE_MESSAGE(msg)
Definition: MsgHandler.h:201
std::vector< Shortcut > shortcuts
The needed shortcuts.
Definition: CHBuilder.h:365
void updateLevel()
Definition: CHBuilder.h:326
ShortcutVia shortcuts
Definition: CHBuilder.h:89
void updateShortcuts(SPTree< CHInfo, CHConnection > *spTree)
compute needed shortcuts when contracting this edge
Definition: CHBuilder.h:266
void endProcessMsg(std::string msg)
Ends a process information.
Definition: MsgHandler.cpp:127