 |
Eclipse SUMO - Simulation of Urban MObility
|
Go to the documentation of this file.
63 template<
class E,
class V>
91 CHBuilder(
const std::vector<E*>& edges,
bool unbuildIsWarning,
93 bool validatePermissions):
99 for (
typename std::vector<E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
112 const int numEdges = (int)
myCHInfos.size();
113 const std::string vClass = (
mySPTree->validatePermissions() ?
119 std::vector<CHInfo*> queue;
121 for (
int i = 0; i < numEdges; i++) {
128 for (
int i = 0; i < numEdges; i++) {
132 for (
int i = 0; i < numEdges; i++) {
136 std::make_heap(queue.begin(), queue.end(),
myCmp);
137 int contractionRank = 0;
139 while (!queue.empty()) {
141 CHInfo* max = queue.front();
142 max->
rank = contractionRank;
143 #ifdef CHRouter_DEBUG_CONTRACTION
144 std::cout <<
"contracting '" << max->
edge->getID() <<
"' with prio: " << max->
priority <<
" (rank " << contractionRank <<
")\n";
146 const E*
const edge = max->
edge;
148 const int edgeID = edge->getNumericalID();
149 for (
typename CHConnections::const_iterator it = max->
followers.begin(); it != max->
followers.end(); it++) {
156 for (
typename CHConnections::const_iterator it = max->
approaching.begin(); it != max->
approaching.end(); it++) {
163 for (
typename std::vector<Shortcut>::const_iterator it = max->
shortcuts.begin(); it != max->
shortcuts.end(); it++) {
174 std::pop_heap(queue.begin(), queue.end(),
myCmp);
240 traveltime(std::numeric_limits<double>::max()),
253 const double oldPriority =
priority;
263 #ifdef CHRouter_DEBUG_CONTRACTION_DEGREE
265 std::cout <<
"computing shortcuts for '" +
edge->getID() +
"' with degree " +
toString(degree) +
"\n";
273 for (
typename CHConnections::iterator it_f =
followers.begin(); it_f !=
followers.end(); it_f++) {
275 const double viaCost = aInfo.
cost + fInfo.
cost;
279 #ifdef CHRouter_DEBUG_CONTRACTION_WITNESSES
285 viaCost, underlying, viaPermissions));
287 }
else if (validatePermissions) {
292 #ifdef CHRouter_DEBUG_CONTRACTION_WITNESSES
297 #ifdef CHRouter_DEBUG_CONTRACTION_WITNESSES
304 if (validatePermissions) {
306 for (
typename CHConnectionPairs::const_iterator it = pairs.begin(); it != pairs.end(); ++it) {
309 const double viaCost = aInfo->
cost + fInfo->
cost;
314 viaCost, underlying, viaPermissions));
322 int maxLower = std::numeric_limits<int>::min();
325 otherRank = it->target->rank;
326 if (otherRank <
rank) {
330 for (
typename CHConnections::iterator it =
followers.begin(); it !=
followers.end(); it++) {
331 otherRank = it->target->rank;
332 if (otherRank <
rank) {
336 if (maxLower == std::numeric_limits<int>::min()) {
339 level = maxLower + 1;
384 traveltime = std::numeric_limits<double>::max();
391 std::cout <<
"adding shortcut between " << aInfo.
target->
edge->getID() <<
", " << fInfo.
target->
edge->getID() <<
" via " <<
edge->getID() <<
"\n";
395 const double viaCost = aInfo.
cost + fInfo.
cost;
396 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";
411 return a->
edge->getNumericalID() > b->
edge->getNumericalID();
420 return &(
myCHInfos[edge->getNumericalID()]);
428 const bool prune = !
mySPTree->validatePermissions();
429 const E*
const edge = info.
edge;
430 if (prune && ((edge->getPermissions() &
mySVC) !=
mySVC)) {
433 const double baseCost = effortProvider->
getEffort(edge, vehicle, time);
435 for (
const std::pair<const E*, const E*>& successor : edge->getViaSuccessors(
mySVC)) {
436 const E* fEdge = successor.first;
437 if (prune && ((fEdge->getPermissions() &
mySVC) !=
mySVC)) {
441 const SVCPermissions permissions = (edge->getPermissions() & fEdge->getPermissions());
442 double cost = baseCost;
443 const E* viaEdge = successor.second;
444 while (viaEdge !=
nullptr && viaEdge->isInternal()) {
445 cost += effortProvider->
getEffort(viaEdge, vehicle, time);
446 viaEdge = viaEdge->getViaSuccessors().front().first;
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);
474 CHInfo* max = queue.front();
475 #ifdef CHRouter_DEBUG_CONTRACTION_QUEUE
476 std::cout <<
"updating '" << max->
edge->getID() <<
"'\n";
480 std::pop_heap(queue.begin(), queue.end(),
myCmp);
481 std::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 <<
") ";
std::pair< const E *, const E * > ConstEdgePair
SVCPermissions permissions
SVCPermissions permissions
SUMOVehicleClass
Definition of vehicle classes to differ between different lane usage and authority types.
std::vector< Shortcut > shortcuts
The needed shortcuts.
bool tryUpdateFront(std::vector< CHInfo * > &queue)
tries to update the priority of the first edge
std::map< ConstEdgePair, const E * > ShortcutVia
void debugPrintQueue(std::vector< CHInfo * > &queue)
std::vector< CHConnectionPair > CHConnectionPairs
double getEffort(const E *const e, const V *const v, double t) const
int depth
number of edges from start
Forward/backward connection with associated forward/backward cost.
CHBuilder(const std::vector< E * > &edges, bool unbuildIsWarning, const SUMOVehicleClass svc, bool validatePermissions)
Constructor.
const SUMOVehicleClass mySVC
the permissions for which the hierarchy was constructed
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 ...
const std::vector< E * > & myEdges
all edges with numerical ids
StringBijection< SUMOVehicleClass > SumoVehicleClassStrings(sumoVehicleClassStringInitializer, SVC_CUSTOM2, false)
static long getCurrentMillis()
Returns the current time in milliseconds.
std::vector< CHConnection > CHConnections
std::vector< CHInfo > myCHInfos
static vector for lookup
int SVCPermissions
bitset where each bit declares whether a certain SVC may use this edge/lane
std::vector< std::vector< Connection > > backwardUplinks
void debugWitness(const CHConnection &aInfo, const CHConnection &fInfo)
virtual void endProcessMsg(std::string msg)
Ends a process information.
void resetContractionState()
SVCPermissions permissions
the permissions when reaching this edge on the fastest path
std::vector< std::vector< Connection > > forwardUplinks
std::string time2string(SUMOTime t)
double traveltime
Effort to reach the edge.
CHInfo(const E *e)
Constructor.
virtual ~CHBuilder()
Destructor.
const CHConnectionPairs & getNeededShortcuts(const E *excluded)
CHInfoComparator myCmp
Comparator for contraction priority.
Shortcut(ConstEdgePair e, double c, int u, SVCPermissions p)
bool visited
members used in SPTree
CHInfo * getCHInfo(const E *const edge)
const E * edge
The current edge - not const since it may receive shortcut edges.
std::string toString(const T &t, std::streamsize accuracy=gPrecision)
SVCPermissions permissions
bool validatePermissions()
whether permissions should be validated;
int underlying
the number of connections underlying this connection
bool operator()(const CHInfo *a, const CHInfo *b) const
Comparing method.
#define PROGRESS_BEGIN_MESSAGE(msg)
double priority
The contraction priority.
Forward/backward connection with associated FORWARD cost.
CHBuilder & operator=(const CHBuilder &s)
Invalidated assignment operator.
MsgHandler *const myErrorMsgHandler
the handler for routing errors
void debugNoWitness(const CHConnection &aInfo, const CHConnection &fInfo)
debugging methods
const Hierarchy * buildContractionHierarchy(SUMOTime time, const V *const vehicle, const SUMOAbstractRouter< E, V > *effortProvider)
#define PROGRESS_DONE_MESSAGE()
Connection(int t, double c, SVCPermissions p)
void disconnect(CHConnections &connections, CHInfo *other)
remove all connections to/from the given edge (assume it exists only once)
int contractedNeighbors
priority subterms
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)
bool updatePriority(SPTree< CHInfo, CHConnection > *spTree)
recompute the contraction priority and report whether it changed
void registerForValidation(const C *aInfo, const C *fInfo)
save source/target pair for later validation
CHConnections approaching
std::pair< const CHConnection *, const CHConnection * > CHConnectionPair
@ SVC_IGNORING
vehicles ignoring classes
void updateShortcuts(SPTree< CHInfo, CHConnection > *spTree)
compute needed shortcuts when contracting this edge
CHConnection(CHInfo *t, double c, SVCPermissions p, int u)
#define WRITE_MESSAGE(msg)
int myUpdateCount
counters for performance logging
SPTree< CHInfo, CHConnection > * mySPTree
the shortest path tree to use when searching for shortcuts
static MsgHandler * getMessageInstance()
Returns the instance to add normal messages to.
CHConnections followers
connections (only valid after synchronization)