CSC 212: Programming with Data Structures

Final Project

Due: Friday, April 29, 11:59pm

Adapted from assignment by Nick Howe

Overview

For this stage of the project, you will extend your Graph class from 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. There is a core part of the assignment that everyone should do, then some sections you can pick and choose from to build up the final product.

Honor Code

At this stage of the semester, it is helpful to remember the Honor Code. For this assignment you should not be looking at any other code besides your own and the code you have developed this semester. That includes other student's code and code on the Internet (a few lines of StackOverflow is fine, but no algorithms, including the code on Wikipedia). This is to make sure that you're getting the full chance to learn and display your own skills, as well as fairness to others in the class. If you have any questions, please let me know.

Core Assignment (up to 70%)

The core part of the assignment that everyone should do is to create a graph visualization and implement the Havel-Hakimi algorithm discussed in class for creating a graph from a degree sequence. For the visualization part, it is completely up to you, but here is one recommendation:

Visualization

  1. Create a class DisplayNode, which will be used to hold information about how a node should be displayed. You can think of this class as the concrete "V" in your Graph class. Fields for this class might include the node's color, position, label, etc.

  2. Create a class DisplayEdge, which will be used to hold information about how an edge should be displayed. You can think of this class as the concrete "E" in your Graph class. Fields for this class might include the edge's color, data, etc.

  3. Create a class JGraph which will extend JComponent. This should have a paintComponent method, among others. Spend some time thinking about how to implement paintComponent. JQueue might be a good reference for this part.

  4. Create a class GraphGUI (see QueueGUI as a reference). This will have a main method and be the driver of the GUI.
Try out your visualization with a hard-coded graph to start. This starting graph can then be used for traversals.

Havel-Hakimi

Then implement Havel-Hakimi (think about where it makes sense to put this algorithm), which should take in a degree sequence (you may hard-code an interesting sequence as a field at the top). It could be part of an extension to let the user enter the sequence through the command line or through the GUI directly. The graph does not have to be built up gradually, it can be displayed in it's final form right away. It could be part of an extension to have a mechanism for building up the graph gradually (i.e. the user clicks a button to have the next step shown). So the graph could first start out as all "floating" nodes, and gradually become connected. Requirements:
  1. The graph should start out as "floating" nodes. (OPTIONAL)

  2. The user should be able to click (on a button, for example), and execute the next step of the algorithm, until it's finished. (OPTIONAL)

  3. The user should be able to type in the degree sequence in a text-box. (OPTIONAL)

  4. The algorithm must be recursive in nature. (NOT OPTIONAL)

Extensions

For the rest of the assignment, you may choose from the options below (each roughly 10% of a fully complete assignment, but at least two of your choices must be traversals for a top grade).
  • Extensions of Havel-Hakimi

    Implement the previously required functionality of the Havel-Hakimi visualization.

  • GUI-based graph building

    The program should present the user with a GUI 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. Animation during drag operations is desirable but not required.

  • 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 for your file to 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.

  • Breadth-first traversal (BFT)

    To start a breadth-first traversal (BFT), the user could click on a button and then a start node (for example). It would also be okay to start the traversal from the first node added, or the first alphabetically. Then the traversal order should be indicated visually (i.e. nodes changing color), or text-based within the GUI. Think about ways that disconnected nodes could be indicated to the user (optional). Your implementation could be queue-based, as discussed in class.

  • Depth-first traversal (DFT)

    Same as above, but for depth-first traversal from a given node. Your implementation should be recursive, as discussed in class.

  • Dijkstra's Shortest Path

    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.

  • Network Flow

    Another option is to implement a max-flow algorithm such as the one discussed in class. Think about how to visualize the algorithm working and display the maximum flow to the user.
There are many other directions that could be pursued. If you create new features or implement other algorithms, document them throughly in your readme for the possibility of extra credit.

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.

To Submit -- Stage II

  • Any java files necessary to compile your program
  • Any data files you used to test your program
  • A screenshot of an interesting example
  • readme.txt
  • typescript if that makes sense for your program

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