71 template<
class E,
class V>
99 CHBuilder(
const std::vector<E*>& edges,
bool unbuildIsWarning,
101 bool validatePermissions):
107 for (
typename std::vector<E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
120 const int numEdges = (int)
myCHInfos.size();
121 const std::string vClass = (
mySPTree->validatePermissions() ?
127 std::vector<CHInfo*> queue;
129 for (
int i = 0; i < numEdges; i++) {
136 for (
int i = 0; i < numEdges; i++) {
140 for (
int i = 0; i < numEdges; i++) {
144 make_heap(queue.begin(), queue.end(),
myCmp);
145 int contractionRank = 0;
147 while (!queue.empty()) {
150 max->
rank = contractionRank;
151 #ifdef CHRouter_DEBUG_CONTRACTION 152 std::cout <<
"contracting '" << max->
edge->getID() <<
"' with prio: " << max->
priority <<
" (rank " << contractionRank <<
")\n";
154 const E*
const edge = max->
edge;
156 const int edgeID = edge->getNumericalID();
157 for (
typename CHConnections::const_iterator it = max->
followers.begin(); it != max->
followers.end(); it++) {
164 for (
typename CHConnections::const_iterator it = max->
approaching.begin(); it != max->
approaching.end(); it++) {
171 for (
typename std::vector<Shortcut>::const_iterator it = max->
shortcuts.begin(); it != max->
shortcuts.end(); it++) {
172 const ConstEdgePair& edgePair = it->edgePair;
182 pop_heap(queue.begin(), queue.end(),
myCmp);
242 contractedNeighbors(0),
247 traveltime(std::numeric_limits<double>::
max()) {
253 updateShortcuts(spTree);
256 contractedNeighbors += 1;
258 const double oldPriority = priority;
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;
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";
274 for (
typename CHConnections::iterator it_a = approaching.begin(); it_a != approaching.end(); it_a++) {
278 for (
typename CHConnections::iterator it_f = followers.begin(); it_f != followers.end(); it_f++) {
280 const double viaCost = aInfo.
cost + fInfo.
cost;
284 #ifdef CHRouter_DEBUG_CONTRACTION_WITNESSES 285 debugNoWitness(aInfo, fInfo);
288 underlyingTotal += underlying;
290 viaCost, underlying, viaPermissions));
292 }
else if (validatePermissions) {
297 #ifdef CHRouter_DEBUG_CONTRACTION_WITNESSES 298 debugNoWitness(aInfo, fInfo);
302 #ifdef CHRouter_DEBUG_CONTRACTION_WITNESSES 303 debugNoWitness(aInfo, fInfo);
309 if (validatePermissions) {
311 for (
typename CHConnectionPairs::const_iterator it = pairs.begin(); it != pairs.end(); ++it) {
314 const double viaCost = aInfo->
cost + fInfo->
cost;
317 underlyingTotal += underlying;
319 viaCost, underlying, viaPermissions));
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);
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);
344 level = maxLower + 1;
350 contractedNeighbors = 0;
396 std::cout <<
"adding shortcut between " << aInfo.
target->
edge->getID() <<
", " << fInfo.
target->
edge->getID() <<
" via " << edge->getID() <<
"\n";
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";
416 return a->
edge->getNumericalID() > b->
edge->getNumericalID();
425 return &(
myCHInfos[edge->getNumericalID()]);
433 const bool prune = !
mySPTree->validatePermissions();
434 const E*
const edge = info.
edge;
435 if (prune && ((edge->getPermissions() &
mySVC) !=
mySVC)) {
438 const double cost = effortProvider->
getEffort(edge, vehicle, time);
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)) {
451 #ifdef CHRouter_DEBUG_WEIGHTS 452 std::cout << time <<
": " << edge->getID() <<
" cost: " << cost <<
"\n";
460 for (
typename CHConnections::iterator it = connections.begin(); it != connections.end(); it++) {
461 if (it->target == other) {
462 connections.erase(it);
475 #ifdef CHRouter_DEBUG_CONTRACTION_QUEUE 476 std::cout <<
"updating '" << max->
edge->getID() <<
"'\n";
480 pop_heap(queue.begin(), queue.end(),
myCmp);
481 push_heap(queue.begin(), queue.end(),
myCmp);
490 for (
typename std::vector<CHInfo*>::iterator it = queue.begin(); it != queue.end(); it++) {
492 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.
void updateShortcuts(SPTree< CHInfo, CHConnection > *spTree)
compute needed shortcuts when contracting this edge
void endProcessMsg(std::string msg)
Ends a process information.