73 template<
class E,
class V,
class PF>
83 typedef std::pair<const EdgeInfo*, const EdgeInfo*>
Meeting;
89 typedef std::vector<const E*>
Result;
111 edge(E::dictionary(id)),
152 for (
size_t i = 0; i < numEdges; 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):
334 for (
size_t i = 0; i < numEdges; i++) {
354 virtual void compute(
const E* from,
const E* to,
const V*
const vehicle,
356 assert(from != 0 && to != 0);
370 Meeting meeting(static_cast<EdgeInfo*>(0), static_cast<EdgeInfo*>(0));
371 bool continueForward =
true;
372 bool continueBackward =
true;
373 int num_visited_fw = 0;
374 int num_visited_bw = 0;
375 while (continueForward || continueBackward) {
376 if (continueForward) {
380 if (continueBackward) {
390 #ifdef CHRouter_DEBUG_QUERY_PERF
391 std::cout <<
"visited " << num_visited_fw + num_visited_bw <<
" edges (" << num_visited_fw <<
"," << num_visited_bw <<
") ,final path length: " +
toString(into.size()) +
")\n";
393 this->
endQuery(num_visited_bw + num_visited_fw);
400 for (
typename std::vector<const E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
401 if (PF::operator()(*i, v)) {
404 costs += this->
getEffort(*i, v, time + costs);
413 std::deque<const E*> tmp;
414 const EdgeInfo* backtrack = meeting.first;
415 while (backtrack != 0) {
416 tmp.push_front((E*) backtrack->
edge);
417 backtrack = backtrack->
prev;
419 backtrack = meeting.second->
prev;
420 while (backtrack != 0) {
421 tmp.push_back((E*) backtrack->
edge);
422 backtrack = backtrack->
prev;
426 while (!tmp.empty()) {
427 const E* cur = tmp.front();
433 const E* via =
getVia(prev, cur);
468 edge(E::dictionary(id)),
495 #ifdef CHRouter_DEBUG_CONTRACTION_DEGREE
497 std::cout <<
"computing shortcuts for '" +
edge->getID() +
"' with degree " +
toString(degree) +
"\n";
505 for (
typename CHConnections::iterator it_f =
followers.begin(); it_f !=
followers.end(); it_f++) {
511 #ifdef CHRouter_DEBUG_CONTRACTION_WITNESSES
517 viaCost, underlying, viaPermissions));
519 }
else if (validatePermissions) {
524 #ifdef CHRouter_DEBUG_CONTRACTION_WITNESSES
529 #ifdef CHRouter_DEBUG_CONTRACTION_WITNESSES
536 if (validatePermissions) {
538 for (
typename CHConnectionPairs::const_iterator it = pairs.begin(); it != pairs.end(); ++it) {
546 viaCost, underlying, viaPermissions));
557 otherRank = it->target->rank;
558 if (otherRank <
rank) {
562 for (
typename CHConnections::iterator it =
followers.begin(); it !=
followers.end(); it++) {
563 otherRank = it->target->rank;
564 if (otherRank <
rank) {
571 level = maxLower + 1;
623 std::cout <<
"adding shortcut between " << aInfo.
target->
edge->getID() <<
", " << fInfo.
target->
edge->getID() <<
" via " << edge->getID() <<
"\n";
628 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";
644 return a->
edge->getNumericalID() > b->
edge->getNumericalID();
653 return &(
myCHInfos[edge->getNumericalID()]);
661 const bool prune = !
mySPTree->validatePermissions();
662 const E*
const edge = info.
edge;
663 if (prune && ((edge->getPermissions() &
mySVC) !=
mySVC)) {
668 const std::vector<E*>& successors = edge->getSuccessors(
mySVC);
669 for (
typename std::vector<E*>::const_iterator it = successors.begin(); it != successors.end(); ++it) {
670 const E* fEdge = *it;
671 if (prune && ((fEdge->getPermissions() &
mySVC) !=
mySVC)) {
675 SVCPermissions permissions = (edge->getPermissions() & follower->
edge->getPermissions());
679 #ifdef CHRouter_DEBUG_WEIGHTS
680 std::cout << time <<
": " << edge->getID() <<
" cost: " << cost <<
"\n";
688 for (
typename CHConnections::iterator it = connections.begin(); it != connections.end(); it++) {
689 if (it->target == other) {
690 connections.erase(it);
699 const size_t numEdges =
myCHInfos.size();
700 const std::string vClass = (
mySPTree->validatePermissions() ?
706 std::vector<CHInfo*> queue;
711 for (
size_t i = 0; i < numEdges; i++) {
716 for (
size_t i = 0; i < numEdges; i++) {
720 for (
size_t i = 0; i < numEdges; i++) {
724 make_heap(queue.begin(), queue.end(),
myCmp);
725 int contractionRank = 0;
727 while (!queue.empty()) {
730 max->
rank = contractionRank;
731 #ifdef CHRouter_DEBUG_CONTRACTION
732 std::cout <<
"contracting '" << max->
edge->getID() <<
"' with prio: " << max->
priority <<
" (rank " << contractionRank <<
")\n";
737 edgeInfoFW->
rank = contractionRank;
738 for (
typename CHConnections::iterator it = max->
followers.begin(); it != max->
followers.end(); it++) {
747 edgeInfoBW->
rank = contractionRank;
748 for (
typename CHConnections::iterator it = max->
approaching.begin(); it != max->
approaching.end(); it++) {
756 for (
typename Shortcuts::iterator it = max->
shortcuts.begin(); it != max->
shortcuts.end(); it++) {
757 EdgePair& edgePair = it->edgePair;
765 pop_heap(queue.begin(), queue.end(),
myCmp);
794 const E*
getVia(
const E* forwardFrom,
const E* forwardTo) {
795 ConstEdgePair forward(forwardFrom, forwardTo);
796 typename ShortcutVia::iterator it =
myShortcuts.find(forward);
811 #ifdef CHRouter_DEBUG_CONTRACTION_QUEUE
812 std::cout <<
"updating '" << max->
edge->getID() <<
"'\n";
816 pop_heap(queue.begin(), queue.end(),
myCmp);
817 push_heap(queue.begin(), queue.end(),
myCmp);
826 for (
typename std::vector<CHInfo*>::iterator it = queue.begin(); it != queue.end(); it++) {
828 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.
virtual void 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...
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
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.
std::vector< EdgeInfo > myEdgeInfos
The container of edge information.
CHInfo(size_t id)
Constructor.
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.
EdgeInfo(size_t id)
Constructor.
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)
Unidirectional(size_t numEdges, bool forward)
Constructor.
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
CHRouter(size_t numEdges, bool unbuildIsWarning, Operation operation, const SUMOVehicleClass svc, SUMOTime weightPeriod, bool validatePermissions)
Constructor.
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
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
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)
const E * edge
The current edge.
vehicles ignoring classes
virtual SUMOAbstractRouter< E, V > * clone() const
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.