73 template<
class E,
class V,
class PF>
83 typedef std::pair<const EdgeInfo*, const EdgeInfo*>
Meeting;
89 typedef std::vector<const E*>
Result;
150 myAmForward(forward),
152 for (
typename std::vector<E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
153 myEdgeInfos.push_back(
EdgeInfo(*i));
157 inline bool found(
const E* edge)
const {
158 return myFound.count(edge) > 0;
162 return &(myEdgeInfos[edge->getNumericalID()]);
166 return &(myEdgeInfos[edge->getNumericalID()]);
178 return nod1->
edge->getNumericalID() > nod2->
edge->getNumericalID();
185 void init(
const E*
const start,
const V*
const vehicle) {
186 assert(vehicle != 0);
188 for (
typename std::vector<EdgeInfo*>::iterator i = myFrontier.begin(); i != myFrontier.end(); i++) {
192 for (
typename EdgeSet::iterator i = myFound.begin(); i != myFound.end(); i++) {
193 getEdgeInfo(*i)->reset();
197 EdgeInfo* startInfo = getEdgeInfo(start);
200 myFrontier.push_back(startInfo);
210 EdgeInfo*
const minimumInfo = myFrontier.front();
211 pop_heap(myFrontier.begin(), myFrontier.end(), myComparator);
212 myFrontier.pop_back();
214 const E*
const minEdge = minimumInfo->
edge;
215 #ifdef CHRouter_DEBUG_QUERY 216 std::cout <<
"DEBUG: " << (myAmForward ?
"Forward" :
"Backward") <<
" hit '" << minEdge->getID() <<
"' Q: ";
217 for (
typename std::vector<EdgeInfo*>::iterator it = myFrontier.begin(); it != myFrontier.end(); it++) {
218 std::cout << (*it)->traveltime <<
"," << (*it)->edge->getID() <<
" ";
222 if (otherSearch.
found(minEdge)) {
225 #ifdef CHRouter_DEBUG_QUERY 226 std::cout <<
"DEBUG: " << (myAmForward ?
"Forward" :
"Backward") <<
"-Search hit other search at '" << minEdge->getID() <<
"', tt: " << ttSeen <<
" \n";
228 if (ttSeen < minTTSeen) {
231 meeting.first = minimumInfo;
232 meeting.second = otherInfo;
234 meeting.first = otherInfo;
235 meeting.second = minimumInfo;
242 myFound.insert(minimumInfo->
edge);
243 for (
typename std::vector<Connection>::iterator it = minimumInfo->
upward.begin(); it != minimumInfo->
upward.end(); it++) {
248 if ((it->permissions & svc) != svc) {
252 if (!upwardInfo->
visited && traveltime < oldTraveltime) {
254 upwardInfo->
prev = minimumInfo;
256 myFrontier.push_back(upwardInfo);
257 push_heap(myFrontier.begin(), myFrontier.end(), myComparator);
259 push_heap(myFrontier.begin(),
260 find(myFrontier.begin(), myFrontier.end(), upwardInfo) + 1,
270 return !myFrontier.empty() && myFrontier.front()->traveltime < minTTSeen;
276 for (
typename std::vector<EdgeInfo>::iterator it = myEdgeInfos.begin(); it != myEdgeInfos.end(); ++it) {
324 bool validatePermissions):
335 for (
typename std::vector<E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
355 virtual bool compute(
const E* from,
const E* to,
const V*
const vehicle,
357 assert(from != 0 && to != 0);
371 Meeting meeting(static_cast<EdgeInfo*>(0), static_cast<EdgeInfo*>(0));
372 bool continueForward =
true;
373 bool continueBackward =
true;
374 int num_visited_fw = 0;
375 int num_visited_bw = 0;
377 while (continueForward || continueBackward) {
378 if (continueForward) {
382 if (continueBackward) {
390 myErrorMsgHandler->
inform(
"No connection between edge '" + from->getID() +
"' and edge '" + to->getID() +
"' found.");
393 #ifdef CHRouter_DEBUG_QUERY_PERF 394 std::cout <<
"visited " << num_visited_fw + num_visited_bw <<
" edges (" << num_visited_fw <<
"," << num_visited_bw <<
") ,final path length: " +
toString(into.size()) +
")\n";
396 this->
endQuery(num_visited_bw + num_visited_fw);
404 for (
typename std::vector<const E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
405 if (PF::operator()(*i, v)) {
408 costs += this->
getEffort(*i, v, time + costs);
417 std::deque<const E*> tmp;
418 const EdgeInfo* backtrack = meeting.first;
419 while (backtrack != 0) {
420 tmp.push_front((E*) backtrack->
edge);
421 backtrack = backtrack->
prev;
423 backtrack = meeting.second->
prev;
424 while (backtrack != 0) {
425 tmp.push_back((E*) backtrack->
edge);
426 backtrack = backtrack->
prev;
430 while (!tmp.empty()) {
431 const E* cur = tmp.front();
437 const E* via =
getVia(prev, cur);
473 contractedNeighbors(0),
484 updateShortcuts(spTree);
487 contractedNeighbors += 1;
489 const SUMOReal oldPriority = priority;
491 const int edge_difference = (int)followers.size() + (int)approaching.size() - 2 * (int)shortcuts.size();
492 priority = (
SUMOReal)(2 * edge_difference - contractedNeighbors - underlyingTotal - 5 * level);
493 return priority != oldPriority;
499 #ifdef CHRouter_DEBUG_CONTRACTION_DEGREE 500 const int degree = approaching.size() + followers.size();
501 std::cout <<
"computing shortcuts for '" + edge->getID() +
"' with degree " +
toString(degree) +
"\n";
505 for (
typename CHConnections::iterator it_a = approaching.begin(); it_a != approaching.end(); it_a++) {
509 for (
typename CHConnections::iterator it_f = followers.begin(); it_f != followers.end(); it_f++) {
515 #ifdef CHRouter_DEBUG_CONTRACTION_WITNESSES 516 debugNoWitness(aInfo, fInfo);
519 underlyingTotal += underlying;
521 viaCost, underlying, viaPermissions));
523 }
else if (validatePermissions) {
528 #ifdef CHRouter_DEBUG_CONTRACTION_WITNESSES 529 debugNoWitness(aInfo, fInfo);
533 #ifdef CHRouter_DEBUG_CONTRACTION_WITNESSES 534 debugNoWitness(aInfo, fInfo);
540 if (validatePermissions) {
542 for (
typename CHConnectionPairs::const_iterator it = pairs.begin(); it != pairs.end(); ++it) {
548 underlyingTotal += underlying;
550 viaCost, underlying, viaPermissions));
560 for (
typename CHConnections::iterator it = approaching.begin(); it != approaching.end(); it++) {
561 otherRank = it->target->rank;
562 if (otherRank < rank) {
563 maxLower =
MAX2(rank, maxLower);
566 for (
typename CHConnections::iterator it = followers.begin(); it != followers.end(); it++) {
567 otherRank = it->target->rank;
568 if (otherRank < rank) {
569 maxLower =
MAX2(rank, maxLower);
575 level = maxLower + 1;
581 contractedNeighbors = 0;
627 std::cout <<
"adding shortcut between " << aInfo.
target->
edge->getID() <<
", " << fInfo.
target->
edge->getID() <<
" via " << edge->getID() <<
"\n";
632 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";
648 return a->
edge->getNumericalID() > b->
edge->getNumericalID();
657 return &(
myCHInfos[edge->getNumericalID()]);
665 const bool prune = !
mySPTree->validatePermissions();
666 const E*
const edge = info.
edge;
667 if (prune && ((edge->getPermissions() &
mySVC) !=
mySVC)) {
672 const std::vector<E*>& successors = edge->getSuccessors(
mySVC);
673 for (
typename std::vector<E*>::const_iterator it = successors.begin(); it != successors.end(); ++it) {
674 const E* fEdge = *it;
675 if (prune && ((fEdge->getPermissions() &
mySVC) !=
mySVC)) {
683 #ifdef CHRouter_DEBUG_WEIGHTS 684 std::cout << time <<
": " << edge->getID() <<
" cost: " << cost <<
"\n";
692 for (
typename CHConnections::iterator it = connections.begin(); it != connections.end(); it++) {
693 if (it->target == other) {
694 connections.erase(it);
703 const int numEdges = (int)
myCHInfos.size();
704 const std::string vClass = (
mySPTree->validatePermissions() ?
710 std::vector<CHInfo*> queue;
715 for (
int i = 0; i < numEdges; i++) {
720 for (
int i = 0; i < numEdges; i++) {
724 for (
int i = 0; i < numEdges; i++) {
728 make_heap(queue.begin(), queue.end(),
myCmp);
729 int contractionRank = 0;
731 while (!queue.empty()) {
734 max->
rank = contractionRank;
735 #ifdef CHRouter_DEBUG_CONTRACTION 736 std::cout <<
"contracting '" << max->
edge->getID() <<
"' with prio: " << max->
priority <<
" (rank " << contractionRank <<
")\n";
741 edgeInfoFW->
rank = contractionRank;
742 for (
typename CHConnections::iterator it = max->
followers.begin(); it != max->
followers.end(); it++) {
751 edgeInfoBW->
rank = contractionRank;
752 for (
typename CHConnections::iterator it = max->
approaching.begin(); it != max->
approaching.end(); it++) {
760 for (
typename Shortcuts::iterator it = max->
shortcuts.begin(); it != max->
shortcuts.end(); it++) {
761 EdgePair& edgePair = it->edgePair;
769 pop_heap(queue.begin(), queue.end(),
myCmp);
798 const E*
getVia(
const E* forwardFrom,
const E* forwardTo) {
799 ConstEdgePair forward(forwardFrom, forwardTo);
800 typename ShortcutVia::iterator it =
myShortcuts.find(forward);
815 #ifdef CHRouter_DEBUG_CONTRACTION_QUEUE 816 std::cout <<
"updating '" << max->
edge->getID() <<
"'\n";
820 pop_heap(queue.begin(), queue.end(),
myCmp);
821 push_heap(queue.begin(), queue.end(),
myCmp);
830 for (
typename std::vector<CHInfo*>::iterator it = queue.begin(); it != queue.end(); it++) {
832 std::cout <<
"(" << chInfo->
edge->getID() <<
"," << chInfo->
priority <<
") ";
Computes the shortest path through a contracted network.
void debugWitness(const CHConnection &aInfo, const CHConnection &fInfo)
EdgeSet myFound
the set of visited (settled) Edges
static MsgHandler * getWarningInstance()
Returns the instance to add warnings to.
CHInfoComparator myCmp
Comparator for contraction priority.
std::pair< E *, E * > EdgePair
std::pair< const E *, const E * > ConstEdgePair
contraction related members
int myUpdateCount
counters for performance logging
SPTree< CHInfo, CHConnection > * mySPTree
the shortest path tree to use when searching for shortcuts
int depth
number of edges from start
const SUMOTime myWeightPeriod
the validity duration of one weight interval
EdgeInfo * getEdgeInfo(const E *const edge)
CHConnections followers
connections (only valid after synchronization)
bool step(const Unidirectional &otherSearch, SUMOReal &minTTSeen, Meeting &meeting)
explore on element from the frontier,update minTTSeen and meeting if an EdgeInfo found by the otherSe...
const E * getVia(const E *forwardFrom, const E *forwardTo)
SUMOVehicleClass
Definition of vehicle classes to differ between different lane usage and authority types...
virtual ~CHRouter()
Destructor.
std::set< const E * > EdgeSet
A set of (found) Edges.
Unidirectional myForwardSearch
the unidirectional search queues
void buildPathFromMeeting(Meeting meeting, Result &into)
normal routing methods
SUMOReal traveltime
Effort to reach the edge.
void resetContractionState()
std::string time2string(SUMOTime t)
void synchronize(CHInfo &info, SUMOReal time, const V *const vehicle)
copy connections from the original net (modified destructively during contraction) ...
std::vector< EdgeInfo * > myFrontier
the min edge heap
SVCPermissions permissions
bool visited
Whether the shortest path to this edge is already found.
CHInfo * getCHInfo(const E *const edge)
bool operator()(const EdgeInfo *nod1, const EdgeInfo *nod2) const
Comparing method.
ShortcutVia myShortcuts
map from (forward) shortcut to via-Edge
void updateShortcuts(SPTree< CHInfo, CHConnection > *spTree)
compute needed shortcuts when contracting this edge
std::vector< const E * > Result
The found route (used as output parameter)
int contractedNeighbors
priority subterms
EdgeInfoByTTComparator myComparator
SUMOReal priority
The contraction priority.
int rank
the contraction rank (higher means more important)
Shortcut(EdgePair e, SUMOReal c, int u, SVCPermissions p)
E * edge
The current edge - not const since it may receive shortcut edges.
CHRouter(const std::vector< E *> &edges, bool unbuildIsWarning, Operation operation, const SUMOVehicleClass svc, SUMOTime weightPeriod, bool validatePermissions)
Constructor.
Unidirectional myBackwardSearch
SVCPermissions permissions
std::map< ConstEdgePair, const E * > ShortcutVia
virtual SUMOAbstractRouter< E, V > * clone()
void registerForValidation(const C *aInfo, const C *fInfo)
save source/target pair for later validation
std::vector< Shortcut > Shortcuts
std::vector< CHConnectionPair > CHConnectionPairs
std::vector< CHInfo > myCHInfos
static vector for lookup
bool operator()(const CHInfo *a, const CHInfo *b) const
Comparing method.
SUMOTime myValidUntil
the validity duration of the current hierarchy (exclusive)
Forward/backward connection with associated FORWARD cost.
std::vector< EdgeInfo > myEdgeInfos
The container of edge information.
Unidirectional(const std::vector< E *> &edges, bool forward)
Constructor.
virtual bool compute(const E *from, const E *to, const V *const vehicle, SUMOTime msTime, Result &into)
Builds the route between the given edges using the minimum traveltime in the contracted graph...
const CHConnectionPairs & getNeededShortcuts(const E *excluded)
void init(const E *const start, const V *const vehicle)
bool tryUpdateFront(std::vector< CHInfo *> &queue)
tries to update the priority of the first edge
SUMOReal traveltime
Effort to reach the edge.
std::vector< CHConnection > CHConnections
#define PROGRESS_BEGIN_MESSAGE(msg)
static MsgHandler * getMessageInstance()
Returns the instance to add normal messages to.
bool updatePriority(SPTree< CHInfo, CHConnection > *spTree)
recompute the contraction priority and report whether it changed
bool found(const E *edge) const
SUMOReal(* Operation)(const E *const, const V *const, SUMOReal)
Type of the function that is used to retrieve the edge effort.
void debugNoWitness(const CHConnection &aInfo, const CHConnection &fInfo)
debugging methods
std::pair< const EdgeInfo *, const EdgeInfo * > Meeting
A meeting point of the two search scopes.
StringBijection< SUMOVehicleClass > SumoVehicleClassStrings(sumoVehicleClassStringInitializer, SVC_CUSTOM2, false)
Operation myOperation
The object's operation to perform.
CHConnection(CHInfo *t, SUMOReal c, SVCPermissions p, int u)
SUMOReal getEffort(const E *const e, const V *const v, SUMOReal t) const
std::string toString(const T &t, std::streamsize accuracy=OUTPUT_ACCURACY)
SVCPermissions permissions
SUMOVehicleClass mySVC
the permissions for which the hierarchy was constructed
SUMOReal recomputeCosts(const std::vector< const E *> &edges, const V *const v, SUMOTime msTime) const
bool visited
members used in SPTree
Shortcuts shortcuts
The needed shortcuts.
const std::vector< E * > & myEdges
all edges with numerical ids
MsgHandler *const myErrorMsgHandler
the handler for routing errors
Forward/backward connection with associated forward/backward cost.
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 ...
CHConnections approaching
void inform(std::string msg, bool addType=true)
adds a new error to the list
const EdgeInfo * getEdgeInfo(const E *const edge) const
int underlying
the number of connections underlying this connection
void disconnect(CHConnections &connections, CHInfo *other)
remove all connections to/from the given edge (assume it exists only once)
SVCPermissions permissions
the permissions when reaching this edge on the fastest path
bool myAmForward
the role of this search
void endQuery(int visits)
void debugPrintQueue(std::vector< CHInfo *> &queue)
bool validatePermissions()
whether permissions should be validated;
static long getCurrentMillis()
Returns the current time in milliseconds.
#define PROGRESS_DONE_MESSAGE()
std::pair< const CHConnection *, const CHConnection * > CHConnectionPair
#define WRITE_MESSAGE(msg)
Connection(EdgeInfo *t, SUMOReal c, SVCPermissions p)
EdgeInfo(const E *e)
Constructor.
const E * edge
The current edge.
vehicles ignoring classes
void buildContractionHierarchy(SUMOTime time, const V *const vehicle)
std::vector< Connection > upward
Connections to higher ranked nodes.
EdgeInfo * prev
The previous edge.
void endProcessMsg(std::string msg)
Ends a process information.