Course Links

Exercises

Resources

External

For your final project you will implement a graph data structure in Java, and use it to create an interactive application of your own design. The assignment is set up in stages, so that you can get one part working completely before moving on to the next. To help budget your time, you should aim to complete stage I in the first week, and stage II in the second. As a guideline, successful completion of Stage I will suffice to earn a C or D on the project (depending on style and other considerations), while the top grades are reserved for those who complete most or all of the objectives in Stage II, including the traversal implementations. That said, it is important to write your code carefully and cleanly, and work out the problems in each stage before moving on to the next. It is better to complete less, and have it work without any bugs, than to attempt more that does not work.

You may not pair program for the final project. All work submitted must be entirely your own, with the possible exception of limited amounts of quoted material properly documented according to the course standards.

Stage I -- Graph Implementation

We are spending time in class examining the implementation of graphs. Although they may be represented in many different ways, for this assignment you will use a sparse, list-based representation offering significant representational flexibility. Both nodes and edges will have data structures attached; as a result, the Graph class will be a generic parameterized by two types.

To give you an idea of what is expected, you should browse the javadoc pages of a sample Graph class. You should implement the same functionality, so that your graph class may be used by a program expecting this interface. Keep in mind that this shows only the fields and methods declared public: you will probably want additional methods with more limited access to accomplish tasks that would be potentially dangerous (lead to an inconsistent data structure) if made available for public use. You are not required to follow the given interface exactly, and may wish to make some changes -- for example, if you plan to implement directed graphs, then some of the methods should take this into account. Nevertheless it is probably a good idea to consider any changes carefully, and perhaps discuss them with the instructor. In general, you should feel free to add methods that seem useful, so long as they don't expose internal structure that should be hidden.

You should test your classes thoroughly to ensure that they will function properly in the next stage of the project. Develop these tests in the file TestGraph.java, and submit that with the rest of your assignment. The contents of TestGraph should show that you understand how to thoroughly test a new class.

You are encouraged to use the Java core classes in this project wherever they seem applicable. In particular, the ArrayList class is recommended for storing lists/sequences, and HashSet when you have a collection that will be tested often for membership. Take advantage of the methods already defined by these classes, such as contains(), remove(), get(), etc. (Note that some of these depend on the proper definition of the .equals method in order to function properly, and that redefining .equals also obliges you to redefine .hashcode.) Please note in your readme file why you chose to use any predefined data classes that appear in your program.

To Submit -- Stage I

Submit files as stage1final by 11:59 PM on 6 December and I will give you feedback the following week.

Stage II -- A Graph Application

For stage II of the project, you will extend the Graph class written in the previous stage to create a useful application. For this stage, some of the details of the assignment are left flexible to allow you to develop your own ideas. Each section below describes different aspects that you may choose to develop. You may put these together into a graph editing program, or you may pick some more focused application such as efficient maze traversal. The planning and implementation will be left up to you, with the exception of the notes given out in lectures. (For this reason among others, continued class attendance is important.)

Input/Output Mechanisms

For the TestGraph program it is sufficient to "hard-code" the method calls to create a simple graph. Using this method seriously limits the flexibility of a program, of course, since any change to the graph structure involves recompilation. We need a better way of supplying the program with interesting graphs to work on. The two principal means of accomplishing this are interactively via a GUI, and off-line by reading a data file.

GUI-based graph building
The program should present the user with a GUI (either modal or modeless) that makes it easy for a user to build a graph interactively. The user should be able to add nodes by clicking, move them by dragging, delete them by clicking, add edges by dragging from one node to another, and delete edges by the same action, all depending on the current mode. Animation during drag operations is desirable but not required.
Text-Based Input
If GUI interaction is not chosen, then the program should be implemented using a text menu of choices, including loading a new graph from a file, printing the graph or its adjacency matrix, and making changes to the graph such as adding/removing nodes and edges. Text-based programs should take care to make the user interface as clear as possible: it should be easy to see the structure of the graph when it is printed, and easy to specify desired changes when adding or removing from the structure. You will have to work harder than in a GUI environment to make clear to the user what the structure of the graph is, since there is no visual representation. If I can't understand easily what is going on as I interact with your program, you will probably not get a very high grade.
File Input
Programs that implement file input should be able to read in a file in a predetermined format and convert it into a corresponding Graph data structure. A very basic example of one possible format is shown below: 
 
