For example, if we wanted to find the shortest path between points 1 and 5, we'd fix the first row in the matrix (row 0), which corresponds to point 1 when used as starting point, and start from the fifth column (0,4), going left (the matrix is always populated with the points in reverse order so we start with point 5 and go back until we reach point 1).

At this point our path contains only one point (point 5). In the (0,4) cell we find a reference to point 4 (follow the arrows). We add point 4 to the path (point 5 -> point 4). Now we check the cell corresponding to point 4 (0,3) and find a reference to point 2. We add point 2 to the path, which now looks like point 5 -> point 4 -> point 2. Again, we read the content of the cell that corresponds to point 2 (0,1) and find that it references point 1. We add point 1 to the list, which now looks like (point 5 -> point 4 -> point 2 -> point 1) and stop, since point 1 was the end of the desired path.

Remember the path is in reverse order so we'll have to traverse it backwards and return 1 - 2 - 4 - 5 (see Figure 10).

The code in Listing 1 is an extract from Dijkstra::calculateShortestPaths function (see Dijkstra in the code section) and it shows the Greedy loop that finds the shortest distances from one fixed point to all the others. It's enclosed in an outer loop that fixes another named point (startVertex) in each iteration. It's slightly modified from the original version and edited for clarity (comments and variable declaration in the loops. distanceMatrix is a long[][] and pointMatrix is a Point[][]).

Dijkstra::retrievePath is the function that returns the paths given any two named points in the initial set. It uses both pointMatrix and distanceMatrix and stops when the distance between the two current adjacent points is 0 (meaning the two points are, in fact, references to the same point like cell (0,0) in the table above).

After calculating the shortest paths, the results are saved in the database. There are four tables to hold the data:

• POINT, which contains all the defined points. The PixelMapper tool uses this table to load the points on the map at initializa-tion. It's also used by the "search" function.
• LINK, which holds all the defined links. Like the table above, the PixelMapper tool uses this one to paint the links created in a previous session.
• SHORTEST_PATH, which is populated after running Dijkstra.calculateShortestPaths. It only contains a "path id" and the ids of the start and end points.
• SHORTEST_PATH_ELEMENT, the table that is also populated after the algorithm runs. It holds all the path elements, that is, the links between the consecutive points on a path. It has lengths, turns, cardinal points, etc. From this table come the step-by-step directions seen in Figure 3.

I had to consider every two adjacent links (or path elements) as vectors in the plane, take the cross-product and use the right-hand rule to find whether the result pointed up or down and, as a function of that, see if the turn was to the right or left. For collinear vectors, I used their direction (if same direction then the "turn" would be a "go straight" and if the opposite direction the turn would be a "U-turn"). (See PathUtil::getTurn.)

Strictly speaking, oriented links would have been unnecessary if the application only gave "walking directions." But it can be set up to show driving directions too. So having "one-way" path elements begins to make sense.

The Web application has been implemented around the MVC (model-view-controller) paradigm using Struts. When a user asks for directions, the database is queried, and the data access layer returns the path between the start and the end points with all the details required.

To further improve the response time, the application implements a caching mechanism. After a path is generated as the result of a user request, an ImageCacheToken is created and added to the in-memory cache. The ImageCacheToken contains the path image as a stream of bytes (see Figure 2) and the list with the step-by-step directions (see Figure 3). Retrieving from the cache is almost instantaneous.

The coordinates of all the points involved are passed to the Processor::tracePath. This function draws on the map, creates the step-by-step directions, and feeds all these to a new ImageCacheToken instance.

While points are added to the map(Processor::tracePath), the "visible area" is permanently enlarged to accommodate all the points that comprise that path. A "band" (of configurable size) is then added around the cropped image. (See the Processor source in the code section.)

In fact, the ImageCacheToken contains two images (as byte arrays.) If the start and end points are far apart, the resulting image can be large. A scaled-down image is shown first with a "show full image" button painted on it (in the lower-left corner). The maximum size of the image before it gets scaled down is a configurable parameter and can be set by the administrator.

After the ImageCacheToken is instantiated and populated with data for a specific path, it's added to the ImageCache instance, so next time the system gets a request for the same directions, the same ImageCacheToken is returned without querying the database or processing the image map. If the age of the ImageCacheToken goes over a configurable limit, the instance becomes available for persistence.

Once an ImageCacheToken is obtained (either from cache, persistence, or newly created), the image is sent to the Web application as a byte array.

However, since the application can potentially be used by tens of thousands of people, there's a good chance that the servlet container will throw an OutOfMemoryException after a large number of path images have been generated and cached in-memory. To prevent that from happening, a persistence layer has been added. A thread periodically checks the in-memory cache and moves the "expired" ImageCacheToken instances to the persistence implementation. An ImageCacheToken has a configu-rable attribute (age) that tells the persistence thread whether it can be persisted or not.

Once it's been determined that an ImageCacheToken instance is available for persistence, an ImageCacheTokenSerializable type is instantiated and data from the original ImageCacheToken is copied over. The only difference between the two types is that ImageCacheTokenSerializable holds the image bytes as Byte64 encoded strings, which are serializable (java.io.ByteArrayOutputStream type is not serializable). Then the new instance is passed to the CachePersistence by calling addToPersistence.

Out-of-the-box, the application comes with a file system implementation of the persistence layer (FileSystemPersistence) that serializes the ImageCacheToken instances and writes them off to the file system (using the java.io.ObjectOutputStream::writeObject). A set of interfaces and classes has been exposed that can be used to produce custom implementations for the cache persistence. JMS or DB cache persistence implementations shouldn't be too hard to write.

Conclusion
The application could be used by universities or cities to offer visitors directions to their points of interest. Cities may also want to make their downtown maps more interactive and give people an easy way to find their way to buildings or attractions.

An application such as this could be installed in kiosks equipped with touch-screens, where people could search for points of interest and print out step-by-step directions. It could be enhanced to "link" maps together and show directions between different floors of a building or between different campuses. Another improvement could be showing "points of interest" along a path such as bookstores, restaurants, and coffee shops.

References

1. Knuth, Donald, The Art of Computer Programming (vol 1, 3rd edition). Addison-Wesley.
2. Andonie R., Garbacea I., Funda-mental Algorithms (a C++ perspective). Libris, 1995.
3. Wikipedia, www.wikipedia.com