58 template<
class E,
class V>
75 for (
const E*
const e : edges) {
80 inline bool found(
const E*
const edge)
const {
101 return nod1->
edge->getNumericalID() > nod2->
edge->getNumericalID();
108 void init(
const E*
const start,
const V*
const vehicle) {
109 assert(vehicle != 0);
121 startInfo->effort = 0.;
122 startInfo->prev =
nullptr;
138 const E*
const minEdge = minimumInfo->edge;
139 #ifdef CHRouter_DEBUG_QUERY
140 std::cout <<
"DEBUG: " << (
myAmForward ?
"Forward" :
"Backward") <<
" hit '" << minEdge->getID() <<
"' Q: ";
141 for (
typename std::vector<EdgeInfo*>::iterator it =
myFrontier.begin(); it !=
myFrontier.end(); it++) {
142 std::cout << (*it)->traveltime <<
"," << (*it)->edge->getID() <<
" ";
146 if (otherSearch.
found(minEdge)) {
147 const auto*
const otherInfo = otherSearch.
getEdgeInfo(minEdge);
148 const double ttSeen = minimumInfo->
effort + otherInfo->effort;
149 #ifdef CHRouter_DEBUG_QUERY
150 std::cout <<
"DEBUG: " << (
myAmForward ?
"Forward" :
"Backward") <<
"-Search hit other search at '" << minEdge->getID() <<
"', tt: " << ttSeen <<
" \n";
152 if (ttSeen < minTTSeen) {
155 meeting.first = minimumInfo;
156 meeting.second = otherInfo;
158 meeting.first = otherInfo;
159 meeting.second = minimumInfo;
164 minimumInfo->visited =
true;
166 myFound.insert(minimumInfo->edge);
167 for (
const auto& uplink : uplinks[minEdge->getNumericalID()]) {
168 const auto upwardInfo = &
myEdgeInfos[uplink.target];
169 const double effort = minimumInfo->effort + uplink.cost;
172 if ((uplink.permissions & svc) != svc) {
175 const double oldEffort = upwardInfo->effort;
176 if (!upwardInfo->visited && effort < oldEffort) {
177 upwardInfo->effort = effort;
178 upwardInfo->prev = minimumInfo;
179 if (oldEffort == std::numeric_limits<double>::max()) {
201 std::vector<typename SUMOAbstractRouter<E, V>::EdgeInfo*>
myFrontier;
205 std::vector<typename SUMOAbstractRouter<E, V>::EdgeInfo>
myEdgeInfos;
221 const bool havePermissions,
const bool haveRestrictions):
222 SUMOAbstractRouter<E, V>(
"CHRouter", unbuildIsWarning, operation, nullptr, havePermissions, haveRestrictions),
238 const bool havePermissions,
const bool haveRestrictions) :
239 SUMOAbstractRouter<E, V>(
"CHRouterClone", unbuildIsWarning, operation, nullptr, havePermissions, haveRestrictions),
270 virtual void reset(
const V*
const vehicle) {
287 virtual bool compute(
const E* from,
const E* to,
const V*
const vehicle,
288 SUMOTime msTime, std::vector<const E*>& into,
bool silent =
false) {
289 assert(from !=
nullptr && to !=
nullptr);
297 this->
reset(vehicle);
303 double minTTSeen = std::numeric_limits<double>::max();
304 Meeting meeting(
nullptr,
nullptr);
305 bool continueForward =
true;
306 bool continueBackward =
true;
307 int num_visited_fw = 0;
308 int num_visited_bw = 0;
310 while (continueForward || continueBackward) {
311 if (continueForward) {
315 if (continueBackward) {
320 if (minTTSeen < std::numeric_limits<double>::max()) {
328 #ifdef CHRouter_DEBUG_QUERY_PERF
329 std::cout <<
"visited " << num_visited_fw + num_visited_bw <<
" edges (" << num_visited_fw <<
"," << num_visited_bw <<
") ,final path length: " +
toString(into.size()) +
")\n";
331 this->
endQuery(num_visited_bw + num_visited_fw);
339 std::deque<const E*> tmp;
340 const auto* backtrack = meeting.first;
341 while (backtrack != 0) {
342 tmp.push_front((E*) backtrack->edge);
343 backtrack = backtrack->prev;
345 backtrack = meeting.second->prev;
346 while (backtrack != 0) {
347 tmp.push_back((E*) backtrack->edge);
348 backtrack = backtrack->prev;
352 while (!tmp.empty()) {
353 const E* cur = tmp.front();
359 const E* via =
getVia(prev, cur);
373 const E*
getVia(
const E* forwardFrom,
const E* forwardTo)
const {
SUMOVehicleClass
Definition of vehicle classes to differ between different lane usage and authority types.
std::string toString(const T &t, std::streamsize accuracy=gPrecision)
std::pair< const E *, const E * > ConstEdgePair
bool operator()(const typename SUMOAbstractRouter< E, V >::EdgeInfo *nod1, const typename SUMOAbstractRouter< E, V >::EdgeInfo *nod2) const
Comparing method.
EdgeInfoByTTComparator myComparator
const SUMOAbstractRouter< E, V >::EdgeInfo * getEdgeInfo(const E *const edge) const
bool step(const std::vector< ConnectionVector > &uplinks, const Unidirectional &otherSearch, double &minTTSeen, Meeting &meeting)
explore on element from the frontier,update minTTSeen and meeting if an EdgeInfo found by the otherSe...
Unidirectional(const std::vector< E * > &edges, bool forward)
Constructor.
std::vector< typename SUMOAbstractRouter< E, V >::EdgeInfo > myEdgeInfos
The container of edge information.
SUMOAbstractRouter< E, V >::EdgeInfo * getEdgeInfo(const E *const edge)
std::vector< typename CHBuilder< E, V >::Connection > ConnectionVector
bool myAmForward
the role of this search
void init(const E *const start, const V *const vehicle)
bool found(const E *const edge) const
std::vector< typename SUMOAbstractRouter< E, V >::EdgeInfo * > myFrontier
the min edge heap
std::set< const E * > myFound
the set of visited (settled) Edges
Computes the shortest path through a contracted network.
virtual ~CHRouter()
Destructor.
const SUMOTime myWeightPeriod
the validity duration of one weight interval
SUMOTime myValidUntil
the validity duration of the current hierarchy (exclusive)
Unidirectional myBackwardSearch
CHRouter(const std::vector< E * > &edges, bool unbuildIsWarning, typename SUMOAbstractRouter< E, V >::Operation operation, const SUMOVehicleClass svc, SUMOTime weightPeriod, const bool havePermissions, const bool haveRestrictions)
Constructor.
virtual SUMOAbstractRouter< E, V > * clone()
Unidirectional myForwardSearch
the unidirectional search queues
virtual bool compute(const E *from, const E *to, const V *const vehicle, SUMOTime msTime, std::vector< const E * > &into, bool silent=false)
Builds the route between the given edges using the minimum traveltime in the contracted graph.
std::pair< const typename SUMOAbstractRouter< E, V >::EdgeInfo *, const typename SUMOAbstractRouter< E, V >::EdgeInfo * > Meeting
A meeting point of the two search scopes.
void buildPathFromMeeting(Meeting meeting, std::vector< const E * > &into) const
normal routing methods
CHRouter(const std::vector< E * > &edges, bool unbuildIsWarning, typename SUMOAbstractRouter< E, V >::Operation operation, const SUMOVehicleClass svc, typename CHBuilder< E, V >::Hierarchy *hierarchy, const bool havePermissions, const bool haveRestrictions)
Cloning constructor, should be used only for time independent instances which build a hierarchy only ...
CHBuilder< E, V > * myHierarchyBuilder
virtual void reset(const V *const vehicle)
trigger hierarchy rebuild
const std::vector< E * > & myEdges
all edges with numerical ids
const E * getVia(const E *forwardFrom, const E *forwardTo) const
const SUMOVehicleClass mySVC
the permissions for which the hierarchy was constructed
CHBuilder< E, V >::Hierarchy * myHierarchy
static MsgHandler * getWarningInstance()
Returns the instance to add warnings to.
void informf(const std::string &format, T value, Targs... Fargs)
adds a new formatted message
const E *const edge
The current edge.
double effort
Effort to reach the edge.
MsgHandler *const myErrorMsgHandler
the handler for routing errors
const bool myHavePermissions
whether edge permissions need to be considered
Operation myOperation
The object's operation to perform.
const bool myHaveRestrictions
whether edge restrictions need to be considered
void endQuery(int visits)