p 4 6 
n 1 New_York 
n 2 Los_Angeles 
n 3 Chicago 
n 4 Houston 
e 1 2 2800 
e 1 3 795 
e 2 3 2020 
e 3 4 1085 
e 1 4 1635 
e 2 4 1550
The first line states the "problem" by giving the number of nodes and edges. The next four lines describe the four nodes, giving a temporary id and a data value for each. (You may wish to add extra data, such as position coordinates, depending on the specifics of your program). The last six lines describe the edges, using the temporary ids given above to identify the endpoints of the node, and ending with a data value (the edge weight). You may augment this file format with additional information, if you wish. For example, the vertex coordinates mentioned above would probably be important if your file will work within a GUI environment, so that you can know where to draw the node. If you allow for file input, please submit a suitable graph file that is sufficiently complex to be interesting.
File output
Less important than file input, but useful nonetheless, is the ability to write out a modified graph in the format given above. If you implement both input and output, then the graphs you create can persist between individual runs of the program.

It is possible to combine multiple input mechanisms in one program: the GUI may have buttons to load or save a constructed graph. The string data at each node will need to be replaced by point coordinates, for display purposes. Better yet, each node could store both types of data, with the string displayed as a label next to the point, and a GUI mode for adding/modifying label text. (In this case you will probably want to create a custom NodeData class that combines the two pieces of information.)

Traversal

We will consider three traversal algorithms in class. The first two, breadth-first traversal and depth-first traversal, can reveal whether two nodes in the graph are connected. Your implementation should traverse the graph from a user-specified starting node, displaying the nodes visited and edges traversed either visually or in text, and then print out or otherwise indicate the nodes that cannot be reached from the start point.

The third traversal algorithm, Dijkstra's shortest path algorithm, should compute and display the shortest distance from a user-specified starting node to all other nodes. Alternately, it can take two user-specified nodes as input, and display the best path between them along with information about its length. Note that Dijkstra's algorithm reduces to simple breadth-first traversal if the edge costs are all the same -- in order to get interesting results the edges must have varying cost. One simple way to do this in a GUI is to base the cost on the Euclidean distance between the nodes that are connected by an edge.

Other Features

Although simply adding more features to your program will not guarantee a top grade, well thought out additions will be considered for extra credit. For example, you could implement (and use) iterators to traverse the list of nodes and edges, thus providing a safer interface to your class. Or you could define and use a well-motivated subclass of the basic graph class already defined. For example, a GuiGraph class might extend the basic class with methods for GUI display.

You can also explore some further application of graphs. For example, you could exploit the connection between mazes and graphs by writing a program that reads a maze file, converts it to an equvalent graph, and uses Dijkstra's algorithm to find the shortest solution to the maze. Or you could write a trip scheduler, which would find the best way to get between nodes assuming that edges represent voyages that take place at specified times (like a train or air schedule). You could write a program that works with graph flows, perhaps computing the maximum flow between two nodes and/or identifying the minimum cut. In any case, your readme file should carefully document any extensions you choose to pursue. Interested students are encouraged to consult with the instructor in advance about additional options they plan to include.

Readme Files

The readme.txt file you write for this project will be particularly important. Because the assignment leaves a number of program design choices available to you, you should use the summary to document and justify the decisions you make. Often there is more than one correct way to implement a particular feature, and each method may have its own strengths and weaknesses. I am interested in your thought process as you design your program. Your summary file should document why you chose a particular approach over the other possibilities. For full credit it is important not only to make the right choices, but to support those choices with sensible justifications.

In some cases, you may find small ways that you wish to alter the implementation details described in this document so as to better fit the design you are creating. The assignment is flexible enough to accommodate some changes of this sort. However, it would be wise to check with the instructor before embarking on any such modification, and to document in your summary exactly why you made the change you did.

To Submit -- Stage II

Submit files as final. All files are due by the end of the last day of classes.