73 template<
class E,
class V,
class PF>
77 typedef double(*
Operation)(
const E*
const,
const V*
const, double);
128 return nod1->
edge->getNumericalID() > nod2->
edge->getNumericalID();
135 AStarRouter(
const std::vector<E*>& edges,
bool unbuildIsWarning,
Operation operation,
const LookupTable*
const lookup = 0):
140 for (
typename std::vector<E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
146 AStarRouter(
const std::vector<EdgeInfo>& edgeInfos,
bool unbuildIsWarning,
Operation operation,
const LookupTable*
const lookup = 0):
151 for (
typename std::vector<EdgeInfo>::const_iterator i = edgeInfos.begin(); i != edgeInfos.end(); ++i) {
167 for (
int i = 0; i < size; i++) {
168 for (
int j = 0; j < size; j++) {
171 (*result)[i].push_back(val);
183 for (
typename std::vector<EdgeInfo*>::iterator i =
myFound.begin(); i !=
myFound.end(); i++) {
191 virtual bool compute(
const E* from,
const E* to,
const V*
const vehicle,
192 SUMOTime msTime, std::vector<const E*>& into) {
193 assert(from != 0 && to != 0);
195 if (PF::operator()(from, vehicle)) {
196 myErrorMsgHandler->
inform(
"Vehicle '" + vehicle->getID() +
"' is not allowed on source edge '" + from->getID() +
"'.");
199 if (PF::operator()(to, vehicle)) {
200 myErrorMsgHandler->
inform(
"Vehicle '" + vehicle->getID() +
"' is not allowed on destination edge '" + to->getID() +
"'.");
204 #ifdef ASTAR_DEBUG_QUERY 205 std::cout <<
"DEBUG: starting search for '" << vehicle->getID() <<
"' speed: " <<
MIN2(vehicle->getMaxSpeed(),
myMaxSpeed * vehicle->getChosenSpeedFactor()) <<
" time: " <<
STEPS2TIME(msTime) <<
"\n";
211 if (toInfo.visited) {
220 fromInfo->traveltime = 0;
226 const double speed =
MIN2(vehicle->getMaxSpeed(),
myMaxSpeed * vehicle->getChosenSpeedFactor());
231 const E*
const minEdge = minimumInfo->edge;
236 #ifdef ASTAR_DEBUG_QUERY_PERF 237 std::cout <<
"visited " +
toString(num_visited) +
" edges (final path length=" +
toString(into.size())
239 +
" edges=" +
toString(into) +
")\n";
241 #ifdef ASTAR_DEBUG_VISITED 243 for (
typename std::vector<EdgeInfo>::const_iterator i =
myEdgeInfos.begin(); i !=
myEdgeInfos.end(); ++i) {
245 dev <<
"edge:" << i->edge->getID() <<
"\n";
254 myFound.push_back(minimumInfo);
255 minimumInfo->visited =
true;
256 #ifdef ASTAR_DEBUG_QUERY 257 std::cout <<
"DEBUG: hit '" << minEdge->getID() <<
"' TT: " << minimumInfo->traveltime <<
" E: " << this->
getEffort(minEdge, vehicle, time + minimumInfo->traveltime) <<
" Q: ";
259 std::cout << (*it)->traveltime <<
"," << (*it)->edge->getID() <<
" ";
263 const double traveltime = minimumInfo->traveltime + this->
getEffort(minEdge, vehicle, time + minimumInfo->traveltime);
265 const double heuristic_remaining =
myLookupTable == 0 ? minEdge->getDistanceTo(to) / speed : (*myLookupTable)[minEdge->getNumericalID()][to->getNumericalID()] / vehicle->getChosenSpeedFactor();
267 const std::vector<E*>& successors = minEdge->getSuccessors(vClass);
268 for (
typename std::vector<E*>::const_iterator it = successors.begin(); it != successors.end(); ++it) {
269 const E*
const follower = *it;
272 if (PF::operator()(follower, vehicle)) {
275 const double oldEffort = followerInfo->traveltime;
276 if (!followerInfo->visited && traveltime < oldEffort) {
278 followerInfo->heuristicTime = traveltime + heuristic_remaining;
290 #ifdef ASTAR_DEBUG_QUERY 293 followerInfo->prev = minimumInfo;
306 #ifdef ASTAR_DEBUG_QUERY_PERF 307 std::cout <<
"visited " +
toString(num_visited) +
" edges (unsuccesful path length: " +
toString(into.size()) +
")\n";
309 myErrorMsgHandler->
inform(
"No connection between edge '" + from->getID() +
"' and edge '" + to->getID() +
"' found.");
317 for (
typename std::vector<const E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
318 if (PF::operator()(*i, v)) {
321 costs += this->
getEffort(*i, v, time + costs);
329 std::vector<const E*> tmp;
330 while (rbegin != 0) {
331 tmp.push_back(rbegin->edge);
332 rbegin = rbegin->prev;
334 std::copy(tmp.rbegin(), tmp.rend(), std::back_inserter(edges));
static MsgHandler * getWarningInstance()
Returns the instance to add warnings to.
double getEffort(const E *const e, const V *const v, double t) const
void close()
Closes the device and removes it from the dictionary.
static LookupTable * createLookupTable(const std::string &filename, const int size)
AStarRouter(const std::vector< EdgeInfo > &edgeInfos, bool unbuildIsWarning, Operation operation, const LookupTable *const lookup=0)
bool visited
The previous edge.
std::vector< EdgeInfo > myEdgeInfos
The container of edge information.
SUMOVehicleClass
Definition of vehicle classes to differ between different lane usage and authority types...
std::vector< EdgeInfo * > myFrontierList
A container for reusage of the min edge heap.
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 travel time.
EdgeInfoComparator myComparator
std::string time2string(SUMOTime t)
MsgHandler *const myErrorMsgHandler
the handler for routing errors
Computes the shortest path through a network using the A* algorithm.
AStarRouter(const std::vector< E *> &edges, bool unbuildIsWarning, Operation operation, const LookupTable *const lookup=0)
Constructor.
double myMaxSpeed
maximum speed in the network
double heuristicTime
Estimated time to reach the edge (traveltime + lower bound on remaining time)
double(* Operation)(const E *const, const V *const, double)
EdgeInfo * prev
The previous edge.
virtual SUMOAbstractRouter< E, V > * clone()
std::string toString(const T &t, std::streamsize accuracy=gPrecision)
EdgeInfo(const E *e)
Constructor.
virtual ~AStarRouter()
Destructor.
bool myBulkMode
whether we are currently operating several route queries in a bulk
void buildPathFrom(const EdgeInfo *rbegin, std::vector< const E *> &edges)
Builds the path from marked edges.
Operation myOperation
The object's operation to perform.
double traveltime
Effort to reach the edge.
bool operator()(const EdgeInfo *nod1, const EdgeInfo *nod2) const
Comparing method.
double recomputeCosts(const std::vector< const E *> &edges, const V *const v, SUMOTime msTime) const
static OutputDevice & getDevice(const std::string &name)
Returns the described OutputDevice.
void inform(std::string msg, bool addType=true)
adds a new error to the list
Static storage of an output device and its base (abstract) implementation.
void endQuery(int visits)
const LookupTable *const myLookupTable
the lookup table for travel time heuristics
std::vector< std::vector< double > > LookupTable
std::vector< EdgeInfo * > myFound
list of visited Edges (for resetting)
vehicles ignoring classes
const E * edge
The current edge.