70 template<
class E,
class V>
98 CHBuilder(
const std::vector<E*>& edges,
bool unbuildIsWarning,
100 bool validatePermissions):
106 for (
typename std::vector<E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
119 const int numEdges = (int)
myCHInfos.size();
120 const std::string vClass = (
mySPTree->validatePermissions() ?
126 std::vector<CHInfo*> queue;
128 for (
int i = 0; i < numEdges; i++) {
135 for (
int i = 0; i < numEdges; i++) {
139 for (
int i = 0; i < numEdges; i++) {
143 make_heap(queue.begin(), queue.end(),
myCmp);
144 int contractionRank = 0;
146 while (!queue.empty()) {
148 CHInfo* max = queue.front();
149 max->
rank = contractionRank;
150 #ifdef CHRouter_DEBUG_CONTRACTION 151 std::cout <<
"contracting '" << max->
edge->getID() <<
"' with prio: " << max->
priority <<
" (rank " << contractionRank <<
")\n";
153 const E*
const edge = max->
edge;
155 const int edgeID = edge->getNumericalID();
156 for (
typename CHConnections::const_iterator it = max->
followers.begin(); it != max->
followers.end(); it++) {
163 for (
typename CHConnections::const_iterator it = max->
approaching.begin(); it != max->
approaching.end(); it++) {
170 for (
typename std::vector<Shortcut>::const_iterator it = max->
shortcuts.begin(); it != max->
shortcuts.end(); it++) {
171 const ConstEdgePair& edgePair = it->edgePair;
181 pop_heap(queue.begin(), queue.end(),
myCmp);
241 contractedNeighbors(0),
246 traveltime(std::numeric_limits<double>::max()) {
252 updateShortcuts(spTree);
255 contractedNeighbors += 1;
257 const double oldPriority = priority;
259 const int edge_difference = (int)followers.size() + (int)approaching.size() - 2 * (int)shortcuts.size();
260 priority = (double)(2 * edge_difference - contractedNeighbors - underlyingTotal - 5 * level);
261 return priority != oldPriority;
267 #ifdef CHRouter_DEBUG_CONTRACTION_DEGREE 268 const int degree = (int)approaching.size() + (int)followers.size();
269 std::cout <<
"computing shortcuts for '" + edge->getID() +
"' with degree " +
toString(degree) +
"\n";
273 for (
typename CHConnections::iterator it_a = approaching.begin(); it_a != approaching.end(); it_a++) {
277 for (
typename CHConnections::iterator it_f = followers.begin(); it_f != followers.end(); it_f++) {
279 const double viaCost = aInfo.
cost + fInfo.
cost;
283 #ifdef CHRouter_DEBUG_CONTRACTION_WITNESSES 284 debugNoWitness(aInfo, fInfo);
287 underlyingTotal += underlying;
289 viaCost, underlying, viaPermissions));
291 }
else if (validatePermissions) {
296 #ifdef CHRouter_DEBUG_CONTRACTION_WITNESSES 297 debugNoWitness(aInfo, fInfo);
301 #ifdef CHRouter_DEBUG_CONTRACTION_WITNESSES 302 debugNoWitness(aInfo, fInfo);
308 if (validatePermissions) {
310 for (
typename CHConnectionPairs::const_iterator it = pairs.begin(); it != pairs.end(); ++it) {
313 const double viaCost = aInfo->
cost + fInfo->
cost;
316 underlyingTotal += underlying;
318 viaCost, underlying, viaPermissions));
326 int maxLower = std::numeric_limits<int>::min();
328 for (
typename CHConnections::iterator it = approaching.begin(); it != approaching.end(); it++) {
329 otherRank = it->target->rank;
330 if (otherRank < rank) {
331 maxLower =
MAX2(rank, maxLower);
334 for (
typename CHConnections::iterator it = followers.begin(); it != followers.end(); it++) {
335 otherRank = it->target->rank;
336 if (otherRank < rank) {
337 maxLower =
MAX2(rank, maxLower);
340 if (maxLower == std::numeric_limits<int>::min()) {
343 level = maxLower + 1;
349 contractedNeighbors = 0;
388 traveltime = std::numeric_limits<double>::max();
395 std::cout <<
"adding shortcut between " << aInfo.
target->
edge->getID() <<
", " << fInfo.
target->
edge->getID() <<
" via " << edge->getID() <<
"\n";
399 const double viaCost = aInfo.
cost + fInfo.
cost;
400 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";
415 return a->
edge->getNumericalID() > b->
edge->getNumericalID();
424 return &(
myCHInfos[edge->getNumericalID()]);
432 const bool prune = !
mySPTree->validatePermissions();
433 const E*
const edge = info.
edge;
434 if (prune && ((edge->getPermissions() &
mySVC) !=
mySVC)) {
437 const double cost = effortProvider->
getEffort(edge, vehicle, time);
439 const std::vector<E*>& successors = edge->getSuccessors(
mySVC);
440 for (
typename std::vector<E*>::const_iterator it = successors.begin(); it != successors.end(); ++it) {
441 const E* fEdge = *it;
442 if (prune && ((fEdge->getPermissions() &
mySVC) !=
mySVC)) {
450 #ifdef CHRouter_DEBUG_WEIGHTS 451 std::cout << time <<
": " << edge->getID() <<
" cost: " << cost <<
"\n";
459 for (
typename CHConnections::iterator it = connections.begin(); it != connections.end(); it++) {
460 if (it->target == other) {
461 connections.erase(it);
473 CHInfo* max = queue.front();
474 #ifdef CHRouter_DEBUG_CONTRACTION_QUEUE 475 std::cout <<
"updating '" << max->
edge->getID() <<
"'\n";
479 pop_heap(queue.begin(), queue.end(),
myCmp);
480 push_heap(queue.begin(), queue.end(),
myCmp);
489 for (
typename std::vector<CHInfo*>::iterator it = queue.begin(); it != queue.end(); it++) {
491 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.