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 );
}
}
}
}