21 #ifndef DijkstraRouter_h 22 #define DijkstraRouter_h 68 template<
class E,
class V,
class PF>
72 typedef double(*
Operation)(
const E*
const,
const V*
const, double);
101 effort = std::numeric_limits<double>::max();
120 return nod1->
edge->getNumericalID() > nod2->
edge->getNumericalID();
131 for (
typename std::vector<E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
143 inline double getTravelTime(
const E*
const e,
const V*
const v,
const double t,
const double effort)
const {
153 for (
typename std::vector<EdgeInfo*>::iterator i =
myFound.begin(); i !=
myFound.end(); i++) {
162 virtual bool compute(
const E* from,
const E* to,
const V*
const vehicle,
163 SUMOTime msTime, std::vector<const E*>& into) {
164 assert(from != 0 && (vehicle == 0 || to != 0));
166 if (PF::operator()(from, vehicle)) {
167 myErrorMsgHandler->
inform(
"Vehicle '" + vehicle->getID() +
"' is not allowed on source edge '" + from->getID() +
"'.");
170 if (PF::operator()(to, vehicle)) {
171 myErrorMsgHandler->
inform(
"Vehicle '" + vehicle->getID() +
"' is not allowed on destination edge '" + to->getID() +
"'.");
175 #ifdef DijkstraRouter_DEBUG_QUERY 176 std::cout <<
"DEBUG: starting search for '" << vehicle->getID() <<
"' time: " <<
STEPS2TIME(msTime) <<
"\n";
181 if (toInfo.visited) {
190 fromInfo->effort = 0;
201 const E*
const minEdge = minimumInfo->edge;
206 #ifdef DijkstraRouter_DEBUG_QUERY_PERF 207 std::cout <<
"visited " +
toString(num_visited) +
" edges (final path length=" +
toString(into.size()) +
" edges=" +
toString(into) +
")\n";
213 myFound.push_back(minimumInfo);
214 minimumInfo->visited =
true;
215 #ifdef DijkstraRouter_DEBUG_QUERY 216 std::cout <<
"DEBUG: hit '" << minEdge->getID() <<
"' Eff: " << minimumInfo->effort <<
", TT: " << minimumInfo->leaveTime <<
" Q: ";
218 std::cout << (*it)->effort <<
"," << (*it)->edge->getID() <<
" ";
222 const double effortDelta = this->
getEffort(minEdge, vehicle, minimumInfo->leaveTime);
223 const double effort = minimumInfo->effort + effortDelta;
224 const double leaveTime = minimumInfo->leaveTime +
getTravelTime(minEdge, vehicle, minimumInfo->leaveTime, effortDelta);
226 const std::vector<E*>& successors = minEdge->getSuccessors(vClass);
227 for (
typename std::vector<E*>::const_iterator it = successors.begin(); it != successors.end(); ++it) {
228 const E*
const follower = *it;
231 if (PF::operator()(follower, vehicle)) {
234 const double oldEffort = followerInfo->effort;
235 if (!followerInfo->visited && effort < oldEffort) {
236 followerInfo->effort =
effort;
238 followerInfo->prev = minimumInfo;
239 if (oldEffort == std::numeric_limits<double>::max()) {
251 #ifdef DijkstraRouter_DEBUG_QUERY_PERF 252 std::cout <<
"visited " +
toString(num_visited) +
" edges (unsuccesful path length: " +
toString(into.size()) +
")\n";
255 myErrorMsgHandler->
inform(
"No connection between edge '" + from->getID() +
"' and edge '" + to->getID() +
"' found.");
264 for (
const E*
const e : edges) {
265 if (PF::operator()(e, v)) {
268 const double effortDelta = this->
getEffort(e, v, t);
269 costs += effortDelta;
277 std::vector<const E*> tmp;
278 while (rbegin != 0) {
279 tmp.push_back(rbegin->edge);
280 rbegin = rbegin->prev;
282 std::copy(tmp.rbegin(), tmp.rend(), std::back_inserter(edges));
293 for (
const EdgeInfo& ei : edgeInfos) {
static MsgHandler * getWarningInstance()
Returns the instance to add warnings to.
double getEffort(const E *const e, const V *const v, double t) const
void buildPathFrom(const EdgeInfo *rbegin, std::vector< const E *> &edges)
Builds the path from marked edges.
bool visited
The previous edge.
MsgHandler *const myErrorMsgHandler
the handler for routing errors
EdgeInfo(const E *const e)
Constructor.
EdgeInfo & operator=(const EdgeInfo &s)=delete
Invalidated assignment operator.
const EdgeInfo & getEdgeInfo(int index) const
SUMOVehicleClass
Definition of vehicle classes to differ between different lane usage and authority types...
double recomputeCosts(const std::vector< const E *> &edges, const V *const v, SUMOTime msTime) const
std::vector< EdgeInfo * > myFound
list of visited Edges (for resetting)
Operation myTTOperation
The object's operation to perform for travel times.
virtual ~DijkstraRouter()
Destructor.
double leaveTime
The time the vehicle leaves the edge.
const E *const edge
The current edge.
std::string toString(const T &t, std::streamsize accuracy=gPrecision)
double getTravelTime(const E *const e, const V *const v, const double t, const double effort) const
Computes the shortest path through a network using the Dijkstra algorithm.
DijkstraRouter(const std::vector< E *> &edges, bool unbuildIsWarning, Operation effortOperation, Operation ttOperation=nullptr)
Constructor.
double(* Operation)(const E *const, const V *const, double)
bool myBulkMode
whether we are currently operating several route queries in a bulk
Operation myOperation
The object's operation to perform.
DijkstraRouter(const std::vector< EdgeInfo > &edgeInfos, bool unbuildIsWarning, Operation effortOperation, Operation ttOperation)
virtual bool compute(const E *from, const E *to, const V *const vehicle, SUMOTime msTime, std::vector< const E *> &into)
Builds the route between the given edges using the minimum effort at the given time The definition of...
EdgeInfoByEffortComparator myComparator
void inform(std::string msg, bool addType=true)
adds a new error to the list
std::vector< EdgeInfo * > myFrontierList
A container for reusage of the min edge heap.
std::vector< EdgeInfo > myEdgeInfos
The container of edge information.
void endQuery(int visits)
bool operator()(const EdgeInfo *nod1, const EdgeInfo *nod2) const
Comparing method.
virtual SUMOAbstractRouter< E, V > * clone()
vehicles ignoring classes
const EdgeInfo * prev
The previous edge.
double effort
Effort to reach the edge.