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", effortOperation, ttOperation),
87 for (
typename std::vector<E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
104 myFrontierList.clear();
105 for (
auto& edgeInfo :
myFound) {
114 virtual bool compute(
const E* from,
const E* to,
const V*
const vehicle,
115 SUMOTime msTime, std::vector<const E*>& into) {
116 assert(from != 0 && (vehicle == 0 || to != 0));
118 if (this->isProhibited(from, vehicle)) {
119 myErrorMsgHandler->
inform(
"Vehicle '" + vehicle->getID() +
"' is not allowed on source edge '" + from->getID() +
"'.");
122 if (this->isProhibited(to, vehicle)) {
123 myErrorMsgHandler->
inform(
"Vehicle '" + vehicle->getID() +
"' is not allowed on destination edge '" + to->getID() +
"'.");
127 #ifdef DijkstraRouter_DEBUG_QUERY 128 std::cout <<
"DEBUG: starting search for '" << vehicle->getID() <<
"' time: " <<
STEPS2TIME(msTime) <<
"\n";
131 if (this->myBulkMode) {
132 const auto& toInfo =
myEdgeInfos[to->getNumericalID()];
133 if (toInfo.visited) {
141 auto*
const fromInfo = &(
myEdgeInfos[from->getNumericalID()]);
142 fromInfo->effort = 0.;
143 fromInfo->prev =
nullptr;
153 const E*
const minEdge = minimumInfo->edge;
154 #ifdef DijkstraRouter_DEBUG_QUERY 155 std::cout <<
"DEBUG: hit '" << minEdge->getID() <<
"' Eff: " << minimumInfo->effort <<
", Leave: " << minimumInfo->leaveTime <<
" Q: ";
157 std::cout << it->effort <<
"," << it->edge->getID() <<
" ";
164 this->endQuery(num_visited);
165 #ifdef DijkstraRouter_DEBUG_QUERY_PERF 166 std::cout <<
"visited " +
toString(num_visited) +
" edges (final path length=" +
toString(into.size()) +
" edges=" +
toString(into) +
")\n";
170 pop_heap(myFrontierList.begin(), myFrontierList.end(),
myComparator);
171 myFrontierList.pop_back();
172 myFound.push_back(minimumInfo);
173 minimumInfo->visited =
true;
174 const E* viaEdge = minimumInfo->via;
175 double effort = minimumInfo->effort;
176 double leaveTime = minimumInfo->leaveTime;
177 while (viaEdge !=
nullptr && viaEdge->isInternal()) {
178 const double viaEffortDelta = this->getEffort(viaEdge, vehicle, leaveTime);
179 leaveTime += this->
getTravelTime(viaEdge, vehicle, leaveTime, viaEffortDelta);
180 effort += viaEffortDelta;
181 viaEdge = viaEdge->getViaSuccessors().front().first;
183 const double effortDelta = this->getEffort(minEdge, vehicle, leaveTime);
184 leaveTime += this->
getTravelTime(minEdge, vehicle, minimumInfo->leaveTime, effortDelta);
185 effort += effortDelta;
187 myExternalEffort->
update(minEdge->getNumericalID(), minimumInfo->prev->edge->getNumericalID(), minEdge->getLength());
189 assert(effort >= minimumInfo->effort);
190 assert(leaveTime >= minimumInfo->leaveTime);
192 for (
const std::pair<const E*, const E*>& follower : minEdge->getViaSuccessors(vClass)) {
193 auto*
const followerInfo = &(
myEdgeInfos[follower.first->getNumericalID()]);
195 if (this->isProhibited(follower.first, vehicle)) {
198 const double oldEffort = followerInfo->effort;
199 if (!followerInfo->visited && effort < oldEffort) {
200 followerInfo->effort = effort;
201 followerInfo->leaveTime = leaveTime;
202 followerInfo->prev = minimumInfo;
203 followerInfo->via = follower.second;
204 if (oldEffort == std::numeric_limits<double>::max()) {
205 myFrontierList.push_back(followerInfo);
206 push_heap(myFrontierList.begin(), myFrontierList.end(),
myComparator);
208 push_heap(myFrontierList.begin(),
209 find(myFrontierList.begin(), myFrontierList.end(), followerInfo) + 1,
215 this->endQuery(num_visited);
216 #ifdef DijkstraRouter_DEBUG_QUERY_PERF 217 std::cout <<
"visited " +
toString(num_visited) +
" edges (unsuccessful path length: " +
toString(into.size()) +
")\n";
220 myErrorMsgHandler->
inform(
"No connection between edge '" + from->getID() +
"' and edge '" + to->getID() +
"' found.");
227 void buildPathFrom(
const typename BASE::EdgeInfo* rbegin, std::vector<const E*>& edges) {
228 std::vector<const E*> tmp;
229 while (rbegin != 0) {
230 tmp.push_back(rbegin->edge);
231 rbegin = rbegin->prev;
233 std::copy(tmp.rbegin(), tmp.rend(), std::back_inserter(edges));
241 DijkstraRouter(
const std::vector<typename BASE::EdgeInfo>& edgeInfos,
bool unbuildIsWarning,
242 typename BASE::Operation effortOperation,
typename BASE::Operation ttOperation,
bool silent,
EffortCalculator* calc) :
243 BASE(
"DijkstraRouter", effortOperation, ttOperation),
247 for (
const auto& edgeInfo : edgeInfos) {
248 myEdgeInfos.push_back(
typename BASE::EdgeInfo(edgeInfo.edge));
267 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.
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...
MsgHandler *const myErrorMsgHandler
the handler for routing errors
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
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.
void inform(std::string msg, bool addType=true)
adds a new error to the list
bool mySilent
whether to supress warning/error if no route was found
vehicles ignoring classes