//Need to finish the AdjacencyMatrixGraph class

package graphs;

import java.util.ArrayList;

import java.util.HashMap;

import java.util.Iterator;

import java.util.List;

import java.util.Map;

import java.util.NoSuchElementException;

import java.util.Set;

public class AdjacencyMatrixGraph extends Graph {

Map keyToIndex;

List indexToKey;

int[][] matrix;

AdjacencyMatrixGraph(Set keys) {

int size = keys.size();

this.keyToIndex = new HashMap();

this.indexToKey = new ArrayList();

this.matrix = new int[size][size];

// need to populate keyToIndex and indexToKey with info from keys

}

@Override

public int size() {

return this.matrix.length;

}

@Override

public int numEdges() {

int count = 0;

for (int i = 0; i < matrix.length; i++) {

for (int j = 0; j < matrix[i].length; j++) {

count += matrix[i][j];

}

}

return count;

}

@Override

public boolean addEdge(T from, T to) {

// TODO Auto-generated method stub

return false;

}

@Override

public boolean hasVertex(T key) {

// TODO Auto-generated method stub

return false;

}

@Override

public boolean hasEdge(T from, T to) throws NoSuchElementException {

// TODO Auto-generated method stub

return false;

}

@Override

public boolean removeEdge(T from, T to) throws NoSuchElementException {

// TODO Auto-generated method stub

return false;

}

@Override

public int outDegree(T key) {

// TODO Auto-generated method stub

return 0;

}

@Override

public int inDegree(T key) {

// TODO Auto-generated method stub

return 0;

}

@Override

public Set vertexSet() {

// TODO Auto-generated method stub

return null;

}

@Override

public List successorList(T key) {

// TODO Auto-generated method stub

return null;

}

@Override

public List predecessorList(T key) {

// TODO Auto-generated method stub

return null;

}

@Override

public Iterator successorIterator(T key) {

// TODO Auto-generated method stub

return null;

}

@Override

public Iterator predecessorIterator(T key) {

// TODO Auto-generated method stub

return null;

}

@Override

public Set stronglyConnectedComponent(T key) {

// TODO Auto-generated method stub

return null;

}

@Override

public List shortestPath(T startLabel, T endLabel) {

// TODO Auto-generated method stub

return null;

}

}

//TESTS

package graphs;

import static org.junit.Assert.assertEquals;

import static org.junit.Assert.assertFalse;

import static org.junit.Assert.assertTrue;

import static org.junit.Assert.fail;

import java.util.Arrays;

import java.util.HashSet;

import java.util.Iterator;

import java.util.List;

import java.util.NoSuchElementException;

import java.util.Set;

import org.junit.AfterClass;

import org.junit.Test;

/**

* Complete test cases for Milestone 1

*

*

* @author Nate Chenette

*

*/

