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

# Purposes of this assignment

• Introduce graphs.
• Introduce backtracking.

# General idea of the assignment

• Implement a graph data structure, using plexes.
• Read in graphs representing mazes.
• Solve the mazes (or tell if they are not solvable).

# 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

• Constructor
• `public Graph(Object value)` creates a graph with the given `value`.
• Mutative transformer
• ` public void delete(Node node)` deletes a node (and all its associated edges) from this graph.
• ` public void delete(Edge edge) `deletes an edge from this graph.
• Accessors
• ` public Set<Node> getNodes()` returns the nodes in this graph.
• ` @Override public String toString() `returns a printable representation of this graph.
• ` public void print() `prints this graph, using the same syntax as `read`.
• `static Graph read(Reader reader)` reads in a graph.
• `public void dump() //` (optional) debugging aid

## The Node class

• Constructor
• ``` public Node(Object value, Graph g)``` constructs a node on graph `g` with the given `value`.
• Mutative transformer
• ` public void delete()` deletes this node (and all its associated edges) from the graph it is on.
• Accessors
• `public Graph getGraph()` returns the graph that this node is on.
• `public Set<Edge> getOutpointingEdges()` returns the edges pointing out from this node.
• ` public Set<Edge> getInpointingEdges()` returns the edges pointing in to this node.
• ` @Override public String toString()` returns a printable representation of this node.

## The Edge class

• Constructor
• ``` public Edge(Node fromNode, Object value, Node toNode) ```constructs an edge with the given `value` from `fromNode` to `toNode`. Nodes must be on the same graph.
• Mutative transformer
• `public void delete()` deletes this edge.
• Accessors
• `public Graph getGraph()` returns the graph that this edge is on.
• ` public Node getOrigin()` returns the node that this edge points out of.
• ` public Node getDestination()` returns the node that this edge points to.
• ` @Override public String toString()` returns a printable representation of this node.

## 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`.

• A `Plex` can represent a `Graph`:
• Its `contents` holds the nodes on this graph.
• The `origins`, `destinations`, and `containers` sets are empty.
• A `Plex` can represent a `Node`:
• Its `containers `set contains a single element, the graph that the node is on.
• Its `origins` holds its inpointing edges.
• Its `destinations` holds its outpointing edges.
• A `Plex` can represent an `Edge`:
• Its `containers` holds the graph on which it occurs is empty.
• Its `origins` holds its origin node.
• Its `destinations` holds its destination node.

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 `value`s are all `String`s obtained from the `value` field of `Token`s. These Tokens may be `NAME`s, `NUMBER`s, or `SYMBOL`s (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. `EOL`s are relevant; indentation is not relevant.

 `digraph { start -> zero zero ( -> one one ( -> two two ) -> one one ) -> zero ) zero end -> finish unconnected}` # 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)

• Use good programming style.
• Don't mix input/output and significant computation in the same method.
• Remember the KISS principle and the DRY principle.
• Use good variable names, etc. etc. All the routine stuff.
• Use Java formatting conventions, not C/C++ formatting conventions.
• If you have not already done so, tell Eclipse to replace tabs with spaces.
• Write Javadoc comments for all classes, interfaces, constructors, and methods.
• Use an `@author` tag in each class and interface.
• Use `@param`, `@return`, and `@throws` tags for each method where they are applicable.
• Include the generated Javadoc with your assignment submission.
• Also include a `readme.txt` file with these estimates:
• Before you begin programming, estimate how long (in hours) this assignment will take you.
• When you are done programming, estimate how long it actually took you.
• Tell the extent to which you used TDD (almost entirely, mostly, somewhat, not at all).
• Your estimates will not affect your grade in any way (unless you don't provide them).
• Except by special arrangement in very unusual circumstances, all projects are to be turned in via Canvas.
• Zip the entire project to turn it in.
• Assignments submitted by email will be ignored.

# 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.