The Data Structures Library in Java

JDSL Tutorial

Previous Lesson
Table of Contents


Lesson 7: Flights

In this lesson we look at how graphs are implemented in JDSL.  Our sample application calculates minimum-time flight itineraries between two cities.

New concepts covered:


The definitions of the classes for this application are contained in four packages:

To run this demo program, execute the following steps: Choose the size of the flight graph you want to use, then follow the directions to calculate an itinerary.


In this lesson, we look at how the JDSL implements Graphs,  a non-linear PositionalContainer type. (Lesson 6 looks at trees, another non-linear positional container type.)  A graph consists of a collection of vertices connected by edges.   Each edge defines a relationship between two vertices.  Edges are either directed from one vertex to the other, or are undirected.

For a complete discussion of graphs, see the textbook.

Both the jdsl.graph.api.Vertex and jdsl.graph.api.Edge extend the Position interface.  Consequently, each has an associated element object, and can be decorated with other objects (see Lesson 6 ).

In our application, the Graph describes a network of flights.  A Vertex of the Graph represents an airport, and each Edge represents a flight.  Edges are directed from the origin airport to the destination airport.  The graph is instantiated in the support.gui.FlightPanel class.

      private Graph graph_ = new IncidenceListGraph();
The jdsl.graph.api.Graph interface is implemented by the jdsl.graph.ref.IncidenceListGraph class.  In an IncidenceListGraph, each vertex keeps a list of its outgoing edges.

The Graph interface contains methods for inserting Vertexes  and Edges into the Graph.

      Vertex v = graph.insertVertex(airport);
The insertVertex(.) method inserts a new vertex into the graph.  The airport object is of class support.AirportSpecs and contains descriptive information about the airport.
      graph.insertDirectedEdge(fromAirport, toAirport, flight);
The insertDirectedEdge(.) method inserts a directed edge from Vertex object fromAirport to Vertex object toAirport.   The flight object is of class support.FlightSpecs and contains descriptive information about the flight.

The shortest-time flight itinerary is calculated using Dijkstra's algorithm that finds a shortest path from a given start Vertex s to all vertices reachable from s.  Dijkstra's algorithm keeps a priority queue of vertices (see Lesson 4 for more about priority queues).  The key for each Vertex v in the priority queue is the length of the shortest known path from s to v.  The priority queue is initialized by inserting Vertex s with key 0 and all the other vertices with key INFINITY (some very large number).

The algorithm runs as follows:

        while( Q is not empty ) {
                remove a minimum weight vertex v from Q
                mark v as having the shortest path
                relax v
        }
Where relaxing a Vertex v consists of:

            for ( each vertex w connected by an edge e outgoing from v)
                  if ( the path formed by extending a shortest path to v with edge e is shorter than
                                     the best known path to w )
                                 update the best known distance to w

This algorithm is implemented by the jdsl.graph.algo.IntegerDijkstraTemplate and the jdsl.graph.algo.IntegerDijkstraPathfinder classes.  The IntegerDijkstraTemplate class allows implementor fine control over the algorithm.  It uses the template-method pattern, in which the essential action of an algorithm (the code that cannot change if the algorithm is to be meaningful) is separated from the details necessary to adapt the essential algorithm to the application at hand. The essential code calls functions that supply the necessary application specific details. A user can override the function definitions but cannot change the essential code. The IntegerDijkstraPathfinder class is simpler, designed for the common case where you just want a shortest path.

public class FlightDijkstra extends jdsl.graph.algo.IntegerDijkstraPathfinder {
   private int startTime_;
We extend the IntegerDijkstraPathfinder class.   The startTime_ variable keeps the time the passenger wants to begin traveling.  This is important, because the shortest travel time itinerary may be different depending on the time of day.

We need to override the weight(.) method that returns the weight of an edge.

  protected int weight (Edge e) {
    FlightSpecs eFS = (FlightSpecs)e.element();
    int waitTime = TimeTable.diff(eFS.departureTime(),
                                  startTime_ + distance(G.origin(e)));
    return waitTime + eFS.flightDuration();
  }


For our application, the weight of an edge represents the layover time combined with the duration of the flight represented by the Edge.  We compute the weight function for Edge e in the following manner:

This method uses one method defined in the class IntegerDijkstraTemplate: We also overload the execute(.) method, that computes the Edges of the shortest path.   You can call execute(InspectableGraph, Vertex, Vertex) multiple times for pairs of vertices from the graph.  We overload the method to include the startTime needed for our shortest path calculations.
  public void execute(InspectableGraph g, Vertex source, Vertex dest, int startTime) 
   throws InvalidVertexException {
    startTime_ = startTime;
    super.execute(g,source,dest);
  }

To obtain the last computed shortest path, we call the reportPath() method of IntegerDijkstraPathfinder. It returns the edges, in order, of the shortest path between two vertices last queried by the execute method above.

This is the final lesson in the tutorial.


Previous Lesson
Table of Contents
Problems, comments?

Last modified: Mon Sep 27 13:40:46 CEST 2004