12
\$\begingroup\$

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)

  1. P: Defines the dimensions of the maze
  2. 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 < sets.length; i++) {
            sets [i] = -1;
            g[i] = new List();
        }
    }

    /**
     * Join two disjoint sets by size. If x and y are the same size,
     * tree containing y becomes subtree of root containing x.
     * 
     * @param   x   Attempt to find the integer in the set and union it to y
     * @param   x   Attempt to find the integer in the set and union it to x
     */
    public void union (int x, int y) {
        int root1 = find(x);
        int root2 = find(y);

        // roots cannot be a part of the same set for union
        if (root1 != root2) {
            // Make x subtree of y
            if (sets[root2] < sets[root1]) {
                sets[root2] += sets[root1];
                sets[root1] = root2;
            }
            // Make y subtree of x
            else {
                sets[root1] += sets[root2];
                sets[root2] = root1;
            }
        }
    }

    /**
     * Search for element 'num' and returns the key in the root of tree
     * containing 'num'. Implements path compression on each find. 
     * 
     * @param num   Element to search for in the set
     * @return      Returns the root of the set that the element is a child of
     */
    public int find (int num) {
        int k = num;
        int root, next = 0;
        callsToFind++;
        totalPathLength++;

        // Find the root
        while (sets[k] >= 0) {
            k = sets[k];
            totalPathLength++;
        }
        root = k;
        k = num;

        // Path compression along the trajectory of the tree from the root
        while (sets[k] >= 0) {
            next = sets[k];
            sets[k] = root;
            k = next;
        }
        return root;
    }

    /*
     *  Displays contents of each element; Negative values represent
     *  the size of the subtree. Negative values also indicate that the
     *  element is the root for the tree
     */
    public void printAll () {
        int i = 0;
        while (i < sets.length) {
            System.out.print (sets[i] + " ");
            i++;
        }
        System.out.println();
    }

    /**
     * @return  Returns the number of disjoint sets present in the structure
     */
    public int numberOfSets () {
        int num = 0;
        int i = 0;
        while (i < sets.length) {
            if (sets[i] < 0) {
                num++;
            }
            i++;
        }
        return num;
    }

    /*
     * Prints statistics for the structure:
     * Number of disjoint sets present in the structure
     * Also the average path length required across all calls to find
     */
    public void printStats () {
        System.out.printf ("Number of sets remaining =  %4d" ,numberOfSets());
        System.out.println();
        System.out.printf ("Mean path length in find =  %6.2f" , (float)totalPathLength / callsToFind);
    }
} // End UnionFind Class

Test Client

/*
 * Test Client
 */
public class EVBEP3 {

