35template<
class E,
class C>
51 if (a->traveltime == b->traveltime) {
52 return a->edge->getNumericalID() > b->edge->getNumericalID();
54 return a->traveltime > b->traveltime;
74 for (
typename std::vector<E*>::iterator i =
myFound.begin(); i !=
myFound.end(); i++) {
87 start->traveltime = 0;
89 start->permissions = start->edge->getPermissions();
99 for (
typename CHConnections::iterator it = min->followers.begin(); it != min->followers.end(); it++) {
101 E* follower = con.target;
102 if (follower == excluded) {
105 const double traveltime = min->traveltime + con.cost;
106 const double oldTraveltime = follower->traveltime;
107 if (!follower->visited && traveltime < oldTraveltime) {
108 follower->traveltime = traveltime;
109 follower->depth = min->depth + 1;
110 follower->permissions = (min->permissions & con.permissions);
111 if (oldTraveltime == std::numeric_limits<double>::max()) {
144 const C*
const aInfo = it->first;
145 const C*
const fInfo = it->second;
147 aInfo->target, fInfo->target, excluded, (aInfo->permissions & fInfo->permissions));
148 const double viaCost = aInfo->cost + fInfo->cost;
149 if (viaCost < bestWitness) {
162 start->traveltime = 0;
169 return dest->traveltime;
176 for (
typename CHConnections::iterator it = min->followers.begin(); it != min->followers.end(); it++) {
178 E* follower = con.target;
179 if (follower == excluded) {
182 if ((con.permissions & permissions) != permissions) {
185 const double traveltime = min->traveltime + con.cost;
186 const double oldTraveltime = follower->traveltime;
187 if (!follower->visited && traveltime < oldTraveltime) {
188 follower->traveltime = traveltime;
189 follower->depth = min->depth + 1;
190 follower->permissions = (min->permissions & con.permissions);
191 if (oldTraveltime == std::numeric_limits<double>::max()) {
203 return dest->traveltime;
209 std::cout <<
"computed SPT from '" << start->edge->getID() <<
"' (excluding " << excluded->edge->getID() <<
") with " <<
myFound.size() <<
" edges\n";
210 for (
typename std::vector<E*>::iterator it = vec.begin(); it != vec.end(); it++) {
212 std::cout <<
"(" << e->edge->getID() <<
"," << e->traveltime <<
") ";
long long int SVCPermissions
bitset where each bit declares whether a certain SVC may use this edge/lane
bool operator()(const E *a, const E *b) const
Comparing method.
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 ...
void debugPrintVector(std::vector< E * > &vec, E *start, const E *excluded)
std::vector< E * > myFrontier
the min edge heap
std::pair< const C *, const C * > CHConnectionPair
CHConnectionPairs myNeededShortcuts
vector of needed shortcuts after validation
std::vector< C > CHConnections
std::vector< CHConnectionPair > CHConnectionPairs
std::vector< E * > myFound
the list of visited edges (used when resetting)
bool myValidatePermissions
whether permissions should be validated
CHConnectionPairs myShortcutsToValidate
vector of needed shortcuts after validation
bool validatePermissions()
whether permissions should be validated;
const CHConnectionPairs & getNeededShortcuts(const E *excluded)
SPTree(int maxDepth, bool validatePermissions)
Constructor.
void registerForValidation(const C *aInfo, const C *fInfo)
save source/target pair for later validation
int myMaxDepth
maximum search depth
EdgeByTTComparator myCmp
comparator for search queue
double dijkstraTT(E *start, E *dest, const E *excluded, SVCPermissions permissions)