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