44 template<
class E,
class C>
60 if (a->traveltime == b->traveltime) {
61 return a->edge->getNumericalID() > b->edge->getNumericalID();
63 return a->traveltime > b->traveltime;
83 for (
typename std::vector<E*>::iterator i =
myFound.begin(); i !=
myFound.end(); i++) {
96 start->traveltime = 0;
98 start->permissions = start->edge->getPermissions();
108 for (
typename CHConnections::iterator it = min->followers.begin(); it != min->followers.end(); it++) {
110 E* follower = con.target;
111 if (follower == excluded) {
114 const double traveltime = min->traveltime + con.cost;
115 const double oldTraveltime = follower->traveltime;
116 if (!follower->visited && traveltime < oldTraveltime) {
117 follower->traveltime = traveltime;
118 follower->depth = min->depth + 1;
119 follower->permissions = (min->permissions & con.permissions);
120 if (oldTraveltime == std::numeric_limits<double>::max()) {
153 const C*
const aInfo = it->first;
154 const C*
const fInfo = it->second;
156 aInfo->target, fInfo->target, excluded, (aInfo->permissions & fInfo->permissions));
157 const double viaCost = aInfo->cost + fInfo->cost;
158 if (viaCost < bestWitness) {
171 start->traveltime = 0;
178 return dest->traveltime;
185 for (
typename CHConnections::iterator it = min->followers.begin(); it != min->followers.end(); it++) {
187 E* follower = con.target;
188 if (follower == excluded) {
191 if ((con.permissions & permissions) != permissions) {
194 const double traveltime = min->traveltime + con.cost;
195 const double oldTraveltime = follower->traveltime;
196 if (!follower->visited && traveltime < oldTraveltime) {
197 follower->traveltime = traveltime;
198 follower->depth = min->depth + 1;
199 follower->permissions = (min->permissions & con.permissions);
200 if (oldTraveltime == std::numeric_limits<double>::max()) {
212 return dest->traveltime;
218 std::cout <<
"computed SPT from '" << start->edge->getID() <<
"' (excluding " << excluded->edge->getID() <<
") with " <<
myFound.size() <<
" edges\n";
219 for (
typename std::vector<E*>::iterator it = vec.begin(); it != vec.end(); it++) {
221 std::cout <<
"(" << e->edge->getID() <<
"," << e->traveltime <<
") ";
double dijkstraTT(E *start, E *dest, const E *excluded, SVCPermissions permissions)
SPTree(int maxDepth, bool validatePermissions)
Constructor.
int SVCPermissions
bitset where each bit declares whether a certain SVC may use this edge/lane
EdgeByTTComparator myCmp
comparator for search queue
CHConnectionPairs myNeededShortcuts
vector of needed shortcuts after validation
std::vector< CHConnectionPair > CHConnectionPairs
void registerForValidation(const C *aInfo, const C *fInfo)
save source/target pair for later validation
std::vector< E * > myFound
the list of visited edges (used when resetting)
const CHConnectionPairs & getNeededShortcuts(const E *excluded)
std::pair< const C *, const C * > CHConnectionPair
std::vector< E * > myFrontier
the min edge heap
void debugPrintVector(std::vector< E *> &vec, E *start, const E *excluded)
bool myValidatePermissions
whether permissions should be validated
std::vector< C > CHConnections
void rebuildFrom(E *start, const E *excluded)
build a shortest path tree from start to a depth of myMaxdepth. The given edge is excluded from this ...
CHConnectionPairs myShortcutsToValidate
vector of needed shortcuts after validation
bool validatePermissions()
whether permissions should be validated;
bool operator()(const E *a, const E *b) const
Comparing method.
int myMaxDepth
maximum search depth