Enterprise

The University of Southern California has a student body of about 40,000 people and a fairly large main campus. Around registration and graduation times, it often happens that parents or future students stop me asking for directions to buildings where they want to go. There are several large maps installed at key points on the campus and map leaflets are available at the Information Booths and are distributed during the orientation sessions. Although these maps are quite detailed, a visitor can be put off by the large number of buildings and, if the distance to the destination is long, people can get lost.

After talking with my colleagues and several students, we came to the conclusion that it would be a good thing to offer our visitors an application they could use to get step-by-step directions within the campus.

Thus the "Campus Directions" idea was born and within two months a pilot installation (with limited functionality and based on a somewhat older map) was available. We extended the idea and came up with an implementation that can cover any university campus or any relatively small area. The setup can be a fun two or three hour work and you get a program that shows step-by-step directions, with lengths and turns ("turn right," "turn left," "go straight") and a map image of the path trace similar to "yahoo maps" or "mapquest."

A sample installation can be seen at http://romania.usc.edu/directions. (To test drive, please send me an e-mail.) Code samples can be downloaded from http://romania.usc.edu/directions/code/index.jsp.

Additional help and a comprehensive list of setup steps can be found at http://romania.usc.edu/directions/help.

Functionality
The application consists of two different modules:

• PixelMapper, a Swing tool used by administrators to set up (initialize) the maps
• The Web Application implemented using JSP, Struts, and custom JSP tag libraries and responsible for showing the directions. It also has "search" functionality that people can use to look up points

To initialize a map, an administrator uses the PixelMapper tool to load the map image (gif, jpeg, or png), and add points and links to it. After all the points have been added and linked, the tool calculates the shortest path and saves that data in a database. The reason why a database is being used is because finding the shortest path in a large set of points tends to take time and because the shortest path between two fixed points is a constant and recalculating a constant value over and over again would be a waste of processing cycles.

There are two types of points and three types of links. A point can be "named," which means it can be the starting point or end point in searches, or it can be a "link point" when it only serves as a connection between named points. In Figure 1, UCC (University Computing Center) and DEN (Norris Dentistry School) are named points whereas the ones along the streets are link points.