    public static void main(String[] args) throws FileNotFoundException {
        // Used for accepting command line arguments
        //Scanner sc = new Scanner (System.in);

        // Used for testing purposes
        Scanner sc = new Scanner(new File("p3in3.txt"));
        UnionFind uf = new UnionFind (0);
        String line = "";
        boolean done = false;
        long startTime = 0;
        long endTime = 0;

        // Loop runs as long as done != true
        while (!done) {
            line = sc.nextLine();   
            String [] tokens = line.split(" "); 

            if (tokens.length >= 1) {   
                switch (tokens[0]) {

                    /*
                     *  Print name followed by newline
                     */
                    case "N": {
                            System.out.println("Evan Bechtol");
                            break;
                    }

                    /*
                     *  Create Union-Find structure with elements 0 to n-1
                     */
                    case "D": {
                        int size = Integer.parseInt(tokens[1]);
                        if (size > 0) {
                            uf = new UnionFind (size);
                        }
                            break;
                    }

                    /*
                     * Call union, output the root value and the size of resulting tree.
                     */
                    case "U": {
                        int x = Integer.parseInt(tokens[1]);
                        int y = Integer.parseInt(tokens[2]);
                        uf.union(x, y);
                        break;
                    }

                    /*
                     * Call find, output root index. Keep track of total path length
                     * require in all find operations
                     */
                    case "F": {
                        int num = Integer.parseInt(tokens[1]);
                        System.out.println (uf.find(num));
                            break;  
                    }

                    /*
                     * Output array elements in structure, space separated on one line
                     */
                    case "P": {
                        uf.printAll();
                        break;
                    }

                    /*
                     * Output statistics
                     */
                    case "S": {         
                            uf.printStats();
                            break;
                    }

                    /*
                     * Create new UnionFind class, generate torus maze and print the
                     * connections between the various nodes
                     */
                    case "M": {

                            int p = Integer.parseInt(tokens[1]); // Used to define the dimensions of maze
                            int twoP = (int)(Math.pow(2, p));    // Represents 2^p
                            int d = twoP * twoP;                 // Represents total number of nodes length * width
                            int q = Integer.parseInt(tokens[2]); // Represents edge weights
                            int i = 0;              // Represents 
                            int j = 0;
                            int choice = 0;
                            int numSets = d;
                            int weight = 0;
                            uf = new UnionFind (d);

                            // Union nodes together until there is only one set.
                            // This controls how the maze is constructed, ensures randomization.
                            while (numSets > 1) {
                                startTime = System.currentTimeMillis();
                                choice = randInt(0, 3);
                                weight = randInt(1, q);
                                i = randInt (0, twoP + (-1));
                                j = randInt (twoP * i , twoP * (i + 1) + (-1));

                                // If the noeds are not in the same set already, and they present a valid neighbor
                                // union is performed and number of sets is decremented.
                                if ((uf.find(i) != uf.find(j)) && uf.g[j].validEdges (i, j, twoP, choice, weight)) {
                                    uf.union(i, j);
                                    numSets += -1;
                                }
                            }

                            // i is reused as an iterator here
                            i = 0;
                            // Display the connections between nodes
                            for (List list : uf.g) {
                                System.out.println ("Node " + i);
                                //list.display();
                                list.printMaze();
                                i++;
                            }
                            endTime = System.currentTimeMillis();
                            break;
                    }

                    /*
                     *  End of data file, print newline and exit
                     */
                    case "E": {
                            System.out.println();
                            done = true;    // Break the loop, end the program
                            break;
                    }
                }
            }
        }

        System.out.println ("Run time for M command in milliseconds: " + (endTime - startTime));
        sc.close();
    }


    public static int randInt(int min, int max) {

        // NOTE: Usually this should be a field rather than a method
        // variable so that it is not re-seeded every call.
        Random rand = new Random();

        // nextInt is normally exclusive of the top value,
        // so add 1 to make it inclusive
        int randomNum = rand.nextInt((max - min) + 1) + min;

        return randomNum;
    }
} // End EVBEP3 Class

Adjacency List Structure

/*
 * The Node class creates individual elements that populate the 
 * List class. Contains indexes of the node's neighbors and their
 * respective edge weights
 */
class Node {
    public int top;
    public int topWeight;
    public int bottom;
    public int bottomWeight;
    public int left;
    public int leftWeight;
    public int right;
    public int rightWeight;
    public int numConnec;

    // Default constructor, ititializes neghbors to -1 by default and edge
    // weights to 0
    Node () {
        top    = -1;
        right  = -1;
        bottom = -1;
        left   = -1;
    }
} // End Node class


