73 template<
class E,
class V,
class PF>
83 typedef std::pair<const EdgeInfo*, const EdgeInfo*>
Meeting;
89 typedef std::vector<const E*>
Result;
152 for (
typename std::vector<E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
157 inline bool found(
const E* edge)
const {
158 return myFound.count(edge) > 0;
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++) {
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;
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;
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);
499 #ifdef CHRouter_DEBUG_CONTRACTION_DEGREE
501 std::cout <<
"computing shortcuts for '" +
edge->getID() +
"' with degree " +
toString(degree) +
"\n";
509 for (
typename CHConnections::iterator it_f =
followers.begin(); it_f !=
followers.end(); it_f++) {
515 #ifdef CHRouter_DEBUG_CONTRACTION_WITNESSES
521 viaCost, underlying, viaPermissions));
523 }
else if (validatePermissions) {
528 #ifdef CHRouter_DEBUG_CONTRACTION_WITNESSES
533 #ifdef CHRouter_DEBUG_CONTRACTION_WITNESSES
540 if (validatePermissions) {
542 for (
typename CHConnectionPairs::const_iterator it = pairs.begin(); it != pairs.end(); ++it) {
550 viaCost, underlying, viaPermissions));
561 otherRank = it->target->rank;
562 if (otherRank <
rank) {
566 for (
typename CHConnections::iterator it =
followers.begin(); it !=
followers.end(); it++) {
567 otherRank = it->target->rank;
568 if (otherRank <
rank) {
575 level = maxLower + 1;
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)) {
679 SVCPermissions permissions = (edge->getPermissions() & follower->
edge->getPermissions());
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
const EdgeInfo * getEdgeInfo(const E *const edge) const
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 tryUpdateFront(std::vector< CHInfo * > &queue)
tries to update the priority of the first edge
bool visited
Whether the shortest path to this edge is already found.
CHInfo * getCHInfo(const E *const edge)
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
bool operator()(const CHInfo *a, const CHInfo *b) const
Comparing method.
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.
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
SUMOTime myValidUntil
the validity duration of the current hierarchy (exclusive)
Forward/backward connection with associated FORWARD cost.
CHRouter(const std::vector< E * > &edges, bool unbuildIsWarning, Operation operation, const SUMOVehicleClass svc, SUMOTime weightPeriod, bool validatePermissions)
Constructor.
std::vector< EdgeInfo > myEdgeInfos
The container of edge information.
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 operator()(const EdgeInfo *nod1, const EdgeInfo *nod2) const
Comparing method.
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
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(* Operation)(const E *const, const V *const, SUMOReal)
Type of the function that is used to retrieve the edge effort.
std::string toString(const T &t, std::streamsize accuracy=OUTPUT_ACCURACY)
SVCPermissions permissions
SUMOVehicleClass mySVC
the permissions for which the hierarchy was constructed
bool visited
members used in SPTree
Shortcuts shortcuts
The needed shortcuts.
SUMOReal recomputeCosts(const std::vector< const E * > &edges, const V *const v, SUMOTime msTime) const
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
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
Unidirectional(const std::vector< E * > &edges, bool forward)
Constructor.
bool myAmForward
the role of this search
void endQuery(int visits)
bool found(const E *edge) const
bool validatePermissions()
whether permissions should be validated;
static long getCurrentMillis()
Returns the current time in milliseconds.
#define PROGRESS_DONE_MESSAGE()
void debugPrintQueue(std::vector< CHInfo * > &queue)
std::pair< const CHConnection *, const CHConnection * > CHConnectionPair
#define WRITE_MESSAGE(msg)
SUMOReal getEffort(const E *const e, const V *const v, SUMOReal t) const
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.