CSE373 Data Structures Au07, Homework 6
Electronic Turn-in of code due:
Friday 11am, Dec 7, 2007 using this link.
Printout of code due: At the beginning of class, Friday, Dec 7, 2007
For this assignment, (if you wish, not required) you may work with one partner. Any two people
working as partners are likely to need to work together closely throughout the
process, probably writing all of the code together. Pair programming may
be a good approach to try for this assignment. Pair programming is a technique that is a part of Extreme Programming
approaches used in some software companies. Here are a few references on pair programming: [as part of Extreme
programming (XP)] [pair programming in
Computer Science courses]. Note: You
are not required to work in pairs – working individually is fine.
If you plan on working pairs: one partner MUST send email containing
the names and email addresses of both partners to Thach
by 11:59pm Monday Dec 3.
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.
Part I. Graph Representations
In this part of the assignment you will implement a graph representation to
be used later in Part II.
The assignment has several files provided:
Fill in the remaining code for AdjListGraph.java, and
Edge.java. Your code should be efficient and must have the minimal big-Oh
possible for the given implementation.
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.
What to Do
Write a program that reads a description of an undirected graph with
weighted edges, then answers questions about paths in that graph. More specifically, the program should operate
as follows:
- The program should begin
execution in a
main method
in a class named Paths. This program should accept two command
line arguments: the name of a text file containing a list of vertices, and
the name of a second text file giving the edges between these nodes. The files are specified 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 edge. The first
two lines give the node names at either end of the edge. 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).
Two sample data files are available representing information
about airports and the distances between them. File vertex.txt contains a list of 3-letter
airport codes, each of which represents a vertex in the graph. File edge.txt contains
information about edges in the graph. Each edge is described by two lines that each contain an airport code, and
a third line giving the distance between them. You may assume that every node name that appears in a path (edge) also
appears in the vertex list.
- When the program begins
execution, it should read the two data files and build an adjacency list
representation of the graph that they represent. The data describes an undirected graph;
in the adjacency list representation you should represent each undirected
edge as a pair of directed
edges, one in each direction between the two vertices.
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 should loop repeatedly and allow 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 such path, including the vertex names on the path
and the total length. 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 paths
in the graph.
You need to decide how the end of input is indicated and have the program
quit gracefully when the end of input is reached.
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 the graph implementation from Part I as a starting
point.
Extra Credit
A small amount of extra credit will be awarded for interesting
extensions. Here are a few
possibilities:
- 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.
- 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.
- 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:
- The files that make up your
program. (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. 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 brief summary of the
data structures and algorithms you finally used. In particular, you should give a
summary of the major design decisions you have made in creating your
graph data structure, and any major changes that were needed as your design
evolved to create the final program. This needs not be long, but it should
describe major decisions you made and any surprises you encountered that
required changes as you developed the code.
- 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 and make a
printout. 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.
