58template<
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 prohibit(
const std::vector<E*>& toProhibit) {
271 if (toProhibit.size() > 0) {
272 WRITE_WARNINGF(
TL(
"Routing algorithm CH does not support dynamic closing of edges%"),
"");
278 virtual void reset(
const V*
const vehicle) {
295 virtual bool compute(
const E* from,
const E* to,
const V*
const vehicle,
296 SUMOTime msTime, std::vector<const E*>& into,
bool silent =
false) {
297 assert(from !=
nullptr && to !=
nullptr);
305 this->
reset(vehicle);
311 double minTTSeen = std::numeric_limits<double>::max();
312 Meeting meeting(
nullptr,
nullptr);
313 bool continueForward =
true;
314 bool continueBackward =
true;
315 int num_visited_fw = 0;
316 int num_visited_bw = 0;
318 while (continueForward || continueBackward) {
319 if (continueForward) {
323 if (continueBackward) {
328 if (minTTSeen < std::numeric_limits<double>::max()) {
336#ifdef CHRouter_DEBUG_QUERY_PERF
337 std::cout <<
"visited " << num_visited_fw + num_visited_bw <<
" edges (" << num_visited_fw <<
"," << num_visited_bw <<
") ,final path length: " +
toString(into.size()) +
")\n";
339 this->
endQuery(num_visited_bw + num_visited_fw);
347 std::deque<const E*> tmp;
348 const auto* backtrack = meeting.first;
349 while (backtrack != 0) {
350 tmp.push_front((E*) backtrack->edge);
351 backtrack = backtrack->prev;
353 backtrack = meeting.second->prev;
354 while (backtrack != 0) {
355 tmp.push_back((E*) backtrack->edge);
356 backtrack = backtrack->prev;
360 while (!tmp.empty()) {
361 const E* cur = tmp.front();
367 const E* via =
getVia(prev, cur);
381 const E*
getVia(
const E* forwardFrom,
const E* forwardTo)
const {
#define WRITE_WARNINGF(...)
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.
SUMOAbstractRouter< E, V >::EdgeInfo * getEdgeInfo(const E *const edge)
EdgeInfoByTTComparator myComparator
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.
const SUMOAbstractRouter< E, V >::EdgeInfo * getEdgeInfo(const E *const edge) const
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 SUMOAbstractRouter< E, V > * clone()
virtual ~CHRouter()
Destructor.
const SUMOTime myWeightPeriod
the validity duration of one weight interval
const E * getVia(const E *forwardFrom, const E *forwardTo) const
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.
CHBuilder< E, V >::Hierarchy * myHierarchy
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
virtual void prohibit(const std::vector< E * > &toProhibit)
const SUMOVehicleClass mySVC
the permissions for which the hierarchy was constructed
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)