In class we have discussed the implementation of the union-find data structure, and also a fun use of the data structure – to build mazes. For this assignment you are to implement both of these!
You should implement the DisjointSets interface
using union by size (total number of elements) and path compression as
described below. What is expected is an
array implementation of the uptree structure
discussed in class and in lecture. You
may wish to use Weiss’s disjoint
sets as a starting point, however notice that this code uses union by
height and leaves off the checking of many error conditions. Your implementation of the DisjointSets interface should add in error checking and
throw exceptions as needed. Your implementation (named DisjSets.java)
should also include a public constructor as follows:
/**
* Required constructor.
* @param numElements is number of
elements in the set.
*/
public DisjSets(int
numElements);
Here is the interface you are required to implement:
interface DisjointSets
{
/**
* Union two disjoint sets using
union by size (number of nodes).
* root1 and
root2 are assumed to be roots and represent set names.
* @param root1 the root of set 1.
* @param
root2 the root of set 2.
*/
void union(int root1, int root2);
/**
* Perform a find with path
compression.
* Assumes elements in the set are
unique and numbered starting at 0, ending at numElements-1
* @param
x the element being searched for.
* @return
the set containing x.
*/
int find(int x);
/**
* Returns the total number of sets.
* @return the current number of sets.
*/
int numSets();
/**
* Returns the total number of elements
in the given set.
* setNum
is assumed to be a root and represents the name of a set.
* @param setNum
the name of a set
*/
int numElements(int setNum);
/**
* Prints out the elements in the
given set.
* setNum
is assumed to be a root and represents the name of a set.
* @param setNum
the name of a set
*/
void printElements(int setNum);
/**
* Returns an array containing the
elements in the given set.
* setNum is assumed to be a root and represents the name of a
set.
* @param setNum the name of a set
*/
int [] getElements(int setNum);
}
Part II. Generate a maze (as described in
lecture and in Weiss).
For part II, you should generate a maze using the method based on disjoint sets discussed in lecture and in Chapter 8 of Weiss. Your maze should obey the constraints discussed in class – e.g. have only one solution, all cells should be reachable, only walls allowing cells to be reachable should be removed. The starting point of the maze should be the upper left corner and the ending point should be the lower right corner.
Your program should take three parameters: maze height, maze width, and an output file name that the maze will be written to. If you are rusty on command line parameters or writing to files, you might look back at the implementation of Reverse.java in homework #1.
Your program should be in a class called MazeBuilder.java. For example, you should be able to call your program as follows:
java MazeBuilder 15
20 output.txt
to write a maze 15 cells high and 20 cells wide to a file called output.txt. Use the following characters for walls in your maze: put a + at each corner, and use – for horizontal walls and | for vertical walls when they exist. The following would be a legal maze of height 2 and width 5.
+-+-+-+-+-+
|
+ +-+ + +-+
| | |
+-+-+-+-+-+
While we expect you to use your DisjointSets implementation in your solution, you do not
necessarily need to use it to represent the sets of edges in the set E or in
the final set Maze. Feel free to use
something simpler for this: an array, ArrayList or
something else from the Java collections will be o.k. here. It is also fine to use the Java Random class.
You should submit these files:
·
MazeBuilder.java
– the main routine in this class should create a maze and be callable as
shown above.
·
DisjSets.java - your
implementation of DisjointSets.java
·
maze10x10.txt - text file showing maze of size 10 x 10.
·
maze20x10.txt - text file showing maze of height 20 x width
10.
If you work with a partner, 1) only one partner needs to submit the code electronically, be sure that both partners’ names are listed in all files. 2) Include a text file (submit electronically and print out) that describes how you developed and tested your code. If you divided it into pieces, describe that. If you worked on everything together, describe the actual process used – how long you talked about what, how long and in what order you wrote and tested the code. Be sure to describe at least one good thing and one bad thing about the process of working together.