SimBroadband
a.k.a
Graph

Due: April 29, 11:59 pm

1. Installing

Type cs016_install graph into a shell in the directory where you want the project.

2. Reading Requirements

Minimum Spanning Trees
See Section 5.1 on the textbook for information about Minimum Spanning Trees, Kruskal's Algorithm, and Prim's Algorithm

Minimum Spanning Tree provides more information, and pseudocode for Prim-Jarnik and Kruskal.

Graphs
Graphs provides a description of graphs, as well as a graph ADT and information on adjacency matrices.

Decoration
See the Decorator Design Pattern section at the end of this handout for more information on decorations.

3. Visualizer

At minimum, implementation of these methods (in 5.1) is required:

public CS16Vertex[] endVertices(CS16Edge e)

public Iterator<CS16Edge> edges()

public Iterator<CS16Vertex> vertices()

public CS16Vertex opposite(CS16Vertex v, CS16Edge e)

Of course, specific functionality (eg. left clicking on the canvas to insert a vertex) requires that its corresponding method(s) (eg. insertVertex(v)) be implemented as well. Here are methods required for certain Visualizer behavior (that may not be intuitive):

public Iterator<CS16Edge> incidentEdges(CS16Vertex v) to visualize edges

public boolean areAdjacent(CS16Vertex v1, CS16Vertex v2) to disable the visualizer from allowing multiple edges to connect v1 and v2

3.1 User Interaction

LEFT CLICK	ON CANVAS	insert a vertex
LEFT CLICK & DRAG	ON CANVAS	insert a vertex-edge-vertex
LEFT CLICK & DRAG TO A VERTEX v	ON CANVAS	insert a vertex-edge to v
LEFT CLICK	ON VERTEX	select vertex v as v1
MIDDLE CLICK	ON VERTEX	select vertex v as v2
RIGHT CLICK	ON VERTEX	remove vertex & incident edges (if any)
LEFT CLICK	ON EDGE	select edge
RIGHT CLICK	ON EDGE	remove edge

 

areAdjacent(v1, v2)	LEFT CLICK ON A VERTEX TO SELECT IT AS v1
	MIDDLE CLICK ON A VERTEX SELECT IT AS v2
connectingEdge(v1, v2)	LEFT CLICK ON A VERTEX TO SELECT IT AS v1
	MIDDLE CLICK ON A VERTEX SELECT IT AS v2
endVertices(e)	LEFT CLICK ON AN EDGE TO SELECT IT AS e
opposite(v1, e)	LEFT CLICK ON A VERTEX TO SELECT IT AS v1
	LEFT CLICK ON AN EDGE TO SELECT IT AS e
incidentEdges(v1)	LEFT CLICK ON A VERTEX TO SELECT IT AS v1

4. Frontend: SimBroadband

4.1 Description

The frontend, SimBroadband, lets you take charge of a telecommunications company trying to set up communication links between cities throughout the country. To be able to set up shop in a city (by clicking on it), the startup cost associated with that city (its fixed cost) must be less than or equal to your current cash flow

There are two monetary indicators in the top-right corner of the screen. The income from city display shows how much money would be made from connecting that city to your telecommunications network. The fixed costs display shows the startup costs associated with connecting that particular city to your network.

The indicators in the bottom-right corner of the screen display your company's total accounting values. You can see your average income per customer, total income, total fixed costs, total variable costs (the price of keeping your network running), and your total net cash flow, as well as the total distance that your network covers.

SimBroadband uses your implementation of the Kruskal MST algorithm to calculate the most efficient communications network. Please remember to make sure this algorithm is coded correctly before you run SimBroadband!

Have fun turning your regional company into a national communications giant!

4.2 User Interaction

LEFT CLICK	ON LOCATION, NOT YET SERVED	give city broadband service if fixed cost isn't greater than net cash
LEFT CLICK	ON LOCATION, ALREADY SERVED	remove broadband service from city
RIGHT CLICK	ANYWHERE	show/hide the broadband connections between cities

