CSC212 Lab 14 Solution Program 2014

--D. Thiebaut (talk) 16:42, 30 November 2014 (EST)

---

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 Lab14_MazeNetworkUnionFind 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
	private int Id[] = null;
	
	// record mouse clicks
	int vertexClicked = 0;
	int lastVertexClicked = 0;
	String bottomLine = "Click on a vertex!";
	
	/**
	 * 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;
		union( u, v );
	}
	
	/**
	 * 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];

		// initialize Union-Find Id array
		Id     = new int[maxNoVertices];
		for ( int i=0; i<maxNoVertices; i++ )
			Id[i] = i;

		// initialize adjMat
		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 );
			}
		}
		
	}
	
	private int idOf( int v ) {
		if ( Id[v] == v )
			return v;
		while ( Id[v] != v )
			v = Id[v];
		return v;
	}
	
	private void union( int v, int u ) {
		int id_v = idOf( v );
		int id_u = idOf( u );
		if ( id_v == id_u ) 
			return;
		Id[ id_v ] = id_u;
	}
	
	private boolean find( int v, int u ) {
		return idOf( v ) == idOf( u );
	}
	
	/**
	 * 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...
		fill( 100, 100, 100 );
		background( 255, 255, 255 );
		
		text( bottomLine, 300, HEIGHT-10 );
		// display each vertex and its adjacent edges..
		for ( int v=0; v<maxNoVertices; v++ ) {
			int vx = deltaX + (int) ( v / maxNoVerticesCols ) * deltaX;
			int vy = deltaY + ( v % maxNoVerticesRows ) * deltaY;
			
			// draw black circle for the vertex 
			ellipse( vy, vx, 4, 4 );
			
			// is mouse pointer inside this vertex?  If so, display some
			// information about this vertex
			if ( dist( vx, vy, mouseX, mouseY ) < 4 ) {
				fill( 255, 0 , 0 );
				text( v+" ", vx, vy );
				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( vx, vy, uCol, uRow );
				}
			}
		}
	}
	
	public void mouseClicked() {
		// loop through all the vertices and figure out which one is closest
		// to mouse pointer
		text( "Click!", 50, HEIGHT-10 );
		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, display some
			// information about this vertex
			if ( dist( vCol, vRow, mouseX, mouseY ) < 5 ) {
				lastVertexClicked = vertexClicked;
				vertexClicked = v;
				fill( 0, 255 , 0 ); // green
				if ( find( lastVertexClicked, vertexClicked ) ) 
					bottomLine = String.format( "%d and %d are connected",
								lastVertexClicked, vertexClicked );
				else
					bottomLine = String.format( "%d and %d are NOT connected",
							lastVertexClicked, vertexClicked );
				System.out.println( bottomLine );
			}
		}
	}
}