CSC212 Lab 14 2014

--D. Thiebaut (talk) 15:29, 24 November 2014 (EST)

---

Union-Find

Setup

• Create the Processing applet whose code is given below (refer to this page for instructions on how to setup a Processing application with Eclipse).
• Run it.
• Verify that you get the an image similar to the one on the right.
• Verify, as well, that when you move the mouse pointer over vertices, the vertex number appears next to it, and its adjacency list gets printed at the bottom of the window.

import java.util.Random;

import processing.core.PApplet;
/**
 * A Processing.org applet that displays a network where each vertex 
 * can be connected to at most 4 neighbors using undirected edges.
 * The network topology is kept in an adjacency matrix.
 * @author thiebaut
 * The grid generated is square, 50x50.
 * The vertices are arranged logically, Vertex 0 at the top-left,
 * Vertex 1, below Vertex 0, down to Vertex 49 on the last row, leftmost column.
 * To the right of Vertex 0 is Vertex 50.  And so on.
 * 
 *   0  - 50 -- 100 -- 150
 *   |     |     |      |             
 *   1 -  51 -- 101 -- 151
 *   |     |     |      |             
 *   2 -  52 -- 102 -- 152
 *   |
 *   3  
 *   |
 *   4
 *   |
 *   ...   |     |      |                     |
 *   49 - 99 -- 149 -- 199               -- 2499
 * 
 */
public class MazeNetwork extends PApplet {
	private int maxNoVerticesRows = 50;   // geometry
	private int maxNoVerticesCols = 50;   // 50 x 50
	
	private int WIDTH   = (maxNoVerticesCols+1) * 12;  // set the width and height
	private int HEIGHT  = (maxNoVerticesRows+1) * 12 + 30 ; // of applet to match graph exactly
	
	private int maxNoVertices     = maxNoVerticesRows * maxNoVerticesCols;
	private int deltaX = WIDTH / ( maxNoVerticesRows + 1 );
	private int deltaY = HEIGHT / ( maxNoVerticesCols + 1 );
	private int probability100    = 55;   // 55% of probability for adding an edge
	
	private boolean[][] adjMat = null;    // adjacency matrix
	
	/**
	 * add an undirected edge between u and v.
	 * @param v
	 * @param u
	 */
	public void addEdge( int v, int u ) {
		adjMat[v][u] = true;
		adjMat[u][v] = true;
	}
	
	/**
	 * generate a random graph.  The seed of the random number generator
	 * is set to a fixed number, so that the graph generated is always the same.
	 */
	public void initGraph() {
		Random random = new Random();
		random.setSeed( 12345 );				// seed for random number generator
		adjMat = new boolean[maxNoVertices][maxNoVertices];
		for ( int r=1; r<maxNoVerticesRows; r++ ) {
			for ( int c=1; c<maxNoVerticesCols; c++ ) {
				int currentVertex = r * maxNoVerticesCols + c;
				int upVertex 	  = (r-1) * maxNoVerticesCols + c;
				int leftVertex 	  = r * maxNoVerticesCols + c - 1;				
				
				// should we create an up connection?
				if ( random.nextInt(100) <= probability100 ) 
					addEdge( currentVertex, upVertex );
				
				// should we create a left connection?
				if ( random.nextInt(100) <= probability100 ) 
					addEdge( currentVertex, leftVertex );
			}
		}
	}
	
	/**
	 * returns a string with all the vertices adjacent to v.  Used to display
	 * the adjacency list of the vertex under the mouse pointer.
	 * @param v
	 * @return
	 */
	public String adjList( int v ) {
		String s = v+": ";
		for ( int u=0; u<maxNoVertices; u++ ) 
			if ( adjMat[v][u] )
				s += u + ", ";
		return s;
	}

	/**
	 * setup() is called automatically once, at the beginning of the program, when
	 * the program is started.  
	 * We setup whatever needs to be created in this method.
	 */
	public void setup() {
		size( WIDTH, HEIGHT );
		smooth();
		initGraph();
	}
	
	/**
	 * draw() is called 30 times a second, typically, but the main applet thread.  
	 * This is the part of the applet that draws constantly on the screen.  
	 */
	public void draw() {
		// clear screen, make it white...
		background( 255, 255, 255 );
		
		// display each vertex and its adjacent edges..
		for ( int v=0; v<maxNoVertices; v++ ) {
			int vCol = deltaY + (int) ( v / maxNoVerticesCols ) 	* deltaY;
			int vRow = deltaX + ( v % maxNoVerticesRows ) 		* deltaX;
			
			// draw black circle for the vertex 
			ellipse( vRow, vCol, 4, 4 );
			
			// is mouse pointer inside this vertex?  If so, display some
			// information about this vertex
			if ( dist( vCol, vRow, mouseX, mouseY ) < 4 ) {
				fill( 255, 0 , 0 );
				text( v+" ", vCol, vRow );
				text( adjList( v ), 100, HEIGHT-10 );
			}
			
			// display all the edges adjacent to vertex v 
			for ( int u=0; u<maxNoVertices; u++ ) {
				if ( adjMat[v][u] ) {
					int uCol = deltaX + (int) ( u / maxNoVerticesCols ) * deltaX;
					int uRow = deltaY + ( u % maxNoVerticesRows ) * deltaY;
					
					// set color to black
					fill( 0, 0, 0 );
					// set line width to 2
					stroke( 2 );
					// draw edge
					line( vCol, vRow, uCol, uRow );
				}
			}
		}
	}
}

Assignment

• Implement the simple Union-Find algorithm. Implement the version we saw that seems the most logical to you.

• create an array of ints called Id, with for dimension the number of vertices in the network (maxNoVertices).
• Initialize all the cells Id[i] to i.
• Every time initGraph() adds a new edge (v, u) to the network, create the union of v, and u. In other words, if v and u do not have the same Id yet, then set the Id of u to the Id of v (or vice versa).
• When you're done, test your network and figure out if the following vertices are connected:

• 1 and 102 (they should be)
• 5 and 707 (they should be as well)
• 30 and 80 (they should not)