Computational Aspects: How Landmarks Can Be Observed, Stored, and Analysed - Landmarks: GIScience for Intelligent Services - page 159

Algorithm 5.4: Algorithm for reconstructing the simplest instruction path,
after [ 39 ] .
Data : G D .V; E/: a connected, simple, directed graph; o 2 E: the origin edge; t 2 E:the
target (destination) edge; d W E I ! E [f;g: the decision function;
p W E ! E I : the predecessor function (generated by Algorithm 5.3 ) .
Result : A sequence (word) P of edges corresponding to the optimal path and a sequence
(word) L of labels corresponding to the best sequence of instructions.
1 P ; /* Initialize the variables. */

2 L ;
3 T ;
4 e t ; /* Set e to the target (start from the back). */

5 while e ¤ o do
6 p.e/ .e p ;i/; /* Retrieve the predecessor of e */

7 L i CL; /* Add to L the instruction to get from e p to e .*/

e 0 e p ; 8

T e 0 ; 9 /* The sequence of all edges between e p and e .*/

while .e 0 ;e/62 E do 10

e 00 d.e 0 ;i/; /* The edge reachable from e 0 via label i .*/ 11

T T Ce 00 ; /* e 00 is between e 0 and e .*/ 12

e 0 e 00 ; 13

14 P T CP ; /* Add T to the path. */

15 e e p ; /* Continue reconstruction from e p .*/

Algorithms 5.2 and 5.3 establish the costs to reach specific edges (or vertices)
in the underlying graph. They do not actually return a path to this destination edge.
This requires another reconstruction algorithm, which starts from the destination
and walks backwards through the graph until it reaches the origin, assembling
the path along the way. Algorithm 5.4 exemplifies such an approach for the
simplest instructions path. Using an algebraic language notation, where E and I
form alphabets, the algorithm constructs a path by iteratively prepending letters
to an initially empty word. Retrieval of the instructions that need to be followed
simply requires direct backtracking through the predecessor list (line 7), while
reconstructing the edges to follow requires an additional loop to retrieve those edges
between subsumed instructions (lines 8-15).

5.4 A Comparison of Landmark Identification

and Landmark Integration Approaches

Richter [ 38 ] , attempting to identify why landmarks have not been taken up in
commercial navigation services so far, categorized several of the approaches
presented in Sects. 5.2 and 5.3 with respect to different aspects. This categorization
is summarized in Table 5.7 . Most of the data mining approaches of Sect. 5.2.2 are
not discussed here since they do not explicitly target landmarks of the scale and kind
addressed in this topic.