 |
Eclipse SUMO - Simulation of Urban MObility
|
Go to the documentation of this file.
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 std::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++) {
175 std::pop_heap(queue.begin(), queue.end(),
myCmp);
241 traveltime(std::numeric_limits<double>::max()),
254 const double oldPriority =
priority;
264 #ifdef CHRouter_DEBUG_CONTRACTION_DEGREE
266 std::cout <<
"computing shortcuts for '" +
edge->getID() +
"' with degree " +
toString(degree) +
"\n";
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
286 viaCost, underlying, viaPermissions));
288 }
else if (validatePermissions) {
293 #ifdef CHRouter_DEBUG_CONTRACTION_WITNESSES
298 #ifdef CHRouter_DEBUG_CONTRACTION_WITNESSES
305 if (validatePermissions) {
307 for (
typename CHConnectionPairs::const_iterator it = pairs.begin(); it != pairs.end(); ++it) {
310 const double viaCost = aInfo->
cost + fInfo->
cost;
315 viaCost, underlying, viaPermissions));
323 int maxLower = std::numeric_limits<int>::min();
326 otherRank = it->target->rank;
327 if (otherRank <
rank) {
331 for (
typename CHConnections::iterator it =
followers.begin(); it !=
followers.end(); it++) {
332 otherRank = it->target->rank;
333 if (otherRank <
rank) {
337 if (maxLower == std::numeric_limits<int>::min()) {
340 level = maxLower + 1;
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)) {
442 const SVCPermissions permissions = (edge->getPermissions() & fEdge->getPermissions());
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 std::pop_heap(queue.begin(), queue.end(),
myCmp);
482 std::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 <<
") ";
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
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)