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, referred to as weighted union in the slides) 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 (like confirming that the parameter passed is a root) 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 Section 8.7 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 always 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. For the code you turn in, you must 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. (If you decide to go into the business of printing out mazes and selling them to your roommate and find that these characters do not print out nicely on paper, feel free to use other characters. HOWEVER, for ease of grading and full points, please stick with these for the code you submit. ) The following would be a legal maze of height 2 and width 5.
+-+-+-+-+-+
|
+ +-+ + +-+
| | |
+-+-+-+-+-+
Use of Java Collections: 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. For E and Maze only - 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 in your solution.
Part III.
Writeup Questions
1. For your DisjointSets implementation, what is the worst case running time of a single union operation?
2. For your DisjointSets implementation, what is the worst case running time of a single find operation?
3.
Please briefly discuss how you went about testing your disjoint
sets. Feel free to refer to your submitted test files.
4. If you worked with a partner, describe 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.
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
· Your test code for your DisjointSets implementation.
· ReadMe.txt – text file containing your answers to the writeup questions.
· 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, only one partner needs to
submit the code electronically, be sure that both partners’ names
are listed in all files.