public class GraphSurfingMilestone1Test {

private static int m1points = 0;

private static int m1weight = 2;

private static final int MAX_POINTS = 100;

// MILESTONE 1

// Implement the following methods first:

// - the constructor taking a Set of data

// - the addEdge method

private Set getThreeVerticesToAdd() {

HashSet toInsert = new HashSet();

toInsert.add("a");

toInsert.add("b");

toInsert.add("c");

return toInsert;

}

@Test

public void testALConstructorAndSize() {

Graph g = new AdjacencyListGraph(new HashSet()); // create empty graph

assertEquals(0, g.size());

g = new AdjacencyListGraph(getThreeVerticesToAdd()); // create graph with three vertices

assertEquals(3, g.size());

m1points += 3*m1weight;

}

@Test

public void testAMConstructorAndSize() {

Graph g = new AdjacencyMatrixGraph(new HashSet()); // create empty graph

assertEquals(0, g.size());

g = new AdjacencyMatrixGraph(getThreeVerticesToAdd()); // create graph with three vertices

assertEquals(3, g.size());

m1points += 3*m1weight;

}

private void helperTestAddEdge(Graph g) {

g.addEdge("a", "b");

assertEquals(true,g.addEdge("b", "c"));

m1points += 2*m1weight;

assertEquals(false,g.addEdge("b", "c"));

try {

g.addEdge("b", "d");

fail("Did not throw NoSuchElementException");

} catch (Exception e) {

if (!(e instanceof NoSuchElementException)) {

fail("Did not throw NoSuchElementException");

}

}

m1points += m1weight;

}

@Test

public void testALAddEdge() {

Graph g = new AdjacencyListGraph(getThreeVerticesToAdd()); // create graph with three vertices

helperTestAddEdge(g);

}

@Test

public void testAMAddEdge() {

Graph g = new AdjacencyMatrixGraph(getThreeVerticesToAdd()); // create graph with three vertices

helperTestAddEdge(g);

}

// The following tests will work once the following are implemented correctly, for each graph

// implementation:

// - the constructor taking a Set of data

// - the addEdge method

private Set getExampleVertexData() {

String[] toInsert = {"a","b","c","d","e","f"};

HashSet items = new HashSet();

for (String str : toInsert) {

items.add(str);

}

return items;

}

private Set getExample2VertexData() {

Integer[] toInsert = {0,1,2,3,4,5,6};

HashSet items = new HashSet();

for (Integer i : toInsert) {

items.add(i);

}

return items;

}

private void addExampleEdges(Graph g) {

g.addEdge("a", "b");

g.addEdge("a", "c");

g.addEdge("b", "d");

g.addEdge("c", "d");

g.addEdge("d", "c");

g.addEdge("d", "e");

g.addEdge("d", "f");

g.addEdge("f", "c");

}

private void addExample2Edges(Graph g) {

g.addEdge(0, 1);

g.addEdge(1, 0);

g.addEdge(0, 2);

g.addEdge(2, 3);

g.addEdge(2, 4);

g.addEdge(3, 4);

g.addEdge(4, 5);

g.addEdge(4, 6);

g.addEdge(6, 2);

}

public Graph makeExampleALGraph() {

Graph g = new AdjacencyListGraph(getExampleVertexData());

addExampleEdges(g);

return g;

}

public Graph makeExample2ALGraph() {

Graph g = new AdjacencyListGraph(getExample2VertexData());

addExample2Edges(g);

return g;

}

public Graph makeExampleAMGraph() {

Graph g = new AdjacencyMatrixGraph(getExampleVertexData());

addExampleEdges(g);

return g;

}

public Graph makeExample2AMGraph() {

Graph g = new AdjacencyMatrixGraph(getExample2VertexData());

addExample2Edges(g);

return g;

}

private void helperTestHasEdge(Graph g, Graph g2) {

assertTrue(g.hasEdge("a","b"));

assertTrue(g.hasEdge("f","c"));

assertFalse(g.hasEdge("b","c"));

assertFalse(g.hasEdge("b","a"));

assertTrue(g2.hasEdge(0,2));

assertTrue(g2.hasEdge(4,6));

assertFalse(g2.hasEdge(2,5));

assertFalse(g2.hasEdge(2,6));

m1points += m1weight;

try {

g.hasEdge("a", "g"); // g not in graph

fail("Did not throw NoSuchElementException");

} catch (Exception e) {

if (!(e instanceof NoSuchElementException)) {

fail("Did not throw NoSuchElementException");

}

}

try {

g2.hasEdge(10, 5); // 10 not in graph

fail("Did not throw NoSuchElementException");

} catch (Exception e) {

if (!(e instanceof NoSuchElementException)) {

fail("Did not throw NoSuchElementException");

}

}

m1points += m1weight;

}

@Test

public void testALHasEdge() {

helperTestHasEdge(makeExampleALGraph(),makeExample2ALGraph());

}

@Test

public void testAMHasEdge() {

helperTestHasEdge(makeExampleAMGraph(),makeExample2AMGraph());

}

@Test

public void testALNumEdges() {

Graph g = makeExampleALGraph();

assertEquals(8, g.numEdges());

Graph g2 = makeExample2ALGraph();

assertEquals(9, g2.numEdges());

m1points += 1.5*m1weight;

}

@Test

public void testAMNumEdges() {

Graph g = makeExampleAMGraph();

assertEquals(8, g.numEdges());

Graph g2 = makeExample2AMGraph();

assertEquals(9, g2.numEdges());

m1points += 1.5*m1weight;

}

private void helperTestInDegree(Graph g) {

assertEquals(0, g.inDegree("a"));

assertEquals(1, g.inDegree("b"));

assertEquals(3, g.inDegree("c"));

assertEquals(2, g.inDegree("d"));

assertEquals(1, g.inDegree("e"));

assertEquals(1, g.inDegree("f"));

m1points += 1.5*m1weight;

}

@Test

public void testALInDegree() {

helperTestInDegree(makeExampleALGraph());

}

@Test

public void testAMInDegree() {

helperTestInDegree(makeExampleAMGraph());

}

private void helperTestOutDegree(Graph g) {

assertEquals(2, g.outDegree("a"));

assertEquals(1, g.outDegree("b"));

assertEquals(1, g.outDegree("c"));

assertEquals(3, g.outDegree("d"));

assertEquals(0, g.outDegree("e"));

assertEquals(1, g.outDegree("f"));

m1points += 1.5*m1weight;

}

@Test

public void testALOutDegree() {

helperTestOutDegree(makeExampleALGraph());

}

@Test

public void testAMOutDegree() {

helperTestOutDegree(makeExampleAMGraph());

}

private void helperTestHasVertex(Graph g, Graph g2) {

assertTrue(g.hasVertex("a"));

assertTrue(g.hasVertex("f"));

assertFalse(g.hasVertex("g"));

assertTrue(g2.hasVertex(0));

assertTrue(g2.hasVertex(6));

assertFalse(g2.hasVertex(7));

m1points += m1weight;

}

@Test

public void testALHasVertex() {

helperTestHasVertex(makeExampleALGraph(),makeExample2ALGraph());

}

@Test

public void testAMHasVertex() {

helperTestHasVertex(makeExampleAMGraph(),makeExample2AMGraph());

}

private void helperTestVertexSet(Graph g, Graph g2) {

assertEquals(getExampleVertexData(),g.vertexSet());

assertEquals(getExample2VertexData(),g2.vertexSet());

m1points += m1weight;

}

@Test

public void testALVertexSet() {

helperTestVertexSet(makeExampleALGraph(),makeExample2ALGraph());

}

@Test

public void testAMVertexSet() {

helperTestVertexSet(makeExampleAMGraph(),makeExample2AMGraph());

}

private void helperTestRemoveEdge(Graph g) {

assertTrue(g.hasEdge("a", "b"));

g.removeEdge("a","b");

assertFalse(g.hasEdge("a", "b"));

assertTrue(g.hasEdge("f", "c"));

assertTrue(g.removeEdge("f","c"));

assertFalse(g.hasEdge("f", "c"));

assertFalse(g.hasEdge("f", "c"));

assertFalse(g.removeEdge("b","c"));

assertFalse(g.hasEdge("f", "c"));

m1points += m1weight;

try {

g.removeEdge("a", "g"); // g not in graph

fail("Did not throw NoSuchElementException");

} catch (Exception e) {

if (!(e instanceof NoSuchElementException)) {

fail("Did not throw NoSuchElementException");

}

}

m1points += m1weight;

}

@Test

public void testALRemoveEdge() {

helperTestRemoveEdge(makeExampleALGraph());

}

@Test

public void testAMRemoveEdge() {

helperTestRemoveEdge(makeExampleAMGraph());

}

private void helperTestSuccessorList(Graph g) {

assertEquals(Arrays.asList("d"),g.successorList("b"));

assertEquals(Arrays.asList(),g.successorList("e"));

List answer = Arrays.asList("c","e","f");

List obtained = g.successorList("d");

assertTrue(answer.containsAll(obtained) && obtained.containsAll(answer));

m1points += 1.5*m1weight;

}

@Test

public void testALSuccessorList() {

helperTestSuccessorList(makeExampleALGraph());

}

@Test

public void testAMSuccessorList() {

helperTestSuccessorList(makeExampleAMGraph());

}

private void helperTestSuccessorIterator(Graph g) {

Iterator it = g.successorIterator("b");

assertTrue(it.hasNext());

assertEquals("d",it.next());

assertFalse(it.hasNext());

m1points += m1weight;

it = g.successorIterator("d");

Set returned = new HashSet();

Set expected = new HashSet();

expected.add("c");

expected.add("e");

expected.add("f");

while (it.hasNext()) {

returned.add(it.next());

}

assertEquals(expected, returned);

m1points += m1weight;

}

@Test

public void testALSuccessorIterator() {

helperTestSuccessorIterator(makeExampleALGraph());

}

@Test

public void testAMSuccessorIterator() {

helperTestSuccessorIterator(makeExampleAMGraph());

}

@Test

public void testALSuccessorIteratorIsLazy() {

int numVertices = 10000;

Set vertexSet = new HashSet();

for (int i = 0; i < numVertices; i++) {

vertexSet.add(i); // add 10000 vertices

}

Graph g = new AdjacencyListGraph(vertexSet);

for (int j = 0; j < numVertices; j++) {

g.addEdge(0, j); // add edges from 0 to all other vertices

}

// Run the speed test for iterator construction and first next()

long startTime = System.currentTimeMillis();

Iterator it = g.successorIterator(0);

it.next();

long endTime = System.currentTimeMillis();

long time = endTime - startTime;

System.out.printf("AdjList SuccessorIterator time for construction and first "

+ "next: %3d ms%n",time);

assertTrue(time < 5); // creating the lazy iterator and running next() once

// should be instantaneous.

m1points += 2*m1weight;

}

@Test

public void testAMSuccessorIteratorIsLazy() {

int numVertices = 10000;

Set vertexSet = new HashSet();

for (int i = 0; i < numVertices; i++) {

vertexSet.add(i); // add 10000 vertices

}

Graph g = new AdjacencyMatrixGraph(vertexSet);

for (int j = 0; j < numVertices; j++) {

g.addEdge(0, j); // add edges from 0 to all other vertices

}

// Run the speed test for iterator construction and first next()

long startTime = System.currentTimeMillis();

// Repeat the following 100 times to make sure inefficiency is apparent

for (int i = 0; i < 100; i++) {

Iterator it = g.successorIterator(0);

it.next();

}

long endTime = System.currentTimeMillis();

long time = endTime - startTime;

System.out.printf("AdjMatrix SuccessorIterator time for (100x) construction and first "

+ "next: %3d ms%n",time);

assertTrue(time < 5); // creating the lazy iterator and running next() once

// should be instantaneous.

m1points += 2*m1weight;

}

private long helperTestRelativeSpeedforAddRemoveEdge(Graph g, int numVertices) {

long startTime = System.currentTimeMillis();

// Add edges everywhere

for (int i = 0; i < numVertices; i++) {

for (int j = 0; j < numVertices; j++) {

assertFalse(g.hasEdge(i, j));

g.addEdge(i, j);

assertTrue(g.hasEdge(i, j));

}

}

// Remove edges everywhere

for (int i = 0; i < numVertices; i++) {

for (int j = 0; j < numVertices; j++) {

assertTrue(g.hasEdge(i, j));

g.removeEdge(i, j);

assertFalse(g.hasEdge(i, j));

}

}

long endTime = System.currentTimeMillis();

return (endTime - startTime);

}

@Test

public void testRelativeSpeedforRemoveEdge() {

int numVertices = 600;

Set vertexSet = new HashSet();

for (int i = 0; i < numVertices; i++) {

vertexSet.add(i);

}

Graph gAL = new AdjacencyListGraph(vertexSet);

Graph gAM = new AdjacencyMatrixGraph(vertexSet);

long timeAL = helperTestRelativeSpeedforAddRemoveEdge(gAL,numVertices);

long timeAM = helperTestRelativeSpeedforAddRemoveEdge(gAM,numVertices);

System.out.printf("RemoveEdges speed test: %4d ms for AdjList, "

+ "%4d ms for AdjMatrix%n",timeAL,timeAM);

// Would expect AdjList to be at least twice as slow at this task.

assertTrue(timeAL > 2*timeAM);

m1points += 3*m1weight;

}

private long helperTestRelativeSpeedforOutDegree(Graph g, int numVertices) {

long startTime = System.currentTimeMillis();

// Start with the empty graph

for (int i = 0; i < numVertices; i++) {

for (int j = 0; j < numVertices; j++) {

if (j == i + 1) {

g.addEdge(i, j); // add one edge for each vertex, at a specific point,

// to get a bit of variety in the out-degrees

}

// main test: out-degree calculation

assertEquals(((j >= i + 1) ? 1 : 0), g.outDegree(i));

}

}

long endTime = System.currentTimeMillis();

return (endTime - startTime);

}

@Test

public void testRelativeSpeedforOutDegree() {

int numVertices = 800;

Set vertexSet = new HashSet();

for (int i = 0; i < numVertices; i++) {

vertexSet.add(i);

}

Graph gAL = new AdjacencyListGraph(vertexSet);

Graph gAM = new AdjacencyMatrixGraph(vertexSet);

long timeAL = helperTestRelativeSpeedforOutDegree(gAL,numVertices);

long timeAM = helperTestRelativeSpeedforOutDegree(gAM,numVertices);

System.out.printf("OutDegree speed test: %4d ms for AdjList, "

+ "%4d ms for AdjMatrix%n",timeAL,timeAM);

// Would expect AdjMatrix to be at least twice as slow at this task.

assertTrue(timeAM > 2*timeAL);

m1points += 3*m1weight;

}

@AfterClass

public static void printSummary() {

System.out.print(" =============== ");

System.out.print("Total points: ");

System.out.print(m1points + "/" + MAX_POINTS);

System.out.println(" ===============");

}

}