|
|||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
| SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | ||||||||
java.lang.Object | +--support.Flight.FullFinder
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 |
|
| Field Detail |
protected Dictionary dict_
protected Graph g_
private UserInterface ui_
protected final java.lang.Object LOCATOR
protected final java.lang.Object EDGE
protected static final java.lang.Integer INFINITE
protected PriorityQueue pq_
| Constructor Detail |
public FullFinder()
UserInterface| Method Detail |
public InspectableGraph buildGraph(java.util.Enumeration airports,
java.util.Enumeration flights)
airports - An enumeration of AirportSpecsflights - An enumeration of FlightSpecsAirportSpecs,
FlightSpecspublic Vertex vertex(java.lang.String code)
public AirportSpecs airportSpecs(Vertex v)
public FlightSpecs flightSpecs(Edge e)
public void initializeGraph()
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
LOCATORpublic boolean relax(Edge e)
To update the destination, you need to
public java.util.Enumeration runDijkstra(int start,
Vertex origin,
Vertex destination)
private int weight(Edge e)
private int distance(Vertex v)
private int time(Vertex v)
private void clear()
|
|||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
| SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | ||||||||