CSC212 Lab 15 Solution 2014

--D. Thiebaut (talk) 11:22, 5 December 2014 (EST)

---

The text of Lab 15 is available here. You need to setup Eclipse to work with Processing to make the code below work.

Model

import java.util.ArrayList;
import java.util.Random;

import processing.core.PApplet;

/**
 * Model component of Model-View-Controller system. Implements the graph, holds
 * the vertices (numbered 0 to maxNoVertices) and keeps the edges in a boolean
 * adjacency matrix, that is maxNoVertices x maxNoVertices;
 * 
 * @author D. Thiebaut
 *
 */

public class Lab15_Model  {
	private final int maxNoVerticesRows = 50; // geometry
	private final int maxNoVerticesCols = 50; // 50 x 50 grid = 2500 vertices
												// total
	private int maxNoVertices = maxNoVerticesRows * maxNoVerticesCols;
	private boolean[] visited;
	private boolean[][] adjMat = null; // adjacency matrix
	private int probability100 = 35; // probability (as percentage) for an edge
										// (35 means 35%)

	private Lab15_Viewer viewer = null;// reference to the viewer of the MVC
										// system
	private Lab15_Controller controller = null;// reference to the controller of
												// the MVC system
	
	/**
	 * constructor. Nothing to do. The building of the network is done by
	 * initGraph().
	 */
	public Lab15_Model() {
	}

	/**
	 * mutator. Sets the reference to the controller.
	 * 
	 * @param c
	 */
	public void setController(Lab15_Controller c) {
		controller = c;
	}

	/**
	 * mutator. Sets the reference to the viewer.
	 * 
	 * @param v
	 */
	public void setViewer(Lab15_Viewer v) {
		viewer = v;
	}

	/**
	 * accessor
	 * 
	 * @return number of vertices in graph
	 */
	public int getNoVertices() {
		return maxNoVertices;
	}

	public int getNoCols() {
		return maxNoVerticesCols;
	}

	public int getNoRows() {
		return maxNoVerticesRows;
	}

	/**
	 * 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;
	}

	/**
	 * returns vertex at given row and col. Assumes row & col will always be
	 * valid.
	 * 
	 * @param row
	 * @param col
	 * @return the vertex at row, col
	 */
	private int vertexAtRowCol(int row, int col) {
		return row + col * maxNoVerticesRows;
	}

	/**
	 * 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];
		visited = new boolean[maxNoVertices]; // automatically initialized to false
		
		for (int r = 1; r < maxNoVerticesRows; r++) {
			for (int c = 1; c < maxNoVerticesCols; c++) {
				int currentVertex = vertexAtRowCol(r, c);
				int upVertex = vertexAtRowCol(r - 1, c);
				int leftVertex = vertexAtRowCol(r, 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 the adjacency list of Vertex v in an arrayList.
	 * 
	 * @param v
	 *            for which we want the adjacent vertices.
	 * @return an arrayList of vertices. The vertices numbers are listed in
	 *         increasing order.
	 */
	public ArrayList<Integer> adjList(int v) {
		ArrayList<Integer> adj = new ArrayList<Integer>();
		for (int u = 0; u < maxNoVertices; u++)
			if (adjMat[v][u])
				adj.add(u);
		return adj;
	}
	
	/**
	 * executes a DFS starting on Vertex v 
	 * @param vertex
	 */
	public void DFS( int vertex ) {
		visited = new boolean[ maxNoVertices ];
		recurseDFS( vertex );
	}
	
	/**
	 * recursively visit vertex v and all the vertices u adjacent to v
	 * @param v
	 */
	private void recurseDFS( int v ) {
		//System.out.println( "recurseDFS on " + v );
		visited[v] = true;
		for ( int u: adjList( v ) ) 
			if ( !visited[u] )
				recurseDFS( u );
	}

	public boolean isVisited(int v) {
		return visited[v];
	}

}

Controller

/**
 * MVC1_controller. The controller of a simple Model-View-Controller (MVC)
 * system. The MVC system displays a 50x50 network of vertices with left, right,
 * up, and down edges to their neighbors. The controller is started by the
 * viewer, which extends PApplet, and which is the first object to become alive.
 * The controller starts the model which initializes the graph. Every graphical
 * interaction in the viewer is passed on to the controller.
 * 
 * @author D. Thiebaut
 *
 */

public class Lab15_Controller {
	// links to the viewer and model.
	Lab15_Viewer viewer = null;
	Lab15_Model model = null;