A link is the path element between two points (1 and 2). Links can be "bi-directional," "uni-directional 1-2," and "uni-directional 2-1." That means the path between points 1 and 2 can be traversed in either direction (1-2 and 2-1) or in only one direction (1-2 or 2-1.) That way the paths between two points A (e.g., UCC) and B (e.g., DEN) can be different if traversed from A to B rather than if traversed from B to A (as in the case when at least one path element along the way isn't bi-directional.)

After the map has been initialized and the shortest paths calculated, a request for the shortest path between UCC and DEN returns the results shown in Figure 2 and Figure 3.

The application automatically crops the map to show only what's meaningful (in this case the rectangle containing the path). The administrator doesn't enter the lengths. Instead they are computed from the distance in pixels multiplied by a factor that depends on the scale of the map. So the more accurate the map, the more exact the directions.

Theoretical Considerations
To calculate the shortest paths I wrote (yet another) Java implementation of the simple algorithm that the Dutch mathematician Edsger Dijkstra created in 1959. The Internet abounds in samples and applets that demonstrate this algorithm. A piece of well-explained pseudo-code can be found on Wikipedia at http://en.wikipedia.org/wiki/Dijkstra's_algorithm.

I'll attempt to give a simplistic and visually driven description of the algorithm. Suppose we have the graph shown below; let's call the vertices (1,2,...5) points and the edges (1-2, 2-4, 4-5, etc.) links. Since there's no link between points 2 and 3, we'll say the distance is infinite (this is important in our implementation).

If we want to calculate the shortest paths from point 1 (the source) to all the others, let's start with a two-row table like the one shown in Figure 5. Let's fill the cells with the distances we know already (see Figure 5).

The distance from point 1 to itself is 0. We have the distances from 1 to 2 and 3. For the points that aren't linked directly to point 1 we write (for infinity.) Now let's pick the nearest point from 1; that's 2. Compare the distances from 1 to 3, 4, and 5 with the distances from 1 to 3, 4, and 5, but through the point 2. (e.g., d(1,4) > d(1,2) + d(2,4)) If the distance on the left is larger, replace it with the value on the right. In the example above the inequality is true since d(1,4) is infinite (no link). So d(1,4) will take the value d(1,2) + d(2,4) (see Figure 6).

Note that from now on, there's a path between 1 and 4 and that's 1-2-4 (in the general case, it may not be the shortest, though). Repeat for points 3 and 5. (To digress a moment, the shortest distance to point 3 is obvious, since there's a direct link but, in general, when the graph edges represent cost, it may be cheaper to travel 1-2-4-3 than 1-3 directly. However, that's not the case here.) At this point our table should look like Figure 7.

It already contains the shortest paths. But we have an overly zealous algorithm (greedy) so we'll continue by discarding point 2 and again find the closest point to 1 without considering 2. We repeat the steps above until all the points have been discarded. We have just found the shortest paths from point 1 to all the others. (To read the table, just move under the needed point. For example, d(p1,p4)=19.)

In the example above we've found the shortest paths on the graph when the starting point was point 1. To find the shortest paths from each point to all the others, the procedure would have to be enclosed in another loop that iterates through the set of points and fixes a different one as the source each time. However, in our case, not every point in the set has to be considered since the (unnamed) "link points" can't act as the start or end of a path.

Technology and Implementation
The application was written entirely in Java. AWT 2D (the two-dimensional functions of the Abstract Windowing Toolkit) and JAI (Java Advanced Imaging extensions) were used for image processing (like tiling, painting on the map, and rendering.) The administration tool (PixelMapper) was written using Swing components and the Web interface uses JSP/Struts and custom JSP tag libraries. The application has been tested with MySQL 4.1, HyperSonicDB 1.7.2, and Oracle 9i and 10g release 1.

Now, before the application can be used, the map has to be "initialized" using the PixelMapper tool (the significant points added, linked, and the shortest distances calculated and saved into the database). Our graph will actually consist of the points on the map (see Figure 1) and the links between them. The activity diagram is shown in Figure 8.

There are few basic entities that the application uses, some of which are shared by both the PixelMapper tool and the Web application. These types are:

• Point, which represents a point on the map. It has attributes like the coordinates (x, y) on the map, name ("Norris Dental School"), etc. A link point has null value for name. The PointList is a vector of point instances
• OrientedLink, which represents a path element; it's the link between two points. It holds references to the start and end point instances and attributes like name ("McClintock Ave.") and length. OrientedLinkList is a vector of OrientedLink instances.
• PathElement, which contains all the details of a segment of the current path. It has references to the two points and contains the distance and the turn. It's initialized with data from the database. (A path is a list of PathElements.)
• Dijkstra, which is the implementation of the shortest path algorithm.
• Processor, which uses data from the database to create the path image.
• ImageCache, which is an in-memory placeholder for ImageCacheToken instances. The ImageCacheToken holds the bytes of the generated path image plus the step-by-step directions.
• CachePersistence, which is the interface to be implemented by the custom persistences. (FileSystemPersistence, which serializes the content of the cache to the file system, is provided.)

Figure 9 shows the relationships between the main types (class diagram).

The upper half of the image depicts the main classes used by the PixelMapper tool at map initialization, whereas the lower part shows the "model" layer of the Web application. The classes in the gray rectangle are shared by the two parts.

The implementation of the algorithm Dijkstra::calculateShortestPaths produces two double-dimensional arrays (two square matrices) - a pointMatrix and a distanceMatrix. The first array is used to find the shortest path between any two given points in the initial PointList, and the second gives the corresponding distances.

Figure 10 shows the pointMatrix partially populated, but containing enough data to find all the shortest paths when points 1 or 4 are used as the start points (refer to Figure 4.)