62 template<
class E,
class V,
class BASE>
67 typedef double(*
Operation)(
const E*
const,
const V*
const, double);
70 typedef std::pair<const typename BASE::EdgeInfo*, const typename BASE::EdgeInfo*>
Meeting;
82 for (
const E*
const e: edges) {
87 inline bool found(
const E*
const edge)
const {
91 inline typename BASE::EdgeInfo*
getEdgeInfo(
const E*
const edge) {
95 inline const typename BASE::EdgeInfo*
getEdgeInfo(
const E*
const edge)
const {
106 bool operator()(
const typename BASE::EdgeInfo* nod1,
const typename BASE::EdgeInfo* nod2)
const {
107 if (nod1->effort == nod2->effort) {
108 return nod1->edge->getNumericalID() > nod2->edge->getNumericalID();
110 return nod1->effort > nod2->effort;
115 void init(
const E*
const start,
const V*
const vehicle) {
116 assert(vehicle != 0);
128 startInfo->effort = 0.;
129 startInfo->prev =
nullptr;
130 myFrontier.push_back(startInfo);
139 bool step(
const std::vector<ConnectionVector>& uplinks,
const Unidirectional& otherSearch,
double& minTTSeen, Meeting& meeting) {
145 const E*
const minEdge = minimumInfo->edge;
146 #ifdef CHRouter_DEBUG_QUERY 147 std::cout <<
"DEBUG: " << (
myAmForward ?
"Forward" :
"Backward") <<
" hit '" << minEdge->getID() <<
"' Q: ";
148 for (
typename std::vector<EdgeInfo*>::iterator it =
myFrontier.begin(); it !=
myFrontier.end(); it++) {
149 std::cout << (*it)->traveltime <<
"," << (*it)->edge->getID() <<
" ";
153 if (otherSearch.
found(minEdge)) {
154 const auto*
const otherInfo = otherSearch.
getEdgeInfo(minEdge);
155 const double ttSeen = minimumInfo->effort + otherInfo->effort;
156 #ifdef CHRouter_DEBUG_QUERY 157 std::cout <<
"DEBUG: " << (
myAmForward ?
"Forward" :
"Backward") <<
"-Search hit other search at '" << minEdge->getID() <<
"', tt: " << ttSeen <<
" \n";
159 if (ttSeen < minTTSeen) {
162 meeting.first = minimumInfo;
163 meeting.second = otherInfo;
165 meeting.first = otherInfo;
166 meeting.second = minimumInfo;
171 minimumInfo->visited =
true;
173 myFound.insert(minimumInfo->edge);
174 for (
const auto& uplink : uplinks[minEdge->getNumericalID()]) {
175 const auto upwardInfo = &
myEdgeInfos[uplink.target];
176 const double effort = minimumInfo->effort + uplink.cost;
179 if ((uplink.permissions & svc) != svc) {
182 const double oldEffort = upwardInfo->effort;
183 if (!upwardInfo->visited && effort < oldEffort) {
184 upwardInfo->effort = effort;
185 upwardInfo->prev = minimumInfo;
186 if (oldEffort == std::numeric_limits<double>::max()) {
225 CHRouter(
const std::vector<E*>& edges,
bool unbuildIsWarning,
typename BASE::Operation operation,
228 bool validatePermissions):
229 BASE(
"CHRouter", operation),
243 CHRouter(
const std::vector<E*>& edges,
bool unbuildIsWarning,
typename BASE::Operation operation,
247 BASE(
"CHRouterClone", operation),
280 virtual bool compute(
const E* from,
const E* to,
const V*
const vehicle,
281 SUMOTime msTime, std::vector<const E*>& into) {
282 assert(from != 0 && to != 0);
295 double minTTSeen = std::numeric_limits<double>::max();
296 Meeting meeting(
nullptr,
nullptr);
297 bool continueForward =
true;
298 bool continueBackward =
true;
299 int num_visited_fw = 0;
300 int num_visited_bw = 0;
302 while (continueForward || continueBackward) {
303 if (continueForward) {
307 if (continueBackward) {
312 if (minTTSeen < std::numeric_limits<double>::max()) {
315 myErrorMsgHandler->
inform(
"No connection between edge '" + from->getID() +
"' and edge '" + to->getID() +
"' found.");
318 #ifdef CHRouter_DEBUG_QUERY_PERF 319 std::cout <<
"visited " << num_visited_fw + num_visited_bw <<
" edges (" << num_visited_fw <<
"," << num_visited_bw <<
") ,final path length: " +
toString(into.size()) +
")\n";
321 this->endQuery(num_visited_bw + num_visited_fw);
329 std::deque<const E*> tmp;
330 const auto* backtrack = meeting.first;
331 while (backtrack != 0) {
332 tmp.push_front((E*) backtrack->edge);
333 backtrack = backtrack->prev;
335 backtrack = meeting.second->prev;
336 while (backtrack != 0) {
337 tmp.push_back((E*) backtrack->edge);
338 backtrack = backtrack->prev;
342 while (!tmp.empty()) {
343 const E* cur = tmp.front();
349 const E* via =
getVia(prev, cur);
376 const E*
getVia(
const E* forwardFrom,
const E* forwardTo)
const {
Computes the shortest path through a contracted network.
const SUMOVehicleClass mySVC
the permissions for which the hierarchy was constructed
static MsgHandler * getWarningInstance()
Returns the instance to add warnings to.
SUMOTime myValidUntil
the validity duration of the current hierarchy (exclusive)
SUMOVehicleClass
Definition of vehicle classes to differ between different lane usage and authority types...
std::vector< typename CHBuilder< E, V >::Connection > ConnectionVector
void buildContractionHierarchy(SUMOTime time, const V *const vehicle)
std::string time2string(SUMOTime t)
void init(const E *const start, const V *const vehicle)
void buildPathFromMeeting(Meeting meeting, std::vector< const E *> &into) const
normal routing methods
bool operator()(const typename BASE::EdgeInfo *nod1, const typename BASE::EdgeInfo *nod2) const
Comparing method.
virtual ~CHRouter()
Destructor.
CHRouter(const std::vector< E *> &edges, bool unbuildIsWarning, typename BASE::Operation operation, const SUMOVehicleClass svc, SUMOTime weightPeriod, bool validatePermissions)
Constructor.
Unidirectional myBackwardSearch
std::vector< typename BASE::EdgeInfo * > myFrontier
the min edge heap
std::vector< typename BASE::EdgeInfo > myEdgeInfos
The container of edge information.
std::string toString(const T &t, std::streamsize accuracy=gPrecision)
const CHBuilder< E, V >::Hierarchy * myHierarchy
BASE::EdgeInfo * getEdgeInfo(const E *const edge)
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 traveltime in the contracted graph...
const E * getVia(const E *forwardFrom, const E *forwardTo) const
const std::vector< E * > & myEdges
all edges with numerical ids
MsgHandler *const myErrorMsgHandler
the handler for routing errors
std::pair< const E *, const E * > ConstEdgePair
StringBijection< SUMOVehicleClass > SumoVehicleClassStrings(sumoVehicleClassStringInitializer, SVC_CUSTOM2, false)
bool found(const E *const edge) const
std::set< const E * > myFound
the set of visited (settled) Edges
const SUMOTime myWeightPeriod
the validity duration of one weight interval
void inform(std::string msg, bool addType=true)
adds a new error to the list
double(* Operation)(const E *const, const V *const, double)
Type of the function that is used to retrieve the edge effort.
const BASE::EdgeInfo * getEdgeInfo(const E *const edge) const
Unidirectional(const std::vector< E *> &edges, bool forward)
Constructor.
Unidirectional myForwardSearch
the unidirectional search queues
virtual SUMOAbstractRouter< E, V > * clone()
bool myAmForward
the role of this search
#define WRITE_MESSAGE(msg)
EdgeInfoByTTComparator myComparator
std::pair< const typename BASE::EdgeInfo *, const typename BASE::EdgeInfo * > Meeting
A meeting point of the two search scopes.
bool step(const std::vector< ConnectionVector > &uplinks, const Unidirectional &otherSearch, double &minTTSeen, Meeting &meeting)
explore on element from the frontier,update minTTSeen and meeting if an EdgeInfo found by the otherSe...
CHBuilder< E, V > * myHierarchyBuilder
CHRouter(const std::vector< E *> &edges, bool unbuildIsWarning, typename BASE::Operation operation, const SUMOVehicleClass svc, SUMOTime weightPeriod, const typename CHBuilder< E, V >::Hierarchy *hierarchy)
Cloning constructor.