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