5. Assignment Specifications

Overview

This assignment can be broken down into three main tasks. The first task is to implement a graph by filling in the MyGraph stencil code. The graph you implement will store NodeSequences of vertices and edges, which it updates as new edges and vertices are added to the graph, and uses an adjacency matrix to keep track of the connections between vertices and edges. Your graph will also use the decorator design pattern to give unique identifying markers to the vertices, and keep track of other useful information. See the rest of this handout, the readings, and the MyGraph header comments for more detailed information on this class.

The second task is to implement Kruskal's Algorithm to find a minimum spanning forest for the graph you have created. You will be filling in the genMinSpanForest() method and the cleanup() method. Note that you are not returning a list of edges that make up the minimum spanning forest, you are using the decorator pattern to mark edges that are part of the minimum spanning forest. Take a look at the reading, the MyKruskal header comments and the relevant section of this handout for more information on how Kruskal's Algorithm works.

The third task is to implement a second minimum spanning tree algorithm called the Prim-Jarnik Algorithm. Again, you will be filling in the genMinSpanForest() method and the cleanup() method and making use of the decorator pattern. And, again, please look at all relevant reading for more information on the Prim-Jarnik algorithm.

Stencil Code You Need to Fill In

   
5.1 MyGraph

public MyGraph()
implements AdjacencyMatrixGraph

This class implements a Graph interface that tracks its edges through the use of an adjacency matrix. Specifically, an adjacency matrix consists of an 2D array of edges organized by their end vertices. That is, each vertex of the graph appears in both dimensions; if an edge exists between two vertices, it is indicated in the intersection between them. For example,

V1 V2 V3 V1 null e1 e2 V2 e1 null null V3 e2 null null

Here, edge e1 connects vertices V1 and V2 (and e2 connects V1 and V3).   Note that the main diagonal consists of null's because this is a simple graph (no vertex can have an edge to itself).

To implement said adjacency matrix, give your MyGraph these data structures as instance variables:

private CS16Edge[][] _adjMatrix	2D array of edges
private NodeSequence<CS16Vertex> _vertices	sequence of vertices
private NodeSequence<CS16Edge> _edges	sequence of edges

With this adjacency matrix implementation, each vertex must be associated with a number which represents its index in the matrix's dimensions.

Before reading further: Learn and understand the Decoration design pattern.
Seriously.

Here are some predefined decorations (in the AdjacencyMatrixGraph interface):

VERTEX_NUMBER	to denote vertex 'number'
POSITION	to denote position of both vertices and edges in their respective sequences
FROMVERTEX	to decorate an edge's 'originating' vertex1
TOVERTEX	to decorate an edge's 'destination' vertex

Here is a predefined constant (in the interface):

MAX_VERTICES

to denote an upperbound on the number of vertices the graph

 

 

 

public CS16Vertex insertVertex(Object vertElement)

Insert a new vertex into the graph in O(1) time.

parameter	vertElement	the element of the vertex-to-insert
return value		the inserted vertex

 

public CS16Edge insertEdge(CS16Vertex v1, CS16Vertex v2, Object edgeElement)
throws InvalidVertexException

Insert a new edge into the graph in O(1) time.

parameter	edgeElement	the element of the edge-to-insert
	V1	the first end vertex of the edge
	V2	the second end vertex of the edge
return value		the inserted edge
exception	InvalidVertexException	thrown when either of v1 or v2 is not the expected type or is null

For details on this and all related exceptions, read
support.graph.InvalidEdgeException
support.graph.InvalidVertexException
support.graph.NoSuchEdgeException
support.graph.NoSuchVertexException

 

public Object removeVertex(CS16Vertex v)
throws InvalidVertexException

Remove a vertex from the graph in O(n²) time. (Note that this can be done in O(n).)

parameter	v	the vertex-to-remove
return value		the element of the removed vertex
exception	InvalidVertexException	thrown when v is not the expected type or is null

public Object removeEdge(CS16Edge e)
throws InvalidEdgeException

