\( \def\bold#1{\bf #1} \newcommand{\d}{\mathrm{d}} \)
label algorithm to solve multicriteria shortes path problem More...
#include <strongcalc.h>
Public Slots | |
void | stop_calculations () |
sets STRONGcalc::calcstopped and stops algorithm in next iteration | |
Signals | |
void | finished (int succesful) |
returns succes if a track was extracted from the STRONG network | |
void | refresh_progress (int step) |
emitted if iteration step has finished | |
Public Member Functions | |
STRONGcalc (OSM *o, KOO *s, KOO *e, char max, char min, STRONGsetting *hs, Track ***trck, int *N, bool Hmonly) | |
STRONG calculation. | |
STRONGcalc (OSM *o, int N, char *filename, Track ***results) | |
save STRONG calculation | |
STRONGcalc (OSM *o, int *N, char *filename, Track ***results) | |
load STRONG calculation | |
void | run () |
void | exit () |
Private Member Functions | |
template<class T > | |
void | calc (FibunacciHeap< T > **f) |
core function of the algorithm More... | |
void | setSTRONG (KOO *k) |
short | traceback (STRONG *s, Neighbour *n) |
reconstructs track and checks if Neighbour n was already used More... | |
void | STRONG_to_trck (int i) |
void | extract_neighbourlist (STRONG *s, STRONG *e, Neighbour ***nl, long int *nc) |
reconstructs link between start STRONG and end STRONG More... | |
int | extract_STRONGPlus_restriciton (Neighbour *n) |
checks if STRONG can expand concerning restrictions | |
int | extract_STRONGClimb_restriciton (Neighbour *n) |
checks if STRONG can expand concerning restrictions | |
void | load_STRONG () |
executes the loading of a STRONG network from file filename | |
void | save_STRONG () |
executes the save of a STRONG network to file filename | |
void | load_crossdata (FILE *f) |
low level load routine of load_STRONG | |
void | save_crossdata (KOO *k, FILE *f) |
low level save routine of save_STRONG | |
void | init_Strong () |
void | init_StrongPlus () |
void | init_StrongClimb () |
void | init_AreaStrong (KOO *k) |
void | init_AreaStrongPlus (KOO *k) |
void | init_AreaStrongClimb (KOO *k) |
int | index_STRONG (STRONGfib *t, Neighbour *n) |
int | index_STRONG (STRONGPlusfib *t, Neighbour *n) |
int | index_STRONG (STRONGClimbfib *t, Neighbour *n) |
void | store_STRONG (STRONGfib *t, Neighbour *n, int si, int i) |
void | store_STRONG (STRONGPlusfib *t, Neighbour *n, int si, int i) |
void | store_STRONG (STRONGClimbfib *t, Neighbour *n, int si, int i) |
Private Attributes | |
int | counter |
RunMode | runmode |
type of STRONGcalc to be executed | |
OSM * | o |
dataset to operate on | |
char | filename [999] |
for save and load | |
KOO * | s |
start point | |
KOO * | e |
end point | |
char | max |
char | min |
restrictions on Neighbour Way type | |
STRONGsetting * | hs |
major settings of the calculation | |
Track *** | trck |
intermediate results of iterations | |
int | N |
int * | Nout |
int | calcstopped |
float | radius |
data ellipse radius calculated from STRONGsetting and start/ end point | |
short | foundSTRONG |
if 1 return succes when finished | |
Neighbour * | dummy |
double * | mind |
STRONG ** | mindSTRONG |
end point array of shortest track at specific strong index | |
FibunacciHeap< STRONGfib > ** | f |
FibunacciHeap< STRONGPlusfib > ** | fplus |
FibunacciHeap< STRONGClimbfib > ** | fclimb |
float | hm |
float | hmup |
float | hmdown |
float | Psum |
float | dP |
label algorithm to solve multicriteria shortes path problem
This thread is designed to calculated the shortes route at given altitude difference. According to the original idea to ride the shortest route with 10000 Hm, the solution is call "$STRONG", and everything, which is related to this calculation will by named alike. The Label in that case is a STRONG struct, it shows where the track, which passes the owning cross, comes from, i.g. from which STRONG struct. Every STRONG struct represents an interval of Hm to make the mathematical problem solvable at all. Every crossdata bears an array of STRONG structs and intervals respectivly. The index of such an array, representing a Hm interval, is called strong index. In Principle the algorithm works like Dijkstra, with the important difference, that an ariving track will compare itself with tracks of similiar Hm having passed the cross before, i.g. tracks which passed the STRONG struct with the related striong index. In Dijkstra the distance only counts and tracks in only one STRONG struct are of importance. For further information refer to multicriteria shortes path problem and label algorithm.
Definition at line 28 of file strongcalc.h.
|
private |
core function of the algorithm
takes a STRONG struct from the lowest Hm priority queue. This queue is a FibunacciHeap. The extracted STRONG is activ and has the shortes distance. It will be expanded by calc() and compare itself to existing aspirants in the related STRONG structs of the neighbouring crossdata. If it has shorter distance or finds a free STRONG struct it will be kept active and stored in the FibunacciHeap.
calc() runs until all FibunacciHeap are empty or calcstopped was set to one.
Definition at line 83 of file strongcalc.cpp.
calculates related Hm intervall from Hm, ig.g strong index
Definition at line 398 of file strongcalc.cpp.
|
private |
calculates related Hm intervall from Hm, ig.g strong index
Definition at line 401 of file strongcalc.cpp.
|
private |
calculates related Hm intervall from Hm, ig.g strong index
Definition at line 412 of file strongcalc.cpp.
|
private |
prepares the class for the calc() function
Calcs maximum strong index, allocates STRONG arrays in all crossdata, which lie in the specified elliptical area. Allocates the FibunacciHeap array and fills it with zero indexed STRONG of all crossdata, which lie within the data area. This serves as a STRONGcalc with undefined start point.
Definition at line 284 of file strongcalc.cpp.
|
private |
prepares the class for the calc() function
Calcs maximum strong index, allocates STRONG arrays in all crossdata, which lie in the specified elliptical area. Allocates the FibunacciHeap array and fills it with zero indexed STRONG of all crossdata, which lie within the data area. This serves as a STRONGcalc with undefined start point.
Definition at line 316 of file strongcalc.cpp.
|
private |
prepares the class for the calc() function
Calcs maximum strong index, allocates STRONG arrays in all crossdata, which lie in the specified elliptical area. Allocates the FibunacciHeap array and fills it with zero indexed STRONG of all crossdata, which lie within the data area. This serves as a STRONGcalc with undefined start point.
Definition at line 299 of file strongcalc.cpp.
|
private |
prepares the class for the calc() function
Calcs maximum strong index, allocates STRONG arrays in all crossdata, which lie in the specified elliptical area. Allocates the FibunacciHeap array and fills it with one Element, namely the startpoint.
Definition at line 161 of file strongcalc.cpp.
|
private |
prepares the class for the calc() function
Calcs maximum strong index, allocates STRONG arrays in all crossdata, which lie in the specified elliptical area. Allocates the FibunacciHeap array and fills it with one Element, namely the startpoint.
Definition at line 241 of file strongcalc.cpp.
|
private |
prepares the class for the calc() function
Calcs maximum strong index, allocates STRONG arrays in all crossdata, which lie in the specified elliptical area. Allocates the FibunacciHeap array and fills it with one Element, namely the startpoint.
Definition at line 200 of file strongcalc.cpp.
|
private |
allocates STRONG arrays
allocates STRONG arrays for all crossdata lying within the the specified data ellipse. This ellipse is defined by start and endpoint as focal point and the maximum distance from these points, stored in radius variable.
Definition at line 336 of file strongcalc.cpp.
stores succesfully expanded STRONG in the FibunacciHeap
Definition at line 563 of file strongcalc.cpp.
|
private |
stores succesfully expanded STRONG in the FibunacciHeap
Definition at line 573 of file strongcalc.cpp.
|
private |
stores succesfully expanded STRONG in the FibunacciHeap
Definition at line 584 of file strongcalc.cpp.
|
private |
reconstructs strong track with strong index i
This is tracing back from end point or if no end point was stated then the point which was reached with least distance.
Definition at line 356 of file strongcalc.cpp.
reconstructs track and checks if Neighbour n was already used
If the Neighbour was found, zero is returned, else one
Definition at line 385 of file strongcalc.cpp.
|
private |
data of the currently traded STRONG struct
Definition at line 153 of file strongcalc.h.
|
private |
bumbper to mark root if STRONG net
Definition at line 141 of file strongcalc.h.
|
private |
priority queue of the calc() routine
Definition at line 144 of file strongcalc.h.
|
private |
priority queue of the calc() routine
Definition at line 146 of file strongcalc.h.
|
private |
priority queue of the calc() routine
Definition at line 145 of file strongcalc.h.
|
private |
data of the currently traded STRONG struct
Definition at line 153 of file strongcalc.h.
|
private |
data of the currently traded STRONG struct
Definition at line 153 of file strongcalc.h.
|
private |
data of the currently traded STRONG struct
Definition at line 153 of file strongcalc.h.
|
private |
minimum distance for strong index
Definition at line 148 of file strongcalc.h.
|
private |
data of the currently traded STRONG struct
Definition at line 153 of file strongcalc.h.