/*
 * The List class contains Nodes, which are linked to one another
 * to create a Linked List. Used as an adjacency list in the
 * UnionFind class
 */
 class List {
    public Node neighbors;

    // Default constructor
    List () {
        neighbors = new Node ();
    }


    /*
     * Display all connections for the node, regardless if a connection is present
     * or not. Also displays edge weights.
     */
    public void display () {
        System.out.print("Top Neighbor   : " + neighbors.top + '\n');
        System.out.print("Top Weight     : " + neighbors.topWeight + '\n');
        System.out.print("Left Neighbor  : " + neighbors.left + '\n');
        System.out.print("Left Weight    : " + neighbors.leftWeight + '\n');
        System.out.print("Right Neighbor : " + neighbors.right + '\n');
        System.out.print("Right Weight   : " + neighbors.rightWeight + '\n');
        System.out.print("Bottom Neighbor: " + neighbors.bottom + '\n');
        System.out.print("Bottom Weight  : " + neighbors.bottomWeight + '\n' + '\n');
    }

    /**
     * Generates valid edges for the node, also assigns a randomly generated weight to that edge
     * @param i         The row that the node exists on, used to generate outer-node edges
     * @param j         The index of the node in the maze from 0 to (2^p)^2 - 1
     * @param twoP      Represents the dimensions of the maze, used in calculating valid edges
     * @param choice    Randomly generated number to choose which edge to generate
     * @param weight    Randomly generated number to assign generated edge a weight
     * @return          If the assignment was done correctly, returns true. Else returns false.
     */
    public boolean validEdges (int i, int j, int twoP, int choice, int weight) {
        if (neighbors.numConnec < 4) {
            // Top
            if (choice == 0) {
                neighbors.top = generateTop(i, j, twoP);
                neighbors.topWeight = weight;
                neighbors.numConnec++;
            }

            // Right
            else if (choice == 1) {
                neighbors.right = generateRight(i, j, twoP);
                neighbors.rightWeight = weight;
                neighbors.numConnec++;
            }

            // Bottom
            else if (choice == 2) {
                neighbors.bottom = generateBottom(i, j, twoP);
                neighbors.bottomWeight = weight;
                neighbors.numConnec++;
            }

            // Left
            else if (choice == 3) {
                neighbors.left = generateLeft(i, j, twoP);
                neighbors.leftWeight = weight;
                neighbors.numConnec++;
            }
        }
        else {
            return false;
        }
        return true;
    }

    /*
     * Utilizes StringBuilder instance to gather the number of connections
     * to other nodes for this node, then get the nodes connected to, finally
     * getting the weights of edges in order of top -> right -> bottom -> left
     * 
     * Format is as follows:  
     * #Connections  Connected Nodes(each node displayed)  Connected Edge Weights(each node displayed)
     */
    public void printMaze () {
        StringBuilder str = new StringBuilder();

        // Append number of connections to str
        if (neighbors.numConnec > 0) {
            str.append(neighbors.numConnec + " ");

            // Append connections to str
            if (neighbors.top > -1) {
                str.append(neighbors.top + " ");
            }
            if (neighbors.right > -1) {
                str.append(neighbors.right + " ");
            }
            if (neighbors.bottom > -1) {
                str.append(neighbors.bottom + " ");
            }
            if (neighbors.left > -1) {
                str.append(neighbors.left + " ");
            }

            // Append weights to str
            if (neighbors.topWeight > 0) {
                str.append(neighbors.topWeight + " ");
            }
            if (neighbors.rightWeight > 0) {
                str.append(neighbors.rightWeight + " ");
            }
            if (neighbors.bottomWeight > 0) {
                str.append(neighbors.bottomWeight + " ");
            }
            if (neighbors.leftWeight > 0) {
                str.append(neighbors.leftWeight + " ");
            }
        }
        else {
            str.append("0");
        }

        System.out.println(str);
    }

    public int generateTop (int i, int j, int twoP) {
        int neighbor = 0;

        // Set the top neighbor
        if (i == 0) {
            neighbor = j + twoP * (twoP + (-1));
        }
        else {
            neighbor = j + (-twoP);
        }
        return neighbor;
    }

    public int generateRight (int i, int j, int twoP) {
        int neighbor = 0;

        // Set the right neighbor
        if (j == twoP * (i + 1) + (-1)) {
            neighbor = twoP * i;
        }
        else {
            neighbor = j + 1;
        }
        return neighbor;
    }

    public int generateBottom (int i, int j, int twoP) {
        int neighbor = 0;

        // Set the bottom neighbor
        if (i == twoP + (-1)) {
            neighbor = j - twoP * (twoP + (-1));
        }
        else {
            neighbor = j + twoP;
        }
        return neighbor;
    }

    public int generateLeft (int i, int j, int twoP) {
        int neighbor = 0;

        // Set the left neighbor
        if (j == twoP * i) {
            neighbor = twoP * (i + 1) + (-1);
        }
        else {
            neighbor = j + (-1);
        }
        return neighbor;
    }
} // End List class
\$\endgroup\$
2
  • 2
    \$\begingroup\$ Like the way you organized this, +1. \$\endgroup\$
    – Legato
    Commented Apr 8, 2015 at 17:05
  • 1
    \$\begingroup\$ @Legato Thanks :) I think that clarity goes a long way for getting good answers. \$\endgroup\$ Commented Apr 8, 2015 at 17:12

1 Answer 1

2
\$\begingroup\$

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().
\$\endgroup\$
2
  • \$\begingroup\$ Thanks for all of your feedback! The reason that I was using "sets" was because the project spec. specifically required the implementation that way, and also required "g" to be a part of union-find structure. (Not sure why, my prof. said that we couldn't change it though). As far as the public variables go, I'll change that. I was just being lazy and didn't want to make getters/setters :P \$\endgroup\$ Commented Apr 13, 2015 at 15:56
  • \$\begingroup\$ Also, I just changed my numberOfSets() method to reflect the changes you suggested, as well as the printStats() method. Thank you again for your time! \$\endgroup\$ Commented Apr 13, 2015 at 16:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.