64 template<
class E,
class V>
92 CHBuilder(
const std::vector<E*>& edges,
bool unbuildIsWarning,
94 bool validatePermissions):
100 for (
typename std::vector<E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
113 const int numEdges = (int)
myCHInfos.size();
114 const std::string vClass = (
mySPTree->validatePermissions() ?
120 std::vector<CHInfo*> queue;
122 for (
int i = 0; i < numEdges; i++) {
129 for (
int i = 0; i < numEdges; i++) {
133 for (
int i = 0; i < numEdges; i++) {
137 make_heap(queue.begin(), queue.end(),
myCmp);
138 int contractionRank = 0;
140 while (!queue.empty()) {
142 CHInfo* max = queue.front();
143 max->
rank = contractionRank;
144 #ifdef CHRouter_DEBUG_CONTRACTION 145 std::cout <<
"contracting '" << max->
edge->getID() <<
"' with prio: " << max->
priority <<
" (rank " << contractionRank <<
")\n";
147 const E*
const edge = max->
edge;
149 const int edgeID = edge->getNumericalID();
150 for (
typename CHConnections::const_iterator it = max->
followers.begin(); it != max->
followers.end(); it++) {
157 for (
typename CHConnections::const_iterator it = max->
approaching.begin(); it != max->
approaching.end(); it++) {
164 for (
typename std::vector<Shortcut>::const_iterator it = max->
shortcuts.begin(); it != max->
shortcuts.end(); it++) {
165 const ConstEdgePair& edgePair = it->edgePair;
175 pop_heap(queue.begin(), queue.end(),
myCmp);
236 contractedNeighbors(0),
241 traveltime(std::numeric_limits<double>::max()),
249 updateShortcuts(spTree);
252 contractedNeighbors += 1;
254 const double oldPriority = priority;
256 const int edge_difference = (int)followers.size() + (int)approaching.size() - 2 * (int)shortcuts.size();
257 priority = (double)(2 * edge_difference - contractedNeighbors - underlyingTotal - 5 * level);
258 return priority != oldPriority;
264 #ifdef CHRouter_DEBUG_CONTRACTION_DEGREE 265 const int degree = (int)approaching.size() + (int)followers.size();
266 std::cout <<
"computing shortcuts for '" + edge->getID() +
"' with degree " +
toString(degree) +
"\n";
270 for (
typename CHConnections::iterator it_a = approaching.begin(); it_a != approaching.end(); it_a++) {
274 for (
typename CHConnections::iterator it_f = followers.begin(); it_f != followers.end(); it_f++) {
276 const double viaCost = aInfo.
cost + fInfo.
cost;
280 #ifdef CHRouter_DEBUG_CONTRACTION_WITNESSES 281 debugNoWitness(aInfo, fInfo);
284 underlyingTotal += underlying;
286 viaCost, underlying, viaPermissions));
288 }
else if (validatePermissions) {
293 #ifdef CHRouter_DEBUG_CONTRACTION_WITNESSES 294 debugNoWitness(aInfo, fInfo);
298 #ifdef CHRouter_DEBUG_CONTRACTION_WITNESSES 299 debugNoWitness(aInfo, fInfo);
305 if (validatePermissions) {
307 for (
typename CHConnectionPairs::const_iterator it = pairs.begin(); it != pairs.end(); ++it) {
310 const double viaCost = aInfo->
cost + fInfo->
cost;
313 underlyingTotal += underlying;
315 viaCost, underlying, viaPermissions));
323 int maxLower = std::numeric_limits<int>::min();
325 for (
typename CHConnections::iterator it = approaching.begin(); it != approaching.end(); it++) {
326 otherRank = it->target->rank;
327 if (otherRank < rank) {
328 maxLower =
MAX2(rank, maxLower);
331 for (
typename CHConnections::iterator it = followers.begin(); it != followers.end(); it++) {
332 otherRank = it->target->rank;
333 if (otherRank < rank) {
334 maxLower =
MAX2(rank, maxLower);
337 if (maxLower == std::numeric_limits<int>::min()) {
340 level = maxLower + 1;
346 contractedNeighbors = 0;
385 traveltime = std::numeric_limits<double>::max();
392 std::cout <<
"adding shortcut between " << aInfo.
target->
edge->getID() <<
", " << fInfo.
target->
edge->getID() <<
" via " << edge->getID() <<
"\n";
396 const double viaCost = aInfo.
cost + fInfo.
cost;
397 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";
412 return a->
edge->getNumericalID() > b->
edge->getNumericalID();
421 return &(
myCHInfos[edge->getNumericalID()]);
429 const bool prune = !
mySPTree->validatePermissions();
430 const E*
const edge = info.
edge;
431 if (prune && ((edge->getPermissions() &
mySVC) !=
mySVC)) {
434 const double baseCost = effortProvider->
getEffort(edge, vehicle, time);
436 for (
const std::pair<const E*, const E*>& successor : edge->getViaSuccessors(
mySVC)) {
437 const E* fEdge = successor.first;
438 if (prune && ((fEdge->getPermissions() &
mySVC) !=
mySVC)) {
443 double cost = baseCost;
444 const E* viaEdge = successor.second;
445 while (viaEdge !=
nullptr && viaEdge->isInternal()) {
446 cost += effortProvider->
getEffort(viaEdge, vehicle, time);
447 viaEdge = viaEdge->getViaSuccessors().front().first;
452 #ifdef CHRouter_DEBUG_WEIGHTS 453 std::cout << time <<
": " << edge->getID() <<
" cost: " <<
cost <<
"\n";
461 for (
typename CHConnections::iterator it = connections.begin(); it != connections.end(); it++) {
462 if (it->target == other) {
463 connections.erase(it);
475 CHInfo* max = queue.front();
476 #ifdef CHRouter_DEBUG_CONTRACTION_QUEUE 477 std::cout <<
"updating '" << max->
edge->getID() <<
"'\n";
481 pop_heap(queue.begin(), queue.end(),
myCmp);
482 push_heap(queue.begin(), queue.end(),
myCmp);
491 for (
typename std::vector<CHInfo*>::iterator it = queue.begin(); it != queue.end(); it++) {
493 std::cout <<
"(" << chInfo->
edge->getID() <<
"," << chInfo->
priority <<
") ";
bool operator()(const CHInfo *a, const CHInfo *b) const
Comparing method.
CHInfoComparator myCmp
Comparator for contraction priority.
bool tryUpdateFront(std::vector< CHInfo *> &queue)
tries to update the priority of the first edge
double getEffort(const E *const e, const V *const v, double t) const
int depth
number of edges from start
SUMOVehicleClass
Definition of vehicle classes to differ between different lane usage and authority types...
int contractedNeighbors
priority subterms
Connection(int t, double c, SVCPermissions p)
CHInfo * getCHInfo(const E *const edge)
void resetContractionState()
std::map< ConstEdgePair, const E * > ShortcutVia
SVCPermissions permissions
void debugWitness(const CHConnection &aInfo, const CHConnection &fInfo)
Shortcut(ConstEdgePair e, double c, int u, SVCPermissions p)
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
MsgHandler *const myErrorMsgHandler
the handler for routing errors
std::string time2string(SUMOTime t)
void debugPrintQueue(std::vector< CHInfo *> &queue)
SVCPermissions permissions
int underlying
the number of connections underlying this connection
bool updatePriority(SPTree< CHInfo, CHConnection > *spTree)
recompute the contraction priority and report whether it changed
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) ...
CHConnections approaching
const SUMOVehicleClass mySVC
the permissions for which the hierarchy was constructed
CHConnections followers
connections (only valid after synchronization)
int myUpdateCount
counters for performance logging
void debugNoWitness(const CHConnection &aInfo, const CHConnection &fInfo)
debugging methods
SPTree< CHInfo, CHConnection > * mySPTree
the shortest path tree to use when searching for shortcuts
double traveltime
Effort to reach the edge.
void registerForValidation(const C *aInfo, const C *fInfo)
save source/target pair for later validation
std::vector< std::vector< Connection > > backwardUplinks
std::string toString(const T &t, std::streamsize accuracy=gPrecision)
SVCPermissions permissions
const CHConnectionPairs & getNeededShortcuts(const E *excluded)
#define PROGRESS_BEGIN_MESSAGE(msg)
static MsgHandler * getMessageInstance()
Returns the instance to add normal messages to.
std::vector< CHConnectionPair > CHConnectionPairs
std::pair< const E *, const E * > ConstEdgePair
StringBijection< SUMOVehicleClass > SumoVehicleClassStrings(sumoVehicleClassStringInitializer, SVC_CUSTOM2, false)
virtual ~CHBuilder()
Destructor.
std::vector< std::vector< Connection > > forwardUplinks
void disconnect(CHConnections &connections, CHInfo *other)
remove all connections to/from the given edge (assume it exists only once)
CHConnection(CHInfo *t, double c, SVCPermissions p, int u)
double priority
The contraction priority.
CHBuilder(const std::vector< E *> &edges, bool unbuildIsWarning, const SUMOVehicleClass svc, bool validatePermissions)
Constructor.
bool visited
members used in SPTree
const E * edge
The current edge - not const since it may receive shortcut edges.
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 ...
CHBuilder & operator=(const CHBuilder &s)
Invalidated assignment operator.
const Hierarchy * buildContractionHierarchy(SUMOTime time, const V *const vehicle, const SUMOAbstractRouter< E, V > *effortProvider)
std::pair< const CHConnection *, const CHConnection * > CHConnectionPair
SVCPermissions permissions
the permissions when reaching this edge on the fastest path
Forward/backward connection with associated FORWARD cost.
CHInfo(const E *e)
Constructor.
std::vector< CHInfo > myCHInfos
static vector for lookup
std::vector< CHConnection > CHConnections
bool validatePermissions()
whether permissions should be validated;
static long getCurrentMillis()
Returns the current time in milliseconds.
#define PROGRESS_DONE_MESSAGE()
Forward/backward connection with associated forward/backward cost.
#define WRITE_MESSAGE(msg)
std::vector< Shortcut > shortcuts
The needed shortcuts.
vehicles ignoring classes
void updateShortcuts(SPTree< CHInfo, CHConnection > *spTree)
compute needed shortcuts when contracting this edge
void endProcessMsg(std::string msg)
Ends a process information.