	/**
	 * constructor.
	 */
	public Lab15_Controller() {
	}

	/**
	 * mutator
	 * 
	 * @param v
	 *            reference to the viewer
	 */
	public void setViewer(Lab15_Viewer v) {
		viewer = v;
	}

	/**
	 * mutator
	 * 
	 * @param m
	 *            reference to the model
	 */
	public void setModel(Lab15_Model m) {
		model = m;
	}

	/**
	 * launched by the viewer, which passes a reference to itself in the
	 * process. Creates a set of references between the model, the view, and the
	 * controller. Initializes the graph held by the model (vertices and edges)
	 * 
	 * @param v
	 *            reference to the viewer.
	 */
	public void initAll(Lab15_Viewer v) {
		// init viewer
		viewer = v;

		// create the model
		model = new Lab15_Model();

		// create reference system between MVC components
		model.setController(this);
		viewer.setModel(model);
		model.setViewer(viewer);

		// create the graph of vertices and edges
		model.initGraph();
	}

	/**
	 * called by viewer when the mouse is over a given vertex. decides what
	 * viewer should do, depending on different modes of operation.
	 * 
	 * @param vertex
	 */
	public void setVertexUnderMouse(int vertex) {
		// ask model to perform a DFS on vertex
		model.DFS( vertex );
		
		// display vertex name
		//viewer.displayVertexName(vertex);
		viewer.drawCircles( vertex );
		// display adjacency list
		viewer.displayAdjacencyList(vertex);
	}

}

Viewer

import java.util.ArrayList;
import processing.core.PApplet;

/**
 * The viewer class of a simple Model-View-Controller (MVC) system. The MVC
 * system displays a 50x50 network of vertices with left, right, up, and down
 * edges to their neighbors. This class is the main class, as it extends
 * PApplet, which will automatically call setup() on start-up, and will
 * repeatedly call draw(), 30 times a second. Constantly redraws the network of
 * vertices and edges held by the model, 30 times a second. Passes special
 * conditions to the controller for decision. For example, when the mouse is
 * over a vertex, or when the mouse is clicked somewhere on the canvas of the
 * applet.
 * 
 * @author D. Thiebaut
 *
 */

public class Lab15_Viewer extends PApplet {

	Lab15_Controller controller = null;
	Lab15_Model model = null;
	public int WIDTH = 800; // best generic width
	public int HEIGHT = 800; // best generic height
	private final int DELTAX = 10; // no pixels between vertices
	private final int DELTAY = 10; // no pixels between vertices
	private int MINDIST = 5; // min dist for vertex detected
	private int vertexUnderMouse = -1;
	private Button button1;

	// as under mouse pointer
	/**
	 * mutator: sets a reference to the model.
	 * 
	 * @param m
	 *            reference to the model
	 */
	public void setModel(Lab15_Model m) {
		model = m;
	}

	/**
	 * helper function. Given a vertex number, returns its position (x, y) on
	 * applet canvas. Vertex 0 will be at (DELTAX, DELTAY).
	 * 
	 * @param vertex
	 *            the vertex to position
	 * @param noRows
	 *            the number of rows in the network
	 * @param noCols
	 *            the number of columns in the network
	 * @return an int array. xy[0] is x, xy[1] is y. In pixels.
	 */
	private int[] getXY(int vertex, int noRows, int noCols) {
		int[] xy = new int[2];
		xy[0] = DELTAX + (int) (vertex / noRows) * DELTAX;
		xy[1] = DELTAY + (vertex % noRows) * DELTAY;
		return xy;
	}

	/**
	 * computes the number of vertex located at location (row, col).
	 * 
	 * @param row
	 * @param col
	 * @return the number (int) of the vertex.
	 */
	private int vertexAtRowCol(int row, int col) {
		int v = row + col * model.getNoRows();
		if (v < 0 || v > model.getNoVertices())
			return -1;
		return v;
	}

	/**
	 * the entry point for the MVC system. The PApplet will automatically call
	 * setup() first. This is the place that initializes everything up,
	 * including controller and model. Gets the controller to link the 3 systems
	 * together. The controller will initialize the model with the graph.
	 */
	public void setup() {
		// --- create model and controller, create reference ---
		// --- system between all three. ---
		controller = new Lab15_Controller();
		controller.initAll(this);

		// --- make window fit model graph exactly ---
		// --- add blank area of 30 pixels high at bottom ---
		// DELTAX = round( WIDTH / (model.getNoCols() + 1 ) );
		// DELTAY = round( HEIGHT / (model.getNoRows() + 1 ) );
		WIDTH = DELTAX * (model.getNoCols() + 1);
		HEIGHT = 30 + DELTAY * (model.getNoRows() + 1);

		// setup button1
		button1 = new Button(this, 10, HEIGHT - 25, "Magic Button");

		// --- set Applet geometry ---
		size(WIDTH, HEIGHT);
		smooth();
	}

