61 template<
class E,
class V>
89 CHBuilder(
const std::vector<E*>& edges,
bool unbuildIsWarning,
91 bool validatePermissions):
97 for (
typename std::vector<E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
110 const int numEdges = (int)
myCHInfos.size();
111 const std::string vClass = (
mySPTree->validatePermissions() ?
117 std::vector<CHInfo*> queue;
119 for (
int i = 0; i < numEdges; i++) {
126 for (
int i = 0; i < numEdges; i++) {
130 for (
int i = 0; i < numEdges; i++) {
134 std::make_heap(queue.begin(), queue.end(),
myCmp);
135 int contractionRank = 0;
137 while (!queue.empty()) {
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";
144 const E*
const edge = max->
edge;
146 const int edgeID = edge->getNumericalID();
147 for (
typename CHConnections::const_iterator it = max->
followers.begin(); it != max->
followers.end(); it++) {
154 for (
typename CHConnections::const_iterator it = max->
approaching.begin(); it != max->
approaching.end(); it++) {
161 for (
typename std::vector<Shortcut>::const_iterator it = max->
shortcuts.begin(); it != max->
shortcuts.end(); it++) {
172 std::pop_heap(queue.begin(), queue.end(),
myCmp);
238 traveltime(std::numeric_limits<double>::max()),
251 const double oldPriority =
priority;
261 #ifdef CHRouter_DEBUG_CONTRACTION_DEGREE
263 std::cout <<
"computing shortcuts for '" +
edge->getID() +
"' with degree " +
toString(degree) +
"\n";
271 for (
typename CHConnections::iterator it_f =
followers.begin(); it_f !=
followers.end(); it_f++) {
273 const double viaCost = aInfo.
cost + fInfo.
cost;
277 #ifdef CHRouter_DEBUG_CONTRACTION_WITNESSES
283 viaCost, underlying, viaPermissions));
285 }
else if (validatePermissions) {
290 #ifdef CHRouter_DEBUG_CONTRACTION_WITNESSES
295 #ifdef CHRouter_DEBUG_CONTRACTION_WITNESSES
302 if (validatePermissions) {
304 for (
typename CHConnectionPairs::const_iterator it = pairs.begin(); it != pairs.end(); ++it) {
307 const double viaCost = aInfo->
cost + fInfo->
cost;
312 viaCost, underlying, viaPermissions));
320 int maxLower = std::numeric_limits<int>::min();
323 otherRank = it->target->rank;
324 if (otherRank <
rank) {
328 for (
typename CHConnections::iterator it =
followers.begin(); it !=
followers.end(); it++) {
329 otherRank = it->target->rank;
330 if (otherRank <
rank) {
334 if (maxLower == std::numeric_limits<int>::min()) {
337 level = maxLower + 1;
382 traveltime = std::numeric_limits<double>::max();
389 std::cout <<
"adding shortcut between " << aInfo.
target->
edge->getID() <<
", " << fInfo.
target->
edge->getID() <<
" via " <<
edge->getID() <<
"\n";
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";
409 return a->
edge->getNumericalID() > b->
edge->getNumericalID();
418 return &(
myCHInfos[edge->getNumericalID()]);
426 const bool prune = !
mySPTree->validatePermissions();
427 const E*
const edge = info.
edge;
428 if (prune && ((edge->getPermissions() &
mySVC) !=
mySVC)) {
431 const double baseCost = effortProvider->
getEffort(edge, vehicle, time);
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)) {
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;
449 #ifdef CHRouter_DEBUG_WEIGHTS
450 std::cout << time <<
": " << edge->getID() <<
" cost: " << cost <<
"\n";
458 for (
typename CHConnections::iterator it = connections.begin(); it != connections.end(); it++) {
459 if (it->target == other) {
460 connections.erase(it);
472 CHInfo* max = queue.front();
473 #ifdef CHRouter_DEBUG_CONTRACTION_QUEUE
474 std::cout <<
"updating '" << max->
edge->getID() <<
"'\n";
478 std::pop_heap(queue.begin(), queue.end(),
myCmp);
479 std::push_heap(queue.begin(), queue.end(),
myCmp);
488 for (
typename std::vector<CHInfo*>::iterator it = queue.begin(); it != queue.end(); it++) {
490 std::cout <<
"(" << chInfo->
edge->getID() <<
"," << chInfo->
priority <<
") ";
#define WRITE_MESSAGE(msg)
#define PROGRESS_DONE_MESSAGE()
#define PROGRESS_BEGIN_MESSAGE(msg)
std::string time2string(SUMOTime t)
convert SUMOTime to string
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
std::string toString(const T &t, std::streamsize accuracy=gPrecision)
Forward/backward connection with associated FORWARD cost.
int underlying
the number of connections underlying this connection
SVCPermissions permissions
CHConnection(CHInfo *t, double c, SVCPermissions p, int u)
bool operator()(const CHInfo *a, const CHInfo *b) const
Comparing method.
void updateShortcuts(SPTree< CHInfo, CHConnection > *spTree)
compute needed shortcuts when contracting this edge
void resetContractionState()
double traveltime
Effort to reach the edge.
void debugWitness(const CHConnection &aInfo, const CHConnection &fInfo)
int contractedNeighbors
priority subterms
bool visited
members used in SPTree
double priority
The contraction priority.
bool updatePriority(SPTree< CHInfo, CHConnection > *spTree)
recompute the contraction priority and report whether it changed
SVCPermissions permissions
the permissions when reaching this edge on the fastest path
std::vector< Shortcut > shortcuts
The needed shortcuts.
int depth
number of edges from start
CHConnections followers
connections (only valid after synchronization)
const E * edge
The current edge - not const since it may receive shortcut edges.
CHInfo(const E *e)
Constructor.
CHConnections approaching
void debugNoWitness(const CHConnection &aInfo, const CHConnection &fInfo)
debugging methods
Forward/backward connection with associated forward/backward cost.
SVCPermissions permissions
Connection(int t, double c, SVCPermissions p)
CHInfo * getCHInfo(const E *const edge)
CHBuilder & operator=(const CHBuilder &s)
Invalidated assignment operator.
bool tryUpdateFront(std::vector< CHInfo * > &queue)
tries to update the priority of the first edge
virtual ~CHBuilder()
Destructor.
std::pair< const CHConnection *, const CHConnection * > CHConnectionPair
std::map< ConstEdgePair, const E * > ShortcutVia
SPTree< CHInfo, CHConnection > * mySPTree
the shortest path tree to use when searching for shortcuts
CHInfoComparator myCmp
Comparator for contraction priority.
Hierarchy * buildContractionHierarchy(SUMOTime time, const V *const vehicle, const SUMOAbstractRouter< E, V > *effortProvider)
const std::vector< E * > & myEdges
all edges with numerical ids
std::vector< CHConnection > CHConnections
std::pair< const E *, const E * > ConstEdgePair
CHBuilder(const std::vector< E * > &edges, bool unbuildIsWarning, const SUMOVehicleClass svc, bool validatePermissions)
Constructor.
std::vector< CHConnectionPair > CHConnectionPairs
std::vector< CHInfo > myCHInfos
static vector for lookup
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)
void debugPrintQueue(std::vector< CHInfo * > &queue)
const SUMOVehicleClass mySVC
the permissions for which the hierarchy was constructed
void disconnect(CHConnections &connections, CHInfo *other)
remove all connections to/from the given edge (assume it exists only once)
MsgHandler *const myErrorMsgHandler
the handler for routing errors
int myUpdateCount
counters for performance logging
virtual void endProcessMsg(std::string msg)
Ends a process information.
static MsgHandler * getMessageInstance()
Returns the instance to add normal messages to.
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 ...
bool validatePermissions()
whether permissions should be validated;
const CHConnectionPairs & getNeededShortcuts(const E *excluded)
void registerForValidation(const C *aInfo, const C *fInfo)
save source/target pair for later validation
double getEffort(const E *const e, const V *const v, double t) const
static long getCurrentMillis()
Returns the current time in milliseconds.
std::vector< std::vector< Connection > > backwardUplinks
std::vector< std::vector< Connection > > forwardUplinks
SVCPermissions permissions
Shortcut(ConstEdgePair e, double c, int u, SVCPermissions p)