In this part of the assignment you will implement a graph representation to be used later in Part II.
The assignment has these files provided:
You are to add code to MyGraph.java that implements the Graph.java interface. Graph.java makes use of the Vertex.java and Edge.java classes provided. You are free to add things to Vertex.java, Edge.java, or MyGraph.java, just don’t remove anything that is currently there. You should not modify Graph.java. Your code should be efficient and strive for the minimal big-Oh possible for the requested operations. Although a simple list of vertices and edges is sufficient to store all information about a graph, it may not be the most efficient method for answering questions about the graph (like those described in part II.)
Grading (please note anything which fails these functions might lead points reduction):
[2 pts] public Collection edges() [2 pts] public Collection vertices() [8 pts] public Collection adjacentVertices(Vertex v) [8 pts] public int isAdjacent(Vertex v, Vertex w)
In this part of the assignment, you will use the graph representation you created in Part I to read a description of a graph and answer questions about it. In particular, you should use Dijkstra's algorithm to find shortest paths in the graph. You will do this by filling in code for the shortestPath method in MyGraph.java. You may assume that graphs you are given will not contain negative cost edges. A description of the shortestPath method from MyGraph.java appears below:
Grading (please note anything which fails this function might lead points reduction):
[20 pts] public int shortestPath(Vertex a, Vertex b, List<Vertex> path)
Style (6 points)
Driver Program: We have provided a driver program to read in input from the user:
When the program begins execution, it reads the two data files and creates a representation of the graph. Although not required, you may find it useful to provide some way to print or display the graph at this point to ensure that it has been read and stored properly. Once the graph has been built, the program loops repeatedly and allows the user to ask for information about paths in the graph. The user should enter two vertex names. If there is a path from the first to the second vertex, the program will describe the shortest (cheapest) such path, including the vertex names on the path and the total length (cost). For example, if the user enters
DEF, then the output might look like
SEA ABC DEF 520 if the shortest path
DEF runs through vertex
ABC and has a total length of
You should modify Paths.java so that
if there is no path between the two requested vertices, a descriptive message
should be printed.
Input file format: You will need two input files, whose format is as follows:
You may assume that every vertex name that appears in an edge also appears in the vertex list. Note that since data files are expected to represent directed graphs, the existence of an edge from a to b does not guarantee the existence of an edge from b to a (unless both edges exist in the data file), nor does it guarantee that the weight of the edge from a to b is the same as the weight of the edge from b to a. You may assume that negative weight edges will not be present in input files you are given (although zero weight edges may exist).
Two sample data files are available representing information about airports and the cost of a flight between them. File vertex.txt contains a list of 3-letter airport codes, each of which represents a vertex in a directed graph. File edge.txt contains information about the directed edges in the graph.
1) Fill in the method bodies as described in Part I and Part II.
2) Make the slight modification to the provided driver program as requested.
3) Answer the write-up questions below.
Note: You may use Java collection classes for this assignment.
Include the following in a file called
1) A description of the worst case big-O running time of your implementations of these methods:
Please use variables E and V in your answers and explain how you got the values you did.
A short description of any extra credit extensions included in
your code or data files. Be sure to
include a brief summary of how to
operate your program, if you have added new features.
You should turn in the following electronically:
readme.txtfile containing your write-up as described above.
A small amount of extra credit will be awarded for interesting extensions. Here are a few possibilities:
I’m open to others ideas as well, please talk to me if you have other ideas!