	/**
	 * return the vertex that is within MINDIST pixels of the current mouse
	 * location.
	 * 
	 * @return the vertex number, or -1 if none found.
	 */
	public int closestVertexToMouse() {
		int row = round((mouseY - DELTAY) / DELTAY);
		int col = round((mouseX - DELTAX) / DELTAX);
		int v = vertexAtRowCol(row, col);
		if (v == -1)
			return -1;
		int[] xy = getXY(v, model.getNoRows(), model.getNoCols());
		if (dist(xy[0], xy[1], mouseX, mouseY) < MINDIST)
			return v;
		return -1;
	}

	/**
	 * draw() is called automatically 30 times a second by mechanism inside the
	 * PApplet that is hidden from the programmer. The role of draw() is to
	 * erase the screen (too fast for the user to notice) and redraw the graph
	 * with vertices and edges, and whatever text needs to be displayed on the
	 * canvas. Detects if the mouse pointer is over a vertex and if so, calls
	 * the controller to decide what should be done in this case.
	 */
	public void draw() {
		// erase window, make background white
		background(255, 255, 255);

		// draw button
		button1.draw();

		// get geometry of grid
		int V = model.getNoVertices();
		int noRows = model.getNoRows();
		int noCols = model.getNoCols();

		// if mouse just over a vertex, tell controller
		// so that specific action can be taken.
		vertexUnderMouse = closestVertexToMouse();
		if (vertexUnderMouse != -1)
			controller.setVertexUnderMouse(vertexUnderMouse);

		// draw larger colored circles for the vertices visited by the last DFS
		fill(255, 204, 0);       // orange interior color 
		stroke(255, 204, 0); // orange outline
		for (int v = 0; v < V; v++) {
			if (!model.isVisited(v))
				continue;

			// get coordinates of Vertex v
			int[] xy = getXY(v, noRows, noCols);

			// draw orange disk for Vertex v
			ellipse(xy[0], xy[1], 8, 8);
		}

		// draw the vertices and edges
		fill(0, 0, 0); // make vertices black
		stroke(0, 0, 0);
		strokeWeight(2); // make line width 2 pixels

		for (int v = 0; v < V; v++) {
			// get coordinates of Vertex v
			int[] xy = getXY(v, noRows, noCols);

			// draw black disk for Vertex v
			ellipse(xy[0], xy[1], 4, 4);

			// get adjacency list for each vertex and display edges
			if (button1.isON())
				for (int u : model.adjList(v)) {
					int[] xy2 = getXY(u, noRows, noCols);
					line(xy[0], xy[1], xy2[0], xy2[1]);
				}
		}
	}

	/**
	 * displays the vertex number next to the circle representing it. This is
	 * typically done whenever the mouse pointer is over a vertex.
	 * 
	 * @param vertexNo
	 */
	public void displayVertexName(int vertexNo) {
		// get position of vertex
		int[] xy = getXY(vertexNo, model.getNoRows(), model.getNoCols());
		// set text color to red
		fill(255, 0, 0);
		// display text
		text(" " + vertexNo, xy[0], xy[1]);
	}

	public void displayAdjacencyList(int vertexNo) {
		String s = "";
		for (int u : model.adjList(vertexNo))
			s += u + ", ";
		// remove last ", " part of the string
		s = s.trim();
		if (s.length() > 0)
			s = s.substring(0, s.length() - 1);
		text(s, 100, HEIGHT - 25);
	}

	static boolean upDown = true;
	static int radius = 0;

	public void drawCircles(int vertexNo) {
		int[] xy = getXY(vertexNo, model.getNoRows(), model.getNoCols());
		if (frameCount % 10 == 9)
			upDown = !upDown;

		if (upDown)
			radius = min(10, radius + 1);
		else
			radius = max(0, radius - 1);

		stroke(255, 0, 0);
		fill(255, 0, 0);
		ellipse(xy[0], xy[1], 2 * radius, 2 * radius);
	}

	public void mouseClicked() {
		// System.out.println( "Mouse clicked at "+mouseX + ", " + mouseY );
		if (button1.containsMouse()) {
			button1.switchState();
		}
	}
}