CIT 594 Assignment 6: Graphs and Backtracking
Spring 2014, David Matuszek

Purposes of this assignment

General idea of the assignment

Part I: Implement a graph data structure

Name your project Graphs. Within this project, create a graph package. The following classes go in this package.

The Graph class

The Node class

The Edge class

The Plex class

We can model graphs, nodes, and edges with plexes using inheritance, not composition. That is, Graph, Node, and Edge each extend Plex.

Supplied code: Plex.java, PlexTest.java.

TDD

Use Test-Driven Design/Development. All your tests (including PlexTest.java) should be in a separate package named tests.

Part II: Read in a graph representing a maze

The Graph#read(Reader) method should use your Tokenizer to read a graph, where a graph has the following example syntax. Graph, node, and edge values are all Strings obtained from the value field of Tokens. These Tokens may be NAMEs, NUMBERs, or SYMBOLs (not including "}"). "Negative numbers" (a NUMBER preceded by a "-" SYMBOL) should be allowed. It is permissible to have whitespace between the "-" and the ">" of the "->" operator. EOLs are relevant; indentation is not relevant.

digraph {
start -> zero
zero ( -> one
one ( -> two
two ) -> one
one ) -> zero )
zero end -> finish
unconnected
}
digraph

Part III: Solve mazes

Create a Mazes class, containing a main method, in a separate mazes package. Ask the user for a file containing a Graph (use JFileChooser). The graph should contain a start node and a finish node. Print the graph, then try to find a path from start to finish. If you find a path, print it out; if there is no path, tell the user that the maze cannot be solved. Do this for as many mazes as the user wishes.

General requirements (slightly revised)

Due date

Turn your assignment in to Canvas before 6 a.m. Tuesday, March 18. Late programs, even if only a minute late, will be penalized 10 points for the first week. Programs later than a week may or may not be accepted for grading.