Remove an edge from the graph in O(1) time.

parameter	e	the edge-to-remove
return value		the element of the removed edge
exception	InvalidEdgeException	thrown when e is not the expected type or is null

public CS16Edge connectingEdge(CS16Vertex v1, CS16Vertex v2)
throws InvalidVertexException, NoSuchEdgeException

Return the edge that connects to two (specified) vertices in O(1) time.

parameter	v1	the first end vertex of the edge
	v2	the second end vertex of the edge
return value		the element of the removed edge
exception	InvalidVertexException	thrown when v is not the expected type or is null
	NoSuchEdgeException	thrown when no edge connects the vertices

public Iterator<CS16Edge> incidentEdges(CS16Vertex v)
throws InvalidVertexException

Return an iterator over all the edges that are incident on (ie, connected to) the specified vertex in O(n) time.

parameter	v	the vertex for which to obtain incidence edges
return value		an iterator over said incident edges
exception	InvalidVertexException	thrown when v is not the expected type or is null

For further information, read
java.util.Iterator

 

public CS16Vertex opposite(CS16Vertex v, CS16Edge e)
throws InvalidVertexException, InvalidEdgeException, NoSuchVertexException

Correct implementation required for Visualizer to work.

Return the vertex at the other end of the specified edge,
where other is defined as opposite the specified vertex, in O(1) time.

parameter	v	a vertex
	e	an edge
return value		the opposite vertex (given the v-e pair specified)
exception	InvalidVertexException	thrown when v is not the expected type or is null
	InvalidEdgeException	thrown when e is not the expected type or is null
	NoSuchVertexException	thrown when no vertex is at the end of (v-e)

public CS16Vertex[] endVertices(CS16Edge e)
throws InvalidEdgeException

Correct implementation required for Visualizer to work.

Return the two vertices at the end of (ie, incident on) the specified edge in O(1) time.

parameter	e	the edge for which to obtain the end vertices
return value		an array said vertices
exception	InvalidEdgeException	thrown when e is not the expected type or is null

public boolean areAdjacent(CS16Vertex v1, CS16Vertex v2)
throws InvalidVertexException

Correct implementation required for Visualizer to work.

Return true if there exists an edge connecting the 2 specified vertices, in O(1) time.

parameter	v1	the first end vertex of the edge
	v2	the second end vertex of the edge
return value		true or false (contingent on adjecency of v1 and v2)
exception	InvalidVertexException	thrown when v is not the expected type or is null

public Iterator<CS16Edge> edges()

Correct implementation required for Visualizer to work.

Return an iterator over all the edges in the graph, in O(m) time,
where m is the number of edges in the graph.

parameter		none
return value		an iterator over all the edges

For further information, read
java.util.Iterator

 

public Iterator<CS16Vertex> vertices()

Correct implementation required for Visualizer to work.

Return an iterator over all the vertices in the graph, in O(n) time,
where n is the number of vertices in the graph.

parameter		none
return value		an iterator over all the vertices

For further information, read
java.util.Iterator

 

 

public void clear()

Clear all the vertices and edges from the graph in O(1) time.

parameter		none
return value		none

   
5.2 MyKruskal

public MyKruskal()
implements MinSpanForest

This class implements a slightly modified version of Kruskal's minimum spanning tree algorithm.

In this implementation, Kruskal's algorithm has been extended to calculate the MST of each connected subgraph of the graph. That is, the algorithm computes the Minimum Spanning Forest (MSF) of a disconnected graph. See the MyMinSpanningForest stencil for elaboration.

public void genMinSpanForest(AdjacencyMatrixGraph g)

Kruskal's algorithm has three phases.

In the first phase, each vertex of the graph is put in its own cloud. Initially, then, there are n of such clouds, where n is the number of vertices in the graph. Consider how to represent a cloud leveraging Java/support data structures; think about the time complexity of insertion into various simple space-efficient data structures.

