62 template<
class E,
class V,
class BASE>
67 typedef double(*
Operation)(
const E*
const,
const V*
const, double);
70 typedef std::pair<const typename BASE::EdgeInfo*, const typename BASE::EdgeInfo*>
Meeting;
82 for (
const E*
const e : edges) {
87 inline bool found(
const E*
const edge)
const {
91 inline typename BASE::EdgeInfo*
getEdgeInfo(
const E*
const edge) {
95 inline const typename BASE::EdgeInfo*
getEdgeInfo(
const E*
const edge)
const {
106 bool operator()(
const typename BASE::EdgeInfo* nod1,
const typename BASE::EdgeInfo* nod2)
const {
107 if (nod1->effort == nod2->effort) {
108 return nod1->edge->getNumericalID() > nod2->edge->getNumericalID();
110 return nod1->effort > nod2->effort;
115 void init(
const E*
const start,
const V*
const vehicle) {
116 assert(vehicle != 0);
128 startInfo->effort = 0.;
129 startInfo->prev =
nullptr;
145 const E*
const minEdge = minimumInfo->edge;
146 #ifdef CHRouter_DEBUG_QUERY
147 std::cout <<
"DEBUG: " << (
myAmForward ?
"Forward" :
"Backward") <<
" hit '" << minEdge->getID() <<
"' Q: ";
148 for (
typename std::vector<EdgeInfo*>::iterator it =
myFrontier.begin(); it !=
myFrontier.end(); it++) {
149 std::cout << (*it)->traveltime <<
"," << (*it)->edge->getID() <<
" ";
153 if (otherSearch.
found(minEdge)) {
154 const auto*
const otherInfo = otherSearch.
getEdgeInfo(minEdge);
155 const double ttSeen = minimumInfo->effort + otherInfo->effort;
156 #ifdef CHRouter_DEBUG_QUERY
157 std::cout <<
"DEBUG: " << (
myAmForward ?
"Forward" :
"Backward") <<
"-Search hit other search at '" << minEdge->getID() <<
"', tt: " << ttSeen <<
" \n";
159 if (ttSeen < minTTSeen) {
162 meeting.first = minimumInfo;
163 meeting.second = otherInfo;
165 meeting.first = otherInfo;
166 meeting.second = minimumInfo;
171 minimumInfo->visited =
true;
173 myFound.insert(minimumInfo->edge);
174 for (
const auto& uplink : uplinks[minEdge->getNumericalID()]) {
175 const auto upwardInfo = &
myEdgeInfos[uplink.target];
176 const double effort = minimumInfo->effort + uplink.cost;
179 if ((uplink.permissions & svc) != svc) {
182 const double oldEffort = upwardInfo->effort;
183 if (!upwardInfo->visited && effort < oldEffort) {
184 upwardInfo->effort = effort;
185 upwardInfo->prev = minimumInfo;
186 if (oldEffort == std::numeric_limits<double>::max()) {
225 CHRouter(
const std::vector<E*>& edges,
bool unbuildIsWarning,
typename BASE::Operation operation,
228 bool validatePermissions):
229 BASE(
"CHRouter", unbuildIsWarning, operation),
242 CHRouter(
const std::vector<E*>& edges,
bool unbuildIsWarning,
typename BASE::Operation operation,
246 BASE(
"CHRouterClone", unbuildIsWarning, operation),
278 virtual bool compute(
const E* from,
const E* to,
const V*
const vehicle,
279 SUMOTime msTime, std::vector<const E*>& into,
bool silent =
false) {
280 assert(from != 0 && to != 0);
293 double minTTSeen = std::numeric_limits<double>::max();
294 Meeting meeting(
nullptr,
nullptr);
295 bool continueForward =
true;
296 bool continueBackward =
true;
297 int num_visited_fw = 0;
298 int num_visited_bw = 0;
300 while (continueForward || continueBackward) {
301 if (continueForward) {
305 if (continueBackward) {
310 if (minTTSeen < std::numeric_limits<double>::max()) {
314 this->myErrorMsgHandler->inform(
"No connection between edge '" + from->getID() +
"' and edge '" + to->getID() +
"' found.");
318 #ifdef CHRouter_DEBUG_QUERY_PERF
319 std::cout <<
"visited " << num_visited_fw + num_visited_bw <<
" edges (" << num_visited_fw <<
"," << num_visited_bw <<
") ,final path length: " +
toString(into.size()) +
")\n";
321 this->endQuery(num_visited_bw + num_visited_fw);
329 std::deque<const E*> tmp;
330 const auto* backtrack = meeting.first;
331 while (backtrack != 0) {
332 tmp.push_front((E*) backtrack->edge);
333 backtrack = backtrack->prev;
335 backtrack = meeting.second->prev;
336 while (backtrack != 0) {
337 tmp.push_back((E*) backtrack->edge);
338 backtrack = backtrack->prev;
342 while (!tmp.empty()) {
343 const E* cur = tmp.front();
349 const E* via =
getVia(prev, cur);
376 const E*
getVia(
const E* forwardFrom,
const E* forwardTo)
const {