44 #define DijkstraRouter_DEBUG_QUERY_VISITED_OUT std::cerr
62 template<
class E,
class V>
74 return nod1->
edge->getNumericalID() > nod2->
edge->getNumericalID();
84 const bool havePermissions =
false,
const bool haveRestrictions =
false) :
85 SUMOAbstractRouter<E, V>(
"DijkstraRouter", unbuildIsWarning, effortOperation, ttOperation, havePermissions, haveRestrictions),
87 for (
typename std::vector<E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
105 bool compute(
const E* from,
const E* to,
const V*
const vehicle,
106 SUMOTime msTime, std::vector<const E*>& into,
bool silent =
false) {
107 assert(from !=
nullptr && (vehicle ==
nullptr || to !=
nullptr));
109 if (this->
myEdgeInfos[from->getNumericalID()].prohibited || this->isProhibited(from, vehicle)) {
115 if (to !=
nullptr && (this->
myEdgeInfos[to->getNumericalID()].prohibited || this->isProhibited(to, vehicle))) {
123 #ifdef DijkstraRouter_DEBUG_QUERY
127 std::tuple<const E*, const V*, SUMOTime> query = std::make_tuple(from, vehicle, msTime);
129 #ifdef DijkstraRouter_DEBUG_BULKMODE
131 std::cout <<
" invalid bulk mode. myLastQuery="
136 << std::get<0>(query)->getID() <<
","
137 << std::get<1>(query)->getID() <<
","
142 const auto& toInfo = this->
myEdgeInfos[to->getNumericalID()];
143 if (toInfo.visited) {
149 this->
init(from->getNumericalID(), msTime);
158 #ifdef DijkstraRouter_DEBUG_QUERY_VISITED
165 const E*
const minEdge = minimumInfo->edge;
166 #ifdef DijkstraRouter_DEBUG_QUERY
167 std::cout <<
"DEBUG: hit '" << minEdge->getID() <<
"' Eff: " << minimumInfo->effort <<
", Leave: " << minimumInfo->leaveTime <<
" Q: ";
169 std::cout <<
"\n " << it->effort <<
", " << it->edge->getID();
173 #ifdef DijkstraRouter_DEBUG_QUERY_VISITED
174 DijkstraRouter_DEBUG_QUERY_VISITED_OUT <<
" <edge id=\"" << minEdge->getID() <<
"\" index=\"" << num_visited <<
"\" cost=\"" << minimumInfo->effort <<
"\" time=\"" << minimumInfo->leaveTime <<
"\"/>\n";
180 myExternalEffort->
update(minEdge->getNumericalID(), minimumInfo->prev->edge->getNumericalID(), minEdge->getLength());
184 #ifdef DijkstraRouter_DEBUG_QUERY_PERF
186 std::cout <<
"visited " +
toString(num_visited) +
" edges (final path length=" +
toString(into.size()) +
" cost=" << cost <<
" edges=" +
toString(into) +
")\n";
188 #ifdef DijkstraRouter_DEBUG_QUERY_VISITED
193 std::pop_heap(this->myFrontierList.begin(), this->myFrontierList.end(),
myComparator);
194 this->myFrontierList.pop_back();
195 this->
myFound.push_back(minimumInfo);
196 minimumInfo->visited =
true;
197 const double effortDelta = this->
getEffort(minEdge, vehicle, minimumInfo->leaveTime);
198 const double leaveTime = minimumInfo->leaveTime + this->
getTravelTime(minEdge, vehicle, minimumInfo->leaveTime, effortDelta);
200 myExternalEffort->
update(minEdge->getNumericalID(), minimumInfo->prev->edge->getNumericalID(), minEdge->getLength());
203 for (
const std::pair<const E*, const E*>& follower : minEdge->getViaSuccessors(vClass)) {
204 auto& followerInfo = this->
myEdgeInfos[follower.first->getNumericalID()];
206 if (followerInfo.prohibited || this->isProhibited(follower.first, vehicle)) {
209 double effort = minimumInfo->effort + effortDelta;
210 double time = leaveTime;
212 assert(effort >= minimumInfo->effort);
213 assert(time >= minimumInfo->leaveTime);
214 const double oldEffort = followerInfo.effort;
215 if (!followerInfo.visited && effort < oldEffort) {
216 followerInfo.effort = effort;
217 followerInfo.leaveTime = time;
218 followerInfo.prev = minimumInfo;
219 if (oldEffort == std::numeric_limits<double>::max()) {
220 this->myFrontierList.push_back(&followerInfo);
221 std::push_heap(this->myFrontierList.begin(), this->myFrontierList.end(),
myComparator);
223 std::push_heap(this->myFrontierList.begin(),
224 std::find(this->myFrontierList.begin(), this->myFrontierList.end(), &followerInfo) + 1,
231 #ifdef DijkstraRouter_DEBUG_QUERY_PERF
232 std::cout <<
"visited " +
toString(num_visited) +
" edges (unsuccessful path length: " +
toString(into.size()) +
")\n";
234 if (to !=
nullptr && !
mySilent && !silent) {
237 #ifdef DijkstraRouter_DEBUG_QUERY_VISITED
246 const bool havePermissions,
const bool haveRestrictions) :
247 SUMOAbstractRouter<E, V>(
"DijkstraRouter", unbuildIsWarning, effortOperation, ttOperation, havePermissions, haveRestrictions),
250 for (
const auto& edgeInfo : edgeInfos) {
#define DijkstraRouter_DEBUG_QUERY_VISITED_OUT
std::string time2string(SUMOTime t)
convert SUMOTime to string
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.
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
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 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
virtual ~DijkstraRouter()
Destructor.
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.
Operation myTTOperation
The object's operation to perform for travel times.
MsgHandler *const myErrorMsgHandler
the handler for routing errors
const bool myHavePermissions
whether edge permissions need to be considered
bool myBulkMode
whether we are currently operating several route queries in a bulk
double recomputeCosts(const std::vector< const E * > &edges, const V *const v, SUMOTime msTime, double *lengthp=nullptr) const
std::vector< typename SUMOAbstractRouter< E, V >::EdgeInfo > myEdgeInfos
The container of edge information.
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
void init(const int edgeID, const SUMOTime msTime)
bool myAmClean
whether we are already initialized
const bool myHaveRestrictions
whether edge restrictions need to be considered
void buildPathFrom(const typename SUMOAbstractRouter< E, V >::EdgeInfo *rbegin, std::vector< const E * > &edges)
Builds the path from marked edges.
bool myAutoBulkMode
whether we are currently trying to detect bulk mode automatically
void endQuery(int visits)
std::vector< typename SUMOAbstractRouter< E, V >::EdgeInfo * > myFrontierList
A container for reusage of the min edge heap.
std::vector< typename SUMOAbstractRouter< E, V >::EdgeInfo * > myFound
list of visited Edges (for resetting)