Data Structures in JDSL:A Sample Application

A Sample Application

In this section we explore the implementation of a sample application using JDSL. In particular, we show the use of some of the concepts described above, such as the graph and priority queue data structures, locators, decorations, and the template method pattern.

Minimum-Time Flight Itineraries

We consider the problem of calculating a minimum-time flight itinerary between two air- ports. The flight network can be modeled using a weighted directed graph: each vertex of the graph represents an airport, each directed edge represents a flight from the origin airport to the destination airport, and the weight of each directed edge is the duration of the flight. The problem we are considering can be solved by computing a shortest path between two vertices of the directed graph or determining that a path does not exists. To this purpose, we can suitably modify the classical algorithm by Dijkstra [2], which takes as input a graph G with nonnegative edge weights and a distinguished source vertex s, and computes a shortest path from s to any reachable vertex of G. Dijkstra’s algorithm main- tains a priority queue Q of vertices: at any time, the key of a vertex u in the priority queue is the length of the shortest path from s to u thus far. The priority queue is initialized by inserting vertex s with key 0 and all the other vertices with key +∞ (some very large number). The algorithm repeatedly executes the following two steps:

1. Remove a minimum-key vertex u from the priority queue and mark it as finished, since a shortest path from s to u has been found.

2. For each edge e connecting u to an unfinished vertex v, if the path formed by extending a shortest path from s to u with edge e is shorter than the shortest known path from s to v, update the key of v (this operation is known as the relaxation of edge e).

Class IntegerDijkstraTemplate

As seen in Section 43.3.4, JDSL provides an implementation of Dijkstra’s algorithm that follows the template method pattern. The abstract class implementing Dijkstra’s algorithm is jdsl.graph.algo.IntegerDijkstraTemplate (see Figures 43.6–43.8; for brevity, the Javadoc comments present in the library code have been removed). The simplest way to run the algorithm is by calling execute(InspectableGraph,Vertex), which first initializes the var- ious auxiliary data structures with init(g,source) and then repeatedly calls doOneIteration(). Note that the number of times doOneIteration() is called is controlled by should- Continue(). Another possibility, instead of calling execute(InspectableGraph,Vertex), is to call init(InspectableGraph,Vertex) directly and then single-step the algorithm by explicitly calling doOneIteration().

For an efficient implementation of the algorithm, it is important to access a vertex stored

in the priority queue in constant time, whenever its key has to be modified. This is possible through the locator accessors provided by class jdsl.core.ref.Array Heap (see Section 43.3.3). In init(Inspectable Graph,Vertex), each vertex u of the graph is inserted in the priority queue and a locator uLoc for the key/element pair is returned. By calling setLocator(u,uLoc), each vertex u is decorated with its locator uLoc; variable LOCATOR is used as the attribute name. Later, in doOneIteration(), the locator of vertex v is retrieved by calling getLocator(v) in order to access and possibly modify the key of v; we recall that the key of v is the shortest known distance from the source vertex source to v. In addition to its locator in the priority queue, every unfinished vertex v is also decorated with its last relaxed incident edge uv by calling setEdgeToParent(v,uv); variable EDGE TO PARENT is used as the attribute name, in this case. When a vertex is finished, this decoration stores the edge to the parent in the shortest path tree, and can be retrieved with getEdgeToParent(Vertex).

Methods runUntil() and doOneIteration() are declared final and thus cannot be overridden. Following the template method pattern, they call some methods, namely, shouldContinue(), vertexNotReachable(Vertex), shortestPathFound(Vertex,int), and edgeRelaxed(Vertex,int,Edge, int,Vertex,int), that may be overridden in a subclass for special applications. For each vertex u of the graph, either vertexNotReachable(u) or shortestPathFound(u,uDist) is called exactly once, when u is removed from the priority queue and marked as finished. In particular, short- estPathFound(u,uDist) decorates u with uDist, the shortest distance from source ; variable DISTANCE is used as the attribute name. Method edgeRelaxed(u,uDist,uv,uvWeight,v,vDist) is called every time an edge uv from a finished vertex u to an unfinished vertex v is examined. The only method whose implementation must be provided by a subclass is abstract method weight(Edge), which returns the weight of an edge. Other important methods are isFinished(Vertex), which returns whether a given vertex is marked as finished, and distance(Vertex), which returns the shortest distance from source to a given finished vertex.

Class IntegerDijkstraPathfinder

JDSL also provides a specialization of Dijkstra’s algorithm to the problem of finding a shortest path between two vertices of a graph. This algorithm is implemented in abstract class jdsl.graph.algo.Integer Dijkstra Pathfinder (see Figure 43.9; for brevity, the Javadoc comments present in the library code have been removed), which extends IntegerDijkstraTemplate. The algorithm is run by calling execute(InspectableGraph,Vertex,Vertex). The execution of Dijkstra’s algorithm is stopped as soon as the destination vertex is finished. To this purpose, shouldContinue() is overridden to return true only if the destination vertex has not been finished yet. Additional methods are provided in IntegerDijkstraPathfinder to test, after the

execution of the algorithm, whether a path from the source vertex to the destination vertex exists (pathExists()), and, in this case, to return it (reportPath()).

Class FlightDijkstra

Our application for computing a minimum-time flight itinerary between two airports can be implemented as a specialization of IntegerDijkstraPathfinder. The distance of each vertex

represents, in this case, the time elapsed from the beginning of the travel to the arrival at the airport represented by that vertex. In Figure 43.10 we show the code of class FlightDijkstra; this class is part of the tutorial∗∗ distributed with JDSL. All it takes to implement our

application is to override method incident Edges(), so that only the outgoing edges of a finished vertex are examined, and to define method weight(Edge). As noted before, the weighted graph representing the flight network is a directed graph. Each edge stores, as an element, an instance of auxiliaryclass FlightSpecs providing the departure time and the duration of the corresponding flight. Note that the weights of the edges are not determined before the execution of the algorithm, but rather depend on the computed shortest distance

between the source vertex and the origin of each edge. Namely, they are obtained by adding the duration of the flight corresponding to the edge and the connecting time at

the origin airport for that flight.†† Method Time Table.diff(int,int) simply computes the difference between its two arguments modulo 24 hours. The algorithm is run by calling execute(Inspectable Graph,Vertex,Vertex,int), where the fourth argument is the earliest time the passenger can begin traveling.

As we can see from this example, the availability in JDSL of a set of carefully designed and extensible data structures and algorithms makes it possible to implement moderately com- plex applications with a small amount of code, thus dramatically reducing the development time.

Acknowledgments

We would like to thank all the members of the JDSL Team for their fundamental role in the design, implementation, and testing of JDSL. It has been a great experience and a real pleasure working together.

This work was supported in part by the National Science Foundation under grants CCR- 0098068 and DUE-0231202.