In the second phase, edges are inserted into a priority queue using the weight of each edge as its key. Here, too, a choice of data structure is entailed. We highly, highly recommend the net.datastructures.HeapPriorityQueue. Consider that insertion and removing the minimum key comprise the functionality required from priority queue. Note that, for this implementation of the algorithm, the 'element' of the edge is an java.lang.Integer storing its weight.

In the third phase, the edge with minimum weight is obtained. If its end vertices belong to different clouds, said clouds are merged. In order that this run in O(nlogn) time, each vertex has to 'know' of which cloud it is a member. To this end, use the decorable pattern; that is, use the predefined CLOUD decoration.

It is important to note that this method does not return the MST. This follows from the fact that there might be several MSTs computed (ie, an MSF). In order to represent that an edge is in an MST, the use of the predefined MST_EDGE decoration is required. Required? Yes. This implementation detail allows the visualizer to correctly recognize and depict an edge as belonging to an MST. This algorithm must run in O((m+n)logn) time.

parameter	g	the graph upon which to perform the algorithm
return value		none

For further information, (definitely) read
support.graph.*

 

 

public void cleanup(AdjacencyMatrixGraph g)

Clean up any decorations that were added to the graph as a result of running the genMinSpanForest(.) algorithm, in O(n+m) time, where n is the number of vertices (in g) and m is the number of edges (in g).

parameter	g	the graph upon which to perform the algorithm
return value		none

   
5.3 MyPrimJarnik

public MyPrimJarnik()
implements MinSpanForest

This class implements a slightly modified version of the Prim-Jarnik minimum spanning tree algorithm.

And, in case you don't yet: Love the Decorator Design Pattern.
You may find the following decorations useful:
TRUE
LOCATOR
DISTANCE
DISCOVERY_EDGE

Enough said.
In this implementation, the Prim-Jarnik algorithm has been extended to calculate the MST of each connected subgraph of the graph. That is, the algorithm computes the Minimum Spanning Forest (MSF) of a disconnected graph. See the MyPrimJarnik stencil for elaboration.

public void genMinSpanForest(AdjacencyMatrixGraph g)

The Prim-Jarnik algorithm has several steps.

We first initialize a decoration that will track the distance of each vertex in the graph from a Minimum spanning tree. There are initially no MST's, so each vertex starts with a distance of "Infinite" (for the purposes of this program, you may use Integer.MAX_VALUE constant as infinite).

Next, we insert all the graph vertices into a priority queue, using each of their distances as a key.

We then remove the vertex with the minimum distance from the priority queue, and "relax" each of that vertex's incident edges. To relax an edge, we examine the distance of the adjacent vertex. If that weight is greater than the connecting edge's weight, and the vertex is not already in a minimum spanning tree, we change that vertex's distance to be the weight of the connecting edge.

IMPORTANT NOTE: This entails modifying the keys of edges already sitting in a priority queue. This means your priority queue will have to be adaptable, like the one you wrote for Heap. We suggest the net.datastructures.SortedListAdaptablePriorityQueue, as funky errors occur if the HeapAdaptablePriorityQueue is used instead.

After all incident edges have been relaxed, we then add the minimum key vertex to the MSF, along with the edge that most recently "relaxed" that vertex (note: there may not be such a vertex).

We continue this process until there are no vertices remaining in the priority queue. As with Kruskal's algorithm, you will *not* be returning a tree. This algorithm must run in O(n² log n) time. Note that this is different than the running time given in the book because we are using an adjacency matrix not an adjacency list.

parameter	g	the graph upon which to perform the algorithm
return value		none

public void cleanup(AdjacencyMatrixGraph g)

Clean up any decorations that were added to the graph as a result of running the genMinSpanForest(.) algorithm, in O(n+m) time, where n is the number of vertices (in g) and m is the number of edges (in g).

parameter	g	the graph upon which to perform the algorithm
return value		none

6. Support Code
Implemented by the TA staff

http://cs16.net/program-docs/graph/

-- or --

/course/cs016/asgn/support/graph/

6.1 Graph

6.1.1 Interfaces

