19 #ifndef DijkstraRouter_h
20 #define DijkstraRouter_h
62 template<
class E,
class V,
class BASE>
72 bool operator()(
const typename BASE::EdgeInfo* nod1,
const typename BASE::EdgeInfo* nod2)
const {
73 if (nod1->effort == nod2->effort) {
74 return nod1->edge->getNumericalID() > nod2->edge->getNumericalID();
76 return nod1->effort > nod2->effort;
82 DijkstraRouter(
const std::vector<E*>& edges,
bool unbuildIsWarning,
typename BASE::Operation effortOperation,
83 typename BASE::Operation ttOperation =
nullptr,
bool silent =
false,
EffortCalculator* calc =
nullptr) :
84 BASE(
"DijkstraRouter", unbuildIsWarning, effortOperation, ttOperation),
86 for (
typename std::vector<E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
104 for (
auto& edgeInfo :
myFound) {
113 virtual bool compute(
const E* from,
const E* to,
const V*
const vehicle,
114 SUMOTime msTime, std::vector<const E*>& into,
bool silent =
false) {
115 assert(from != 0 && (vehicle == 0 || to != 0));
117 if (this->isProhibited(from, vehicle)) {
119 this->myErrorMsgHandler->inform(
"Vehicle '" +
Named::getIDSecure(vehicle) +
"' is not allowed on source edge '" + from->getID() +
"'.");
123 if (this->isProhibited(to, vehicle)) {
125 this->myErrorMsgHandler->inform(
"Vehicle '" +
Named::getIDSecure(vehicle) +
"' is not allowed on destination edge '" + to->getID() +
"'.");
131 #ifdef DijkstraRouter_DEBUG_QUERY
135 if (this->myBulkMode) {
136 const auto& toInfo =
myEdgeInfos[to->getNumericalID()];
137 if (toInfo.visited) {
145 auto*
const fromInfo = &(
myEdgeInfos[from->getNumericalID()]);
146 fromInfo->effort = 0.;
147 fromInfo->prev =
nullptr;
160 const E*
const minEdge = minimumInfo->edge;
161 #ifdef DijkstraRouter_DEBUG_QUERY
162 std::cout <<
"DEBUG: hit '" << minEdge->getID() <<
"' Eff: " << minimumInfo->effort <<
", Leave: " << minimumInfo->leaveTime <<
" Q: ";
164 std::cout << it->effort <<
"," << it->edge->getID() <<
" ";
172 myExternalEffort->
update(minEdge->getNumericalID(), minimumInfo->prev->edge->getNumericalID(), minEdge->getLength());
175 this->endQuery(num_visited);
176 #ifdef DijkstraRouter_DEBUG_QUERY_PERF
177 std::cout <<
"visited " +
toString(num_visited) +
" edges (final path length=" +
toString(into.size()) +
" edges=" +
toString(into) +
")\n";
183 myFound.push_back(minimumInfo);
184 minimumInfo->visited =
true;
185 const double effortDelta = this->getEffort(minEdge, vehicle, minimumInfo->leaveTime);
186 const double leaveTime = minimumInfo->leaveTime + this->
getTravelTime(minEdge, vehicle, minimumInfo->leaveTime, effortDelta);
188 myExternalEffort->
update(minEdge->getNumericalID(), minimumInfo->prev->edge->getNumericalID(), minEdge->getLength());
191 for (
const std::pair<const E*, const E*>& follower : minEdge->getViaSuccessors(vClass)) {
192 auto*
const followerInfo = &(
myEdgeInfos[follower.first->getNumericalID()]);
194 if (this->isProhibited(follower.first, vehicle)) {
197 double effort = minimumInfo->effort + effortDelta;
198 double time = leaveTime;
199 this->updateViaEdgeCost(follower.second, vehicle, time, effort, length);
200 assert(effort >= minimumInfo->effort);
201 assert(time >= minimumInfo->leaveTime);
202 const double oldEffort = followerInfo->effort;
203 if (!followerInfo->visited && effort < oldEffort) {
204 followerInfo->effort = effort;
205 followerInfo->leaveTime = time;
206 followerInfo->prev = minimumInfo;
207 if (oldEffort == std::numeric_limits<double>::max()) {
218 this->endQuery(num_visited);
219 #ifdef DijkstraRouter_DEBUG_QUERY_PERF
220 std::cout <<
"visited " +
toString(num_visited) +
" edges (unsuccessful path length: " +
toString(into.size()) +
")\n";
222 if (to != 0 && !
mySilent && !silent) {
223 this->myErrorMsgHandler->inform(
"No connection between edge '" + from->getID() +
"' and edge '" + to->getID() +
"' found.");
230 void buildPathFrom(
const typename BASE::EdgeInfo* rbegin, std::vector<const E*>& edges) {
231 std::vector<const E*> tmp;
232 while (rbegin != 0) {
233 tmp.push_back(rbegin->edge);
234 rbegin = rbegin->prev;
236 std::copy(tmp.rbegin(), tmp.rend(), std::back_inserter(edges));
244 DijkstraRouter(
const std::vector<typename BASE::EdgeInfo>& edgeInfos,
bool unbuildIsWarning,
245 typename BASE::Operation effortOperation,
typename BASE::Operation ttOperation,
bool silent,
EffortCalculator* calc) :
246 BASE(
"DijkstraRouter", unbuildIsWarning, effortOperation, ttOperation),
249 for (
const auto& edgeInfo : edgeInfos) {
250 myEdgeInfos.push_back(
typename BASE::EdgeInfo(edgeInfo.edge));
266 std::vector<typename BASE::EdgeInfo*>
myFound;