Torus Maze Generator

I have been working on a project to randomly generate a torus made through the use of an adjacency list and disjoint set structure (to be extended to solve the maze later), made from scratch. I think that I have optimized my code pretty well, but may have over-looked some things.

Program Description:

The program works by randomly picking a row and a node in that row to generate an edge for, while there are more than 1 disjoint sets remaining. Checks are done to ensure that the nodes are not already a part of the same set as well.

Desired from post

• Efficiency improvements

• Bugs found (if any)

• Suggestions on clarity improvements

Constraints

• There are no boundaries in a torus maze; exterior nodes will "wrap" to the opposite side of the row or column that they exist on.

• I cannot use any pre-built Java data structures other than Arrays and Strings

• Maze must be able to generate (2^p)^2 elements with 'p' being in the inclusive range of 1 to 6, with random edge weights 'q' from inclusive 1 to q.

Test Input File

The 'M P Q' command works by passing two arguments:

(The max I have tested this program with is: M 12 50, which creates 16,777,216 nodes)

• P: Defines the dimensions of the maze

• Q: Defines the maximum weight of generated edges

N

M 6 40

E

Disjoint Set (Union-Find) Structure

```
/*
* Defines the Union-Find (Disjoint set) structure, using union by size
* and path compression. All values initialized
*/
class UnionFind {
public int [] sets;
public List [] g;
public int totalPathLength;
public int callsToFind;

/*
* Creates the structure and initializes all index (0 -> n-1) values
* to -1
*/
UnionFind (int numElements) {
totalPathLength = 0;
callsToFind = 0;
sets = new int [numElements];
g = new List[numElements];

for (int i = 0; i = 0) {
k = sets[k];
totalPathLength++;
}
root = k;
k = num;

This post will focus on your implementation of Union-Find.

First and foremost, you're not using the g member at all, so you should probably remove that. It turns out you actually are using this, just not in your Union-Find class. This is a bad idea. We typically wish to minimise coupling, and using a public g member in this manner does precisely the opposite.

Next, all your members are public. This usually isn't advisable; you should endeavour to make them private and provide getters and setters as appropriate.

Next, you are in my opinion overloading (not in the programming sense! :P) the sets member. It's doing double-duty, holding the nonnegative parent node index for child nodes, and the negated size of the set for root nodes. The name therefore cannot be meaningful, since its two purposes are so distinct.

If you are pressed for memory then I understand your use of that solution. Keep in mind, however, that since disjoint-set structures are really forests, the classic implementation uses Node objects containing a parent reference and optionally an int for rank / size. This has the advantage of being more semantically meaningful (and arguably more readable):

private class UnionFindNode {
    private UnionFindNode parent; // this, if root
    private ... data;
    private int rank; // optional
}

Finally, your implementation of numberOfSets() is linear when it could be constant. Observe that performing a union operation (on two disjoint sets) will decrease the number of disjoint sets by exactly one. Then, you could add a member (say, numDisjointSets) initialised to numElements that you decrement in your union() function.

Minor things:

• Function calls seem inconsistent — why do you use a space before the argument list sometimes, but not always? (It seems like you omit the space if it takes no arguments. If so, why do you have a space in your declarations for functions taking no arguments?)

• There seems to be an arbitrary space in sets [i] = -1; in your initialisation function.

• Using a for..in loop in printAll() seems more idiomatic.

• Consider renaming numberOfSets() so that it uses a verb. Maybe countDisjointSets() or countDistinctSets()?

• You can use the %n format code to print a newline instead of println() in printStats().

StackExchange Code Review Q#86263, answer score: 2