CSE 373 Data Structures 09wi, Homework 6 & 7
Electronic Turn-in due: 11:59pm Thursday,
March 12, 2009.
This assignment will be equal to 1.5 assignments in weight, although it
will only have one due date. In the
assignment, you will develop a graph implementation and then use it to
implement at least one graph algorithm.
In particular, you will implement (at least) Dijkstra’s algorithm
for finding the shortest path.
For this assignment, (if you wish, not required) you may work with one partner for the programming portion
of the assignment. If you plan on working pairs: one partner MUST send email containing
the names and email addresses of both partners to Sean
by 11:59pm Friday March 6th.
Part I. Graph Representations (recommended due date Friday 3/6/09)
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, although you should feel
free to add things to Vertex.java or Edge.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 (see part II.)
Part II. Graph Algorithms
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 may assume that graphs you are given will
not contain negative cost edges.
What to Do
We have provided a driver program to read in input from the user:
- Paths.java
– driver program that reads in vertex and edge files, creates a graph
and prompts use for vertices to find shortest path between.
The
format of the input files are as follows:
- Nodes: This file has
one line per vertex and each line contains a text string with the vertex
name.
- Edges: This file has
three lines per directed edge. The
first line gives the starting vertex.
The second line gives the ending vertex (the one being pointed
to). The third line is a string of
digits that give the distance (or weight) on that edge (this line should
be converted to a number to be stored in the graph).
You may assume that every node name that appears in a path
(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.
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.
- 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 should describe the shortest (cheapest) such
path, including the vertex names on the path and the total length
(cost). If there is no path, a
descriptive message should be printed (i.e., if either name is not a
vertex in the graph or if there is no path between the given vertices).
Your program must use Dijkstra's algorithm to compute the shortest
(cheapest) paths in the graph.
Examples: If the user enters SEA DEF
,
then the output might look like SEA
ABC DEF 1234
if the shortest path from SEA
to DEF
runs through node ABC
and has a total length of 1234
.
You should use your graph implementation from Part I as a starting
point. Feel free to add or extend the
given vertex, edge, and MyGraphs classes (but don’t take anything out).
Extra Credit
A small amount of extra credit will be awarded for interesting
extensions. Here are a few
possibilities:
- (2
points) Improve your implementation of Dijkstra’s by using a
priority queue. For this, you could
modify your code from previous homework or start from scratch. One modification you will need to make
to your priority queue code from the previous homework is for Dijkstra's
algorithm, we need to be able to find items in the priority queue and
update their priorities. The
simplest implementation of this can just do a sequential scan to locate an
item, then adjust the priority, and move the item to its proper place in
the heap. A more complex
implementation would allow items in the priority queue to be accessed in
constant time. A simple sequential
search of the queue is fine for small graphs, but for large graphs we
would like to be able to find items in constant time so the total time
needed to update a priority is a constant plus the log n time needed to
reestablish the heap property in the queue. There are various ways to do this,
including keeping a back-pointer from each vertex to its entry in the
queue.
- (4
points) Additional graph algorithms, in particular, given a vertex
in the graph, compute a minimum spanning tree from that vertex and print a
list of the edges in the MST in the order in which they are added to the
tree.
- (1
point) More/better/interesting data files. The supplied data files are quite
minimal. Data describing more
extensive graphs, other kinds of graphs, or graphs with additional
information such as coordinates or locations on a map would be great.
- (3 points)
Graphical displays: Display the graph as a drawing; allow the user to
select endpoints by clicking on the screen; highlight the path visually;
etc.
What to Turn In
You should turn in the following electronically:
- ALL of the files that make up
your program. This includes
Vertex.java as well as Graph.java.
You should NOT change Graph.java however. (Please turn these in as individual
files, not zipped together. Your
TAs thank you!)
- A file
readme.txt
that contains the
following:
- A brief summary of how to operate your program,
particularly if it has any extra features or unusual commands other than
the basic ones described above.
You should be sure to describe how to indicate the end of the
input data.
- A short description of
any extra credit extensions
included in your code or data files.
- A description of the
worst case big-O running time of your implementations of:
- adjacentVertices?
- isAdjacent?
- Dijksta?
- Please use variables E
and V in your answers and explain how you got the values you did.
- Any additional data or other
files you developed to work with your program. (These should be described briefly in
the
readme.txt
file.)
In
addition, if you worked with a partner, 1)
only one partner needs to submit the code electronically. 2) Be sure that both partners’ names
are listed in all files. 3) Include in
your readme.txt file a description of how you developed and tested your
code. If you divided it into pieces,
describe that. If you worked on
everything together, describe the actual process used – how long you
talked about what, how long and in what order you wrote and tested the
code. Be sure to describe at least one
good thing and one bad thing about the process of working together.