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) {
103 myFrontierList.clear();
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";
181 std::pop_heap(myFrontierList.begin(), myFrontierList.end(),
myComparator);
182 myFrontierList.pop_back();
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()) {
208 myFrontierList.push_back(followerInfo);
209 std::push_heap(myFrontierList.begin(), myFrontierList.end(),
myComparator);
211 std::push_heap(myFrontierList.begin(),
212 std::find(myFrontierList.begin(), myFrontierList.end(), followerInfo) + 1,
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;
static MsgHandler * getWarningInstance()
Returns the instance to add warnings to.
std::vector< typename BASE::EdgeInfo * > myFound
list of visited Edges (for resetting)
SUMOVehicleClass
Definition of vehicle classes to differ between different lane usage and authority types...
void buildPathFrom(const typename BASE::EdgeInfo *rbegin, std::vector< const E *> &edges)
Builds the path from marked edges.
DijkstraRouter(const std::vector< typename BASE::EdgeInfo > &edgeInfos, bool unbuildIsWarning, typename BASE::Operation effortOperation, typename BASE::Operation ttOperation, bool silent, EffortCalculator *calc)
bool operator()(const typename BASE::EdgeInfo *nod1, const typename BASE::EdgeInfo *nod2) const
Comparing method.
static std::string getIDSecure(const T *obj, const std::string &fallBack="NULL")
get an identifier for Named-like object which may be Null
virtual SUMOAbstractRouter< E, V > * clone()
std::vector< typename BASE::EdgeInfo * > myFrontierList
A container for reusage of the min edge heap.
the effort calculator interface
EffortCalculator *const myExternalEffort
std::string toString(const T &t, std::streamsize accuracy=gPrecision)
virtual void update(const int edge, const int prev, const double length)=0
Computes the shortest path through a network using the Dijkstra algorithm.
std::vector< typename BASE::EdgeInfo > myEdgeInfos
The container of edge information.
double getTravelTime(const ROEdge *const edge, const ROVehicle *const, double)
EdgeInfoByEffortComparator myComparator
const BASE::EdgeInfo & getEdgeInfo(int index) const
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 effort at the given time The definition of...
DijkstraRouter(const std::vector< E *> &edges, bool unbuildIsWarning, typename BASE::Operation effortOperation, typename BASE::Operation ttOperation=nullptr, bool silent=false, EffortCalculator *calc=nullptr)
Constructor.
virtual ~DijkstraRouter()
Destructor.
bool mySilent
whether to supress warning/error if no route was found
virtual void setInitialState(const int edge)=0
vehicles ignoring classes