 |
Eclipse SUMO - Simulation of Urban MObility
|
Go to the documentation of this file.
18 #ifndef DijkstraRouter_h
19 #define DijkstraRouter_h
60 template<
class E,
class V>
72 return nod1->
edge->getNumericalID() > nod2->
edge->getNumericalID();
82 const bool havePermissions =
false,
const bool haveRestrictions =
false) :
83 SUMOAbstractRouter<E, V>(
"DijkstraRouter", unbuildIsWarning, effortOperation, ttOperation, havePermissions, haveRestrictions),
85 for (
typename std::vector<E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
104 for (
auto& edgeInfo :
myFound) {
113 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 !=
nullptr && (vehicle ==
nullptr || to !=
nullptr));
117 if (
myEdgeInfos[from->getNumericalID()].prohibited || this->isProhibited(from, vehicle)) {
123 if (to !=
nullptr && (
myEdgeInfos[to->getNumericalID()].prohibited || this->isProhibited(to, vehicle))) {
131 #ifdef DijkstraRouter_DEBUG_QUERY
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());
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 (followerInfo->prohibited || this->isProhibited(follower.first, vehicle)) {
197 double effort = minimumInfo->effort + effortDelta;
198 double time = leaveTime;
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()) {
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) {
231 myEdgeInfos[edge->getNumericalID()].prohibited =
false;
233 for (E*
const edge : toProhibit) {
234 myEdgeInfos[edge->getNumericalID()].prohibited =
true;
236 this->myProhibited = toProhibit;
242 std::vector<const E*> tmp;
243 while (rbegin != 0) {
244 tmp.push_back(rbegin->
edge);
245 rbegin = rbegin->
prev;
247 std::copy(tmp.rbegin(), tmp.rend(), std::back_inserter(edges));
257 const bool havePermissions,
const bool haveRestrictions) :
258 SUMOAbstractRouter<E, V>(
"DijkstraRouter", unbuildIsWarning, effortOperation, ttOperation, havePermissions, haveRestrictions),
261 for (
const auto& edgeInfo : edgeInfos) {
273 std::vector<typename SUMOAbstractRouter<E, V>::EdgeInfo>
myEdgeInfos;
278 std::vector<typename SUMOAbstractRouter<E, V>::EdgeInfo*>
myFound;
SUMOVehicleClass
Definition of vehicle classes to differ between different lane usage and authority types.
virtual ~DijkstraRouter()
Destructor.
const bool myHavePermissions
whether edge permissions need to be considered
std::vector< typename SUMOAbstractRouter< E, V >::EdgeInfo * > myFound
list of visited Edges (for resetting)
double getEffort(const E *const e, const V *const v, double t) const
virtual void inform(std::string msg, bool addType=true)
adds a new error to the list
std::vector< E * > myProhibited
EdgeInfoByEffortComparator myComparator
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.
double effort
Effort to reach the edge.
Operation myOperation
The object's operation to perform.
Computes the shortest path through a network using the Dijkstra algorithm.
bool mySilent
whether to supress warning/error if no route was found
void buildPathFrom(const typename SUMOAbstractRouter< E, V >::EdgeInfo *rbegin, std::vector< const E * > &edges)
Builds the path from marked edges.
static MsgHandler * getWarningInstance()
Returns the instance to add warnings to.
virtual void update(const int edge, const int prev, const double length)=0
bool operator()(const typename SUMOAbstractRouter< E, V >::EdgeInfo *nod1, const typename SUMOAbstractRouter< E, V >::EdgeInfo *nod2) const
Comparing method.
const bool myHaveRestrictions
whether edge restrictions need to be considered
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)
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...
std::vector< typename SUMOAbstractRouter< E, V >::EdgeInfo * > myFrontierList
A container for reusage of the min edge heap.
const EdgeInfo * prev
The previous edge.
const SUMOAbstractRouter< E, V >::EdgeInfo & getEdgeInfo(int index) const
const E *const edge
The current edge.
bool myBulkMode
whether we are currently operating several route queries in a bulk
double getTravelTime(const E *const e, const V *const v, const double t, const double effort) const
void endQuery(int visits)
std::string toString(const T &t, std::streamsize accuracy=gPrecision)
void prohibit(const std::vector< E * > &toProhibit)
MsgHandler *const myErrorMsgHandler
the handler for routing errors
void updateViaEdgeCost(const E *viaEdge, const V *const v, double &time, double &effort, double &length) const
the effort calculator interface
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
EffortCalculator *const myExternalEffort
virtual void setInitialState(const int edge)=0
@ SVC_IGNORING
vehicles ignoring classes
virtual SUMOAbstractRouter< E, V > * clone()
Operation myTTOperation
The object's operation to perform for travel times.
std::vector< typename SUMOAbstractRouter< E, V >::EdgeInfo > myEdgeInfos
The container of edge information.