58 template<
class E,
class V>
70 return nod1->
edge->getNumericalID() > nod2->
edge->getNumericalID();
80 const bool havePermissions =
false,
const bool haveRestrictions =
false) :
81 SUMOAbstractRouter<E, V>(
"DijkstraRouter", unbuildIsWarning, effortOperation, ttOperation, havePermissions, haveRestrictions),
83 for (
typename std::vector<E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
105 for (
auto& edgeInfo :
myFound) {
114 bool compute(
const E* from,
const E* to,
const V*
const vehicle,
115 SUMOTime msTime, std::vector<const E*>& into,
bool silent =
false) {
116 assert(from !=
nullptr && (vehicle ==
nullptr || to !=
nullptr));
118 if (
myEdgeInfos[from->getNumericalID()].prohibited || this->isProhibited(from, vehicle)) {
124 if (to !=
nullptr && (
myEdgeInfos[to->getNumericalID()].prohibited || this->isProhibited(to, vehicle))) {
132 #ifdef DijkstraRouter_DEBUG_QUERY
136 std::tuple<const E*, const V*, SUMOTime> query = std::make_tuple(from, vehicle, msTime);
138 const auto& toInfo =
myEdgeInfos[to->getNumericalID()];
139 if (toInfo.visited) {
147 auto*
const fromInfo = &(
myEdgeInfos[from->getNumericalID()]);
148 fromInfo->effort = 0.;
149 fromInfo->prev =
nullptr;
163 const E*
const minEdge = minimumInfo->edge;
164 #ifdef DijkstraRouter_DEBUG_QUERY
165 std::cout <<
"DEBUG: hit '" << minEdge->getID() <<
"' Eff: " << minimumInfo->effort <<
", Leave: " << minimumInfo->leaveTime <<
" Q: ";
167 std::cout << it->effort <<
"," << it->edge->getID() <<
" ";
175 myExternalEffort->
update(minEdge->getNumericalID(), minimumInfo->prev->edge->getNumericalID(), minEdge->getLength());
179 #ifdef DijkstraRouter_DEBUG_QUERY_PERF
180 std::cout <<
"visited " +
toString(num_visited) +
" edges (final path length=" +
toString(into.size()) +
" edges=" +
toString(into) +
")\n";
186 myFound.push_back(minimumInfo);
187 minimumInfo->visited =
true;
188 const double effortDelta = this->
getEffort(minEdge, vehicle, minimumInfo->leaveTime);
189 const double leaveTime = minimumInfo->leaveTime + this->
getTravelTime(minEdge, vehicle, minimumInfo->leaveTime, effortDelta);
191 myExternalEffort->
update(minEdge->getNumericalID(), minimumInfo->prev->edge->getNumericalID(), minEdge->getLength());
194 for (
const std::pair<const E*, const E*>& follower : minEdge->getViaSuccessors(vClass)) {
195 auto*
const followerInfo = &(
myEdgeInfos[follower.first->getNumericalID()]);
197 if (followerInfo->prohibited || this->isProhibited(follower.first, vehicle)) {
200 double effort = minimumInfo->effort + effortDelta;
201 double time = leaveTime;
203 assert(effort >= minimumInfo->effort);
204 assert(time >= minimumInfo->leaveTime);
205 const double oldEffort = followerInfo->effort;
206 if (!followerInfo->visited && effort < oldEffort) {
207 followerInfo->effort = effort;
208 followerInfo->leaveTime = time;
209 followerInfo->prev = minimumInfo;
210 if (oldEffort == std::numeric_limits<double>::max()) {
222 #ifdef DijkstraRouter_DEBUG_QUERY_PERF
223 std::cout <<
"visited " +
toString(num_visited) +
" edges (unsuccessful path length: " +
toString(into.size()) +
")\n";
225 if (to !=
nullptr && !
mySilent && !silent) {
234 myEdgeInfos[edge->getNumericalID()].prohibited =
false;
236 for (E*
const edge : toProhibit) {
237 myEdgeInfos[edge->getNumericalID()].prohibited =
true;
239 this->myProhibited = toProhibit;
245 std::vector<const E*> tmp;
246 while (rbegin != 0) {
247 tmp.push_back(rbegin->
edge);
248 rbegin = rbegin->
prev;
250 std::copy(tmp.rbegin(), tmp.rend(), std::back_inserter(edges));
260 const bool havePermissions,
const bool haveRestrictions) :
261 SUMOAbstractRouter<E, V>(
"DijkstraRouter", unbuildIsWarning, effortOperation, ttOperation, havePermissions, haveRestrictions),
264 for (
const auto& edgeInfo : edgeInfos) {
279 std::vector<typename SUMOAbstractRouter<E, V>::EdgeInfo>
myEdgeInfos;
284 std::vector<typename SUMOAbstractRouter<E, V>::EdgeInfo*>
myFound;
SUMOVehicleClass
Definition of vehicle classes to differ between different lane usage and authority types.
@ SVC_IGNORING
vehicles ignoring classes
std::string toString(const T &t, std::streamsize accuracy=gPrecision)
bool operator()(const typename SUMOAbstractRouter< E, V >::EdgeInfo *nod1, const typename SUMOAbstractRouter< E, V >::EdgeInfo *nod2) const
Comparing method.
Computes the shortest path through a network using the Dijkstra algorithm.
void buildPathFrom(const typename SUMOAbstractRouter< E, V >::EdgeInfo *rbegin, std::vector< const E * > &edges)
Builds the path from marked edges.
std::vector< typename SUMOAbstractRouter< E, V >::EdgeInfo * > myFound
list of visited Edges (for resetting)
bool mySilent
whether to suppress warning/error if no route was found
std::tuple< const E *, const V *, SUMOTime > myLastQuery
cache of the last query to enable automated bulk routing
EffortCalculator *const myExternalEffort
const SUMOAbstractRouter< E, V >::EdgeInfo & getEdgeInfo(int index) const
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...
void prohibit(const std::vector< E * > &toProhibit)
DijkstraRouter(const std::vector< E * > &edges, bool unbuildIsWarning, typename SUMOAbstractRouter< E, V >::Operation effortOperation, typename SUMOAbstractRouter< E, V >::Operation ttOperation=nullptr, bool silent=false, EffortCalculator *calc=nullptr, const bool havePermissions=false, const bool haveRestrictions=false)
Constructor.
EdgeInfoByEffortComparator myComparator
std::vector< typename SUMOAbstractRouter< E, V >::EdgeInfo > myEdgeInfos
The container of edge information.
virtual ~DijkstraRouter()
Destructor.
std::vector< typename SUMOAbstractRouter< E, V >::EdgeInfo * > myFrontierList
A container for reusage of the min edge heap.
virtual SUMOAbstractRouter< E, V > * clone()
DijkstraRouter(const std::vector< typename SUMOAbstractRouter< E, V >::EdgeInfo > &edgeInfos, bool unbuildIsWarning, typename SUMOAbstractRouter< E, V >::Operation effortOperation, typename SUMOAbstractRouter< E, V >::Operation ttOperation, bool silent, EffortCalculator *calc, const bool havePermissions, const bool haveRestrictions)
the effort calculator interface
virtual void setInitialState(const int edge)=0
virtual void update(const int edge, const int prev, const double length)=0
virtual void inform(std::string msg, bool addType=true)
adds a new error to the list
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
static std::string getIDSecure(const T *obj, const std::string &fallBack="NULL")
get an identifier for Named-like object which may be Null
const E *const edge
The current edge.
double effort
Effort to reach the edge.
const EdgeInfo * prev
The previous edge.
Operation myTTOperation
The object's operation to perform for travel times.
MsgHandler *const myErrorMsgHandler
the handler for routing errors
std::vector< E * > myProhibited
const bool myHavePermissions
whether edge permissions need to be considered
bool myBulkMode
whether we are currently operating several route queries in a bulk
Operation myOperation
The object's operation to perform.
double getTravelTime(const E *const e, const V *const v, const double t, const double effort) const
double getEffort(const E *const e, const V *const v, double t) const
void updateViaEdgeCost(const E *viaEdge, const V *const v, double &time, double &effort, double &length) const
const bool myHaveRestrictions
whether edge restrictions need to be considered
bool myAutoBulkMode
whether we are currently trying to detect bulk mode automatically
void endQuery(int visits)