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).
• Study it well. Make sure you have read the code, and figured out what the different methods do.
• 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 = deltaX + (int) ( v / maxNoVerticesCols ) 	* deltaX;
			int vRow = deltaY + ( v % maxNoVerticesRows ) 		* deltaY;
			
			// 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 );
				}
			}
		}
	}
}

Note: If you would like to test this graph in a different, simpler java program, the collection of edges is available as a series of addEdge( u, v ) statements on this page.

Problem #1: Adding Union-Find

• 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 how to make your program tell you 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)

Note: Even though you are dealing with a graphic applet, you can still use System.out.println() to print in the console.

Problem #2: Adding User-Interaction

Wouldn't it be nice if the user could click on 2 vertices and have the program indicate whether they are connected or not?
That's what this section is about.

Some Modifications

• Add the following member variables to your class:

        // Keep track of which vertices are clicked
	int vertexClicked = 0;
	int lastVertexClicked = 0;
	String bottomLine = "Click on a vertex!";    // is constantly displayed at bottom of applet

• Add this new method to your class. This method is automatically called by the applet mother class whenever you click the mouse pointer over the applet. The coordinates of the mouse (mouseX, mouseY) are maintained by the mother class, and can be accessed by your program to figure out the location where the mouse was clicked.

         public void mouseClicked() {
		// loop through all the vertices and figure out which one is closest
		// to mouse pointer
		for ( int v=0; v<maxNoVertices; v++ ) {
			int vCol = deltaY + (int) ( v / maxNoVerticesCols ) 	* deltaY;
			int vRow = deltaX + ( v % maxNoVerticesRows ) 		* deltaX;
		
			// is mouse pointer inside this vertex?  If so, record that v is
                        // the vertex that was clicked on.  Keep track of the vertex that was
                        // clicked before that.
			if ( dist( vCol, vRow, mouseX, mouseY ) < 5 ) {
				lastVertexClicked = vertexClicked;
				vertexClicked = v;
				bottomLine = String.format( "last clicked = %d current clicked = %d",
						lastVertexClicked, vertexClicked );
			}
		}
	}

• Modify the beginning of draw() and add the new highlighted line below.

         public void draw() {
		// clear screen, make it white...
		background( 255, 255, 255 );
		
		text( bottomLine, 300, HEIGHT-10 );
                ...