Making Maps Navigable - Programming GPS and OpenStreetMap Applications with Java - page 118

Figure8.3. The graph of the network connections between Hamburg, Berlin and
Hannover.
graph to identify the connected neighbor nodes. The links are abstracted
to edges of the graph.
A graph is the essence of a (road) network and the heart of a navigation
system (see Figure 8.3). If the network is not closed a system could run hot
trying to find a way out of a neighborhood. If bridges get lost during the
compilation process the transportation network is reduced to the borders
of ancient times, when rivers marked borders.
createMapGraph() . The graph for the NavigableMap is created with the
method createMapGraph() .
With the gathered information, every Position of the map can be looked
up via the nodeID in the nodeMap . Nevertheless, the collection has to some-
how browse over a number of nodes to identify one, while an array is
organized in ordinal numbers to access the elements directly. For the sake
of performance and handling, the IDs are reorganized in a sequential order.
A map that associates old, random to new, sequential IDs
Map<oldID,newID> newNodeIDs = new HashMap<Int. ,Int.>();
is used to update the destination list's IDs and to create a new unmodiable
nodeMap with sequential keys.
Next, one empty set of Link is is created for each nodeID:
Set<Link>[] nodeToLinks = new HashSet[newNodeIDs.size()];
for (int nd = 0; nd < nodeToLinks.length; nd++)
nodeToLinks[nd] = new HashSet<Link>();
Each set is filled with each link connecting to the node; from and to are
relative and exchangeable in this context and the nodeIDs are updated to