AdjacencyMatrixGraph

This interface is implemented by MyGraph (see 5.1).

MinSpanForest

This interface is implemented by MyKruskal and MyPrimJarnik (see 5.2, 5.3).

6.1.2 Classes

Before proceeding, (definitely) read:
support.graph.CS16Vertex
support.graph.CS16Edge

support.graph.NodeSequence

GraphVertex This class models the vertex in this graph implementation. It implements support.graph.CS16Vertex. Its element is a VizVertex.

GraphEdge This class models the edge in this graph implementation. It implements support.graph.CS16Edge. Its element is a java.lang.Integer.

 

IGNORE the following support classes, as you will not need them:

support.graph.EdgeIterator

support.graph.GraphCanvas

support.graph.GraphViz

support.graph.VizVertex

 

NOTE:  Both GraphVertex and GraphEdge implement the Decorator design pattern. They both define these fields:

private Hashtable decorations_;

public void set(Object key, Object decoration) {

   decorations_.put(key, decoration);

}

public Object get(Object key) {

   return decorations_.get(key);

}

public boolean has(Object key) {

   return decorations_.containsKey(key);

}

public Object destroy(Object key) {

   return decorations_.remove(key);

}

Note that the methods here return values instances of type Object. It follows that casting will often be required. One use of the decorator pattern in MyGraph is to model the relationship between an edge and its end vertices. For example, - FREE CODE HERE -

public Edge insertEdge(Vertex v1, Vertex v2, Object edgeElement) 

   throws InvalidVertexException {

   // handle exception-throwing here

   CS16Edge e = new GraphEdge(edgeElement);

   e.set(FROMVERTEX, v1);

   e.set(TOVERTEX, v2);

   // possibly some other stuff here  

   // return edge here 

}

 

public class City {

   private String _name;
   private int _latitude;
   private int _longitude;

   // accessor and mutator methods here
}

public class ElectionDayCity extends City {

	private Boolean _pollsClosed = false;
	private Integer _numVoters = 0;
	private Integer _population = 0;

	public Boolean arePollsClosed(){
		return _pollsClosed;
	}
	
	public Integer getNumVoters() {
		return _numVoters;
 	}
	
	public void setPopulation(Integer pop){
		_population = pop;
	}
}

public class ElectionDayResults {

	public Boolean arePollsClosed(City city) {

		ElectionDayCity thisCity = (ElectionDayCity) city;
		// handle class-cast exception if thrown
		// ie. try/catch/throw blocks would go here
		
		return thisCity.arePollsClosed();
	}

	public Integer howManyVoted(City city) {
		
		ElectionDayCity thisCity = (ElectionDayCity) city;
		// handle class-cast exception if thrown
		// ie. try/catch/throw blocks would go here
	
		return thisCity.getNumVoters();
	}

	public void setPopulation(Integer pop, City city) {
		
		ElectionDayCity thisCity = (ElectionDayCity) city;
		// handle class-cast exception if thrown
		// ie. try/catch/throw blocks would go here
		
		thisCity.setPopulation(pop);	
	}
}

public class City implements Decorable {

	private String _name;
	private int _latitude;
	private int _longitude;

	// accessor and mutator methods here
}

public interface jdsl.core.api.Decorable {

	public void set(Object key, Object decoration);
	public Object get(Object key);
	public boolean has(Object key);
	public Object destroy(Object key);

}

public class ElectionDayResults {

	public static final Object POLLS_CLOSED = new Object();
	
	public static final Object VOTER_COUNT = new Object();

	public static final Object POPULATION = new Object();

	public void setPopulation(Integer pop, City city) {
		city.set(POPULATION, pop);	
	}

	public Boolean arePollsClosed(City city) {
  		return (Boolean)city.get(POLLS_CLOSED);
 	}
	
 	public Integer howManyVoted(City city) {
  		if(city.has(POLLS_CLOSED)) {
   			return (Integer)city.get(VOTER_COUNT);
  		}
 	}
 	// etc.
}