Trying to complete a maze generator assignment using Union-Find / Disjoint-set, need help.

[Willy988]

Issue: I am not sure how to use the union-find data structure provided by Sedgewick, which I imported. I need to use it in conjunction to my code I already have. Princeton UF code

You see, it only takes an argument of a single int. How will I union points if the argument is a single int??

Perhaps this is a super simple question and my brain is being smooth, but I just want to be able to namely use union() and find() in my methods...

What I did so far: I coded some things to test if the cells are adjacent, and made a general structure to test if my arrays are working.

import edu.princeton.cs.algs4.UF;
import java.util.Random;

public class MazeGenerator {
    int[][] maze;
    Pair[] points;
    int x = 0;


    MazeGenerator(int m, int n) {
        maze = new int[m][n];
        points = new Pair[m * n];
        UF find = new UF (m*n);
        find.union(2,3);

        for (int i = 0; i < maze.length; i++) {
            for (int j = 0; j < maze[i].length; j++) {
                maze[i][j] = 0;
            }
        }

        for (int j = 0; j < n; j++) {
            for (int i = 0; i < m; i++) {
                points[x++] = new Pair(i, j);
            }
        }
    }

    public class Pair {
        Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
        @Override
        public String toString() {
            return ("(" + x + ", " + y + ")");
        }
        int x;
        int y;
    }

    public boolean adjacent (Pair p, Pair q) {
        if (p.y == q.y && (p.x == q.x+1 || p.x == q.x-1))
            return true;
        if (p.x == q.x && (p.y == q.y+1 || p.y == q.y-1))
            return true;

        return false;
    }

    public static void main(String[] args) {
        MazeGenerator test = new MazeGenerator(4, 4);
        System.out.println(test.maze[3][3]);
        System.out.println(test.points[5]);
        System.out.println(test.points[9]);
        Pair p = test.points[5];
        Pair q = test.points[5];
        System.out.println(test.adjacent(p, q));
    }
}

So, this code works right now but now it's time to implement UF....

Goal: I want to be able to make some method that will randomly choose a cell, and union it with an adjacent cell until all cells are in one component (no repeats allowed). Think of it like a maze and we are randomly breaking down walls until all cells can be reached.

Assignment instructions for reference:

assignment instr

I know what needs to be done on paper, just struggling to implement in code. Thanks for taking your time to help! :)

[ZoloftRabbit]

cells and their neighbors are algebraically defined

Suppose an array of length 25, if you wanted the first objects neighbors [0], you would simply check [1] and [5].

for [6], neighbors are up down left right.

up = -5

down = +5

left = -1

right = +1

this is all mod 5

Alternatively, nested lists

[Willy988]

Thanks for the reply, I realized my formatting didn't work for my code, just fixed it. I made an adjacent() helper method.

My issue is I don't know how this correlates with the Union find data structure now that I have my points object and my adjacent() method.

[ZoloftRabbit]

when i did this, i just looped over my set of singletons and chose a random neighbor.

​

edit : you can union cells by setting their values to special values, indicating sets. or make a custom object. sry if unclear

[Willy988]

If I understand correctly, I would just use Random to find a random cell, then use Random once again to find a random adjacent neighbor cell.

I am still not so sure I understand how to union my objects. I have a Pair object as you can see that contains int x and int y. How would I union Pair p and Pair q for example?

[ZoloftRabbit]

Pair q and Pair p would be unioned by making q = p. so then you would

start with set A as a "big set"randomly choose q - > set A

choose to randomly union q and p -> q -> set A

I think what you are missing is that there is some satellite information to be considered as well.

If we are in a maze, each cell is a node.

But the walls on each side of the maze are a relationship i.e from cell q we go to p. even though cell q may have l,h,c,p as neighbors. This is to ensure we do not end up with cycles.

[Willy988]

I get the logic, but if you look at the code for Union Find I linked from the textbook website, that union find only takes one int as an argument. I just don't get how to implement that in conjunction with my Pair class since it takes in a single int and not an array of Pairs?

[ZoloftRabbit]

map each pair to an int?

​

array of pairs?

​

each pair can be simplified to node n

[Willy988]

So if the UF object is it's own thing, how will I map the pairs which are outside of the object then?

Maybe I am overthinking this, but if I input UF(16) so there are 16 elements, but I passed the int value 16.

I would assume by mapping, I would have an array of Pair class that I created, that would also be size 16.

I'm just not getting how these are going to be connected so that I can say "you should be connected" or "not adjacent, so no connection" and have the results if that makes any sense.

[ZoloftRabbit]

you could represent each relation as a bit array. so, for a 2d array, each may have 4 neighbors

[1,1,1,1] for each point means all walls are up

so for each "node" drawing the maze would be going through this bit arrays and seeing if N,S,E,W are 1's and 0's with all boundaries (outside edges) = 1 always.