support.Flight
Class FullFinder

java.lang.Object
  |
  +--support.Flight.FullFinder
Direct Known Subclasses:
PathFinder

public class FullFinder
extends java.lang.Object

This class maintains the database of flights and handles shortest-path queries.


Field Summary
protected  Dictionary dict_
           
protected  java.lang.Object EDGE
           
protected  Graph g_
           
protected static java.lang.Integer INFINITE
           
protected  java.lang.Object LOCATOR
           
protected  PriorityQueue pq_
           
private  UserInterface ui_
           
 
Constructor Summary
FullFinder()
          The constructor.
 
Method Summary
 AirportSpecs airportSpecs(Vertex v)
          Map from the given vertex to the AirportSpecs for the airport.
 InspectableGraph buildGraph(java.util.Enumeration airports, java.util.Enumeration flights)
          You need to modify this method. Build the graph, given the list of airports and the list of flights.
private  void clear()
          Clear all decorations.
private  int distance(Vertex v)
          Get the length of the shortest path so far to the airport represented by v.
 FlightSpecs flightSpecs(Edge e)
          Map from the given edge to the FlightSpecs for the flight.
 void initializeGraph()
          You need to modify this method. Get the graph (which has already been built) ready for running the algorithm.
 boolean relax(Edge e)
          You need to modify this method. relax the edge.
 java.util.Enumeration runDijkstra(int start, Vertex origin, Vertex destination)
          Run Dijkstra's shortest path algorithm to find the shortest itinerary to get from the origin to the destination.
private  int time(Vertex v)
          Get the earliest time we can get to the airport represented by v.
 Vertex vertex(java.lang.String code)
          Map from the given 3-character string to the vertex which corresponds to that airport.
private  int weight(Edge e)
          Get the weight of the edge.
 
Methods inherited from class java.lang.Object
, clone, equals, finalize, getClass, hashCode, notify, notifyAll, registerNatives, toString, wait, wait, wait
 

Field Detail

dict_

protected Dictionary dict_

g_

protected Graph g_

ui_

private UserInterface ui_

LOCATOR

protected final java.lang.Object LOCATOR

EDGE

protected final java.lang.Object EDGE

INFINITE

protected static final java.lang.Integer INFINITE

pq_

protected PriorityQueue pq_
Constructor Detail

FullFinder

public FullFinder()
The constructor. Takes a UserInterface, mainly for debugging.
See Also:
UserInterface
Method Detail

buildGraph

public InspectableGraph buildGraph(java.util.Enumeration airports,
                                   java.util.Enumeration flights)
You need to modify this method. Build the graph, given the list of airports and the list of flights.

Parameters:
airports - An enumeration of AirportSpecs
flights - An enumeration of FlightSpecs
Returns:
The graph over which to run Dijkstra's later.
See Also:
AirportSpecs, FlightSpecs

vertex

public Vertex vertex(java.lang.String code)
Map from the given 3-character string to the vertex which corresponds to that airport.

airportSpecs

public AirportSpecs airportSpecs(Vertex v)
Map from the given vertex to the AirportSpecs for the airport.

flightSpecs

public FlightSpecs flightSpecs(Edge e)
Map from the given edge to the FlightSpecs for the flight.

initializeGraph

public void initializeGraph()
You need to modify this method. Get the graph (which has already been built) ready for running the algorithm. This involves setting appropriate decorations for all vertices in the graph.

The vertices are all put into the priority queue with infinite time: we know of no path from the origin to that vertex, so it would take us infinitely long to get to that vertex.

You need to keep track of the locator, so that later, when we find a better path, we can change the key in the queue. Use the decorable methods, with key LOCATOR

See Also:
LOCATOR

relax

public boolean relax(Edge e)
You need to modify this method. relax the edge. This means that, if the edge represents a new shortest path to its destination, then we update the destination.

To update the destination, you need to

  1. get the locator for `to' in the priority queue by using the Decorable mechanism;
  2. replace the key of that locator;
  3. set the new incoming edge.

runDijkstra

public java.util.Enumeration runDijkstra(int start,
                                         Vertex origin,
                                         Vertex destination)
Run Dijkstra's shortest path algorithm to find the shortest itinerary to get from the origin to the destination. We leave at time start (in UTC minutes since midnight).

Returns:
an Enumeration of FlightSpecs which tells us the fastest itinerary, null if there is no path.

weight

private int weight(Edge e)
Get the weight of the edge. This takes into account the layover at the airport, the 30-minute minimum connection time, and the flight time. You'll need this in Dijkstra.

distance

private int distance(Vertex v)
Get the length of the shortest path so far to the airport represented by v.

time

private int time(Vertex v)
Get the earliest time we can get to the airport represented by v.

clear

private void clear()
Clear all decorations.