As you know, graphs (the ones with nodes and edges, not the y = x^2 kind) are among the most general and versatile data structures. Any time you're working on a problem with items that have pairwise relationships, there's a good chance you'll need a graph of some kind. If you're using graphs, then you'll be using graph algorithms, too: depth-first search, breadth-first search, Dijkstra's algorithm, computation of minimal spanning trees, discovery of connected components, etc.
If you implement any of these algorithms, you're going to need to test them. And to test them, you'll need a collection of sample graphs. That's where this project comes in. You are going to create a graphical user interface program that enables people to build and save graphs.
The appearance and functioning of this program are entirely up to you. I have a few ideas that you might want to think about, however. Here they are:
You'll need to specify some sort of file format for the representation of graphs. I strongly recommend that your graph files be text files that are at least minimally human-readable. The file format will need to contain information on the number of nodes, their labels, the number of edges, the nodes the edges connect, etc. If your program supports directed graphs and edge weights, then the file format will need to support that information. Since your users will have placed nodes at various locations in the graph-building window, your file format will also need to store node location information, even though that information is not, strictly speaking, a part of a graph.
Ideally, the basics of graph construction should be manageable mostly via the mouse. Some kind of clicking should allow you to create a new node in a particular location. Another kind of clicking or clicking and dragging should allow you to create edges. Having the ability to drag nodes around would be nice, too.
Though the core functioning of this program is the construction and saving of graphs, it would be good to also implement a graph algorithm of some kind and make the results available visually. For example, it's pretty straight-forward to construct a spanning tree based on depth-first search from a starting node, so you could, for example, provide a menu command that allows you to display the spanning tree in green. There is no shortage of neato features of this sort that one could add.
Despite the tantalizing potential offered byt the previous paragraph, please make sure to get the core functioning of the program done: building, saving, and displaying graphs.
Hand in the following (in a directory named "final") via HSP by 5:00PM Monday, June 7, 2004.
Source code
A text file called readme.txt containing:
Anything else you consider relevant, including Makefiles, use cases or diagrams (only if you created them for your own benefit), data files, etc.
Correctness. If you implement a feature, make sure it works correctly. Think about how you're going to test your features before you start coding. You might even go so far as to write a collection of test cases and/or a unit testing plan before doing anything else.
Style and readability. Appropriate commenting, indentation, naming, use of symbolic constants, etc. Good choices of data structures and methods also enhance readability.
User interface. Make your program pleasant and efficient to use. This is the focus of this project.
Modularity. I expect you to make good use of the data abstraction tools available in Java.
Appropriate use of libraries. If you need a string manipulation or mathematical function, for example, check out the methods for String and Math. Make a point of knowing (or asking about) Java's standard libraries.
Documentation. Use javadoc to describe your methods and classes briefly and clearly.
Assertions. Enforce your pre-conditions with assertions.
Performance. This may not be relevant for this project, but if your program has nasty delays in it while you're dragging or typing, try to figure out why, and fix it.
Good memory management. Since Java has garbage collection, it's easy to ignore memory management. But if you are instantiating lots of new objects when you don't need to (say, inside a loop instead of outside), you're wasting both time and space.
Start early, have fun, and keep in touch.
Have a great summer and beyond.