CIT 594 Assignment 6: Graphs and Backtracking
Spring 2014, David Matuszek
Name your project Graphs
. Within this project, create a graph
package. The following classes go in this package.
public Graph(Object value)
creates a graph with the given value
. 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. 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 public Node(Object value,
Graph g)
constructs a node on graph g
with the given value
. public void delete()
deletes this node (and all its associated edges) from the graph it is on.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. 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.public void delete()
deletes this edge.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.We can model graphs, nodes, and edges with plexes using inheritance, not composition. That is, Graph
, Node
, and Edge
each extend Plex
.
Plex
can represent a Graph
:
contents
holds the nodes on this graph.origins
, destinations
, and containers
sets are empty.Plex
can represent a Node
:
containers
set contains a single element, the graph that the node is on.origins
holds its inpointing edges.destinations
holds its outpointing edges.Plex
can represent an Edge
:
containers
origins
holds its origin node.destinations
holds its destination node. Supplied code: Plex.java, PlexTest.java.
Use Test-Driven Design/Development. All your tests (including PlexTest.java
) should be in a separate package named tests
.
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 { |
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.
@author
tag in each class and interface.@param
, @return
, and @throws
tags for each method where they are applicable.readme.txt
file with these estimates: