//NEED TO DEAL WITH stronglyConnectedComponent method find the strongly connected component with the vertex with the key.

package graphs;

import java.util.ArrayList; import java.util.HashMap; import java.util.HashSet; 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 for (T each : keys) { this.indexToKey.add(each); } for (int i = 0; i < size; i++) { this.keyToIndex.put(this.indexToKey.get(i), i); } }

@Override public int size() { return this.keyToIndex.size(); }

@Override public int numEdges() { int count = 0; for (int i = 0; i < this.matrix.length; i++) { for (int j = 0; j < this.matrix[i].length; j++) { count += this.matrix[i][j]; } } return count; }

@Override public boolean addEdge(T from, T to) { if (!this.keyToIndex.containsKey(from) || !this.keyToIndex.containsKey(to)) { throw new NoSuchElementException(); } int iFrom = this.keyToIndex.get(from); int iTo = this.keyToIndex.get(to); if (this.matrix[iFrom][iTo] == 1) { return false; } this.matrix[iFrom][iTo] = 1; return true; }

@Override public boolean hasVertex(T key) { return this.keyToIndex.containsKey(key); }

@Override public boolean hasEdge(T from, T to) throws NoSuchElementException { if (!this.keyToIndex.containsKey(from) || !this.keyToIndex.containsKey(to)) { throw new NoSuchElementException(); } int iFrom = this.keyToIndex.get(from); int iTo = this.keyToIndex.get(to); return this.matrix[iFrom][iTo] == 1; }

@Override public boolean removeEdge(T from, T to) throws NoSuchElementException { if (!this.keyToIndex.containsKey(from) || !this.keyToIndex.containsKey(to)) { throw new NoSuchElementException(); } int iFrom = this.keyToIndex.get(from); int iTo = this.keyToIndex.get(to); if (this.matrix[iFrom][iTo] == 0) { return false; } this.matrix[iFrom][iTo] = 0; return true; }

@Override public int outDegree(T key) { int iFrom = this.keyToIndex.get(key); int l = this.matrix[iFrom].length; int out = 0; for (int i = 0; i < l; i++) { out += this.matrix[iFrom][i]; } return out; }

@Override public int inDegree(T key) { int iTo = this.keyToIndex.get(key); int l = this.matrix.length; int in = 0; for (int i = 0; i < l; i++) { in += this.matrix[i][iTo]; } return in; }

@Override public Set vertexSet() { Set vertexSet = new HashSet(); for (T v : this.indexToKey) { vertexSet.add(v); } return vertexSet; }

@Override public List successorList(T key) { int iFrom = this.keyToIndex.get(key); List successorList = new ArrayList(); for (int i = 0; i < this.matrix[iFrom].length; i++) { if (this.matrix[iFrom][i] == 1) { successorList.add(this.indexToKey.get(i)); } } return successorList; }

@Override public List predecessorList(T key) { int iTo = this.keyToIndex.get(key); List predecessorList = new ArrayList(); for (int i = 0; i < this.matrix.length; i++) { if (this.matrix[i][iTo] == 1) { predecessorList.add(this.indexToKey.get(i)); } } return predecessorList; }

@Override public Iterator successorIterator(T key) { return new successorIterator(this.keyToIndex.get(key)); }

private class successorIterator implements Iterator {

int iFrom; int index = 0;

public successorIterator(int iFrom) { this.iFrom = iFrom; }

@Override public boolean hasNext() { while (true) { if (this.index >= AdjacencyMatrixGraph.this.matrix[this.iFrom].length) { return false; } if (AdjacencyMatrixGraph.this.matrix[this.iFrom][this.index] == 1) { return true; } this.index++; } }

@Override public T next() { if (hasNext()) { this.index++; return AdjacencyMatrixGraph.this.indexToKey.get(this.index - 1); } return null; } }

@Override public Iterator predecessorIterator(T key) { return new predecessorIterator(this.keyToIndex.get(key)); }

private class predecessorIterator implements Iterator {

int iTo; int index = 0;

public predecessorIterator(int iTo) { this.iTo = iTo; }

@Override public boolean hasNext() { while (true) { if (this.index >= AdjacencyMatrixGraph.this.matrix[this.iTo].length) { return false; } if (AdjacencyMatrixGraph.this.matrix[this.index][this.iTo] == 1) { return true; } this.index++; } }

@Override public T next() { if (hasNext()) { this.index += 1; return AdjacencyMatrixGraph.this.indexToKey.get(this.index); } return null; } }

@Override public Set stronglyConnectedComponent(T key) { // TODO return null; }

@Override public List shortestPath(T startLabel, T endLabel) { // TODO return null; }

}

//TEST Cases

package graphs;

import static org.junit.Assert.assertEquals; import static org.junit.Assert.assertTrue;

import java.io.File; import java.io.FileNotFoundException; import java.util.Arrays; import java.util.HashSet; import java.util.List; import java.util.Scanner; import java.util.Set;

import org.junit.AfterClass; import org.junit.BeforeClass; import org.junit.Test;

/** * Complete test cases for Milestone 2 * * * @author Nate Chenette * */ public class GraphSurfingMilestone2Test {

// Toggle this to false to speed up early testing process. private static boolean runLivingPeopleGraphTests = true;

// Toggle this to false to suppress output. private static boolean verbose = true;

private static int m2points = 0; private static int m2bonusPoints = 0; private static int m2weight = 1; private static final int MAX_POINTS = 60; private static Graph livingPeopleALGraph; private static boolean livingPeopleShortestPathWorking = false;

@BeforeClass public static void buildLivingPeopleGraph() { if (runLivingPeopleGraphTests) { livingPeopleALGraph = WikiSurfing.wikiLivingPeopleGraphAL(verbose); } }

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 helperTestStronglyConnectedComponentExampleGraphs(Graph g, Graph g2) { Set answer = new HashSet(Arrays.asList("a")); assertEquals(answer, g.stronglyConnectedComponent("a")); answer = new HashSet(Arrays.asList("c","d","f")); assertEquals(answer, g.stronglyConnectedComponent("f"));

Set answer2 = new HashSet(Arrays.asList(5)); assertEquals(answer2, g2.stronglyConnectedComponent(5)); answer2 = new HashSet(Arrays.asList(0,1)); assertEquals(answer2, g2.stronglyConnectedComponent(1)); answer2 = new HashSet(Arrays.asList(2,3,4,6)); assertEquals(answer2, g2.stronglyConnectedComponent(2)); m2points += 10*m2weight; }

@Test public void testALStronglyConnectedComponentExampleGraphs() { helperTestStronglyConnectedComponentExampleGraphs(makeExampleALGraph(), makeExample2ALGraph()); }

@Test public void testAMStronglyConnectedComponentExampleGraphs() { helperTestStronglyConnectedComponentExampleGraphs(makeExampleAMGraph(), makeExample2AMGraph()); }

private void helperTestShortestPathExampleGraphs(Graph g, Graph g2) { assertEquals(Arrays.asList("a","b"), g.shortestPath("a","b")); assertEquals(Arrays.asList("a","c"), g.shortestPath("a","c")); assertEquals(Arrays.asList("b","d","c"), g.shortestPath("b","c")); assertEquals(Arrays.asList("f","c","d","e"), g.shortestPath("f","e")); assertTrue(Arrays.asList("a","b","d").equals(g.shortestPath("a","d")) || Arrays.asList("a","c","d").equals(g.shortestPath("a","d")));

assertEquals(Arrays.asList(0,1), g2.shortestPath(0,1)); assertEquals(Arrays.asList(0,2,4,6), g2.shortestPath(0,6)); assertEquals(Arrays.asList(6,2,3), g2.shortestPath(6,3)); assertEquals(Arrays.asList(4,6,2,3), g2.shortestPath(4,3)); assertEquals(Arrays.asList(1,0,2,4,5), g2.shortestPath(1,5)); m2points += 8*m2weight;

assertEquals(null, g.shortestPath("b","a")); assertEquals(null, g.shortestPath("f","b")); assertEquals(null, g2.shortestPath(2,0)); assertEquals(null, g2.shortestPath(4,1)); m2points += 2*m2weight;

}

@Test public void testALShortestPathExampleGraphs() { helperTestShortestPathExampleGraphs(makeExampleALGraph(), makeExample2ALGraph()); }

@Test public void testAMShortestPathExampleGraphs() { helperTestShortestPathExampleGraphs(makeExampleAMGraph(), makeExample2AMGraph()); }

@Test public void testWikiSurfingShortestPath() { assertTrue(runLivingPeopleGraphTests); List toTry = Arrays.asList( new ChallengeAndResult("Hope Solo", "Hope Solo", 1), new ChallengeAndResult("Donald Knuth", "Tony Hoare", 2), new ChallengeAndResult("Shafi Goldwasser", "Lenore Blum", 3), new ChallengeAndResult("Dwayne Johnson", "Emma Stone", 4), new ChallengeAndResult("Britney Spears", "Lance Armstrong", 4), new ChallengeAndResult("50 Cent", "Mike Pence", 5), new ChallengeAndResult("Usain Bolt", "Taylor Swift", 5) ); for (ChallengeAndResult chal : toTry) { List result = livingPeopleALGraph.shortestPath(chal.from,chal.to); if (verbose) { System.out.println("Shortest path solution: " + result); } // Check to make sure all are valid edges for (int i = 1; i < result.size(); i++) { assertTrue(livingPeopleALGraph.hasEdge(result.get(i-1), result.get(i))); } // Check to make sure it is a minimum length path assertEquals(chal.solutionLength,result.size()); } assertTrue(livingPeopleALGraph.shortestPath("Tony Hoare", "Donald Knuth") == null); assertTrue(livingPeopleALGraph.shortestPath("LeBron James", "Baron Waqa") == null); livingPeopleShortestPathWorking = true; m2points += 10*m2weight; }

@Test public void testWikiSurfingStronglyConnectedComponent() { assertTrue(runLivingPeopleGraphTests); List toTry = Arrays.asList( new ChallengeAndResult("Simon Geschke", null, 1), new ChallengeAndResult("Roxane Mesquida", null, 2), new ChallengeAndResult("Tony Hoare", null, 3), new ChallengeAndResult("Anna Mickelson", null, 11), new ChallengeAndResult("Antonella Bellutti", null, 17), new ChallengeAndResult("Chinedu Ikedieze", null, 18), new ChallengeAndResult("Edward Natapei", null, 19), new ChallengeAndResult("Baron Waqa", null, 24), new ChallengeAndResult("Zhang Juanjuan", null, 83), new ChallengeAndResult("Larry Bird", null, 146347), new ChallengeAndResult("Donald Knuth", null, 146347) ); for (ChallengeAndResult chal : toTry) { Set result = livingPeopleALGraph.stronglyConnectedComponent(chal.from); if (verbose) { System.out.println(chal.from + " is in a component of size " + result.size()); } // Check to make sure it is a minimum length path assertEquals(chal.solutionLength,result.size()); } Set goal = new HashSet(); goal.addAll(Arrays.asList("He Jifeng", "Cliff Jones (computer scientist)", "Tony Hoare")); assertEquals(goal,livingPeopleALGraph.stronglyConnectedComponent("Tony Hoare")); m2points += 10*m2weight; }

private class ChallengeAndResult { String from; String to; int solutionLength; ChallengeAndResult(String a, String b, int len) { this.from = a; this.to = b; this.solutionLength = len; } }

@Test public void testWikiSurfingFindChallengePair() { assertTrue(runLivingPeopleGraphTests); Scanner sc = null; String from = ""; String to = ""; String pairFileName = "challenge-pair.txt"; try { sc = new Scanner(new File(pairFileName)); } catch (FileNotFoundException e) { System.err.printf("Could not find file %s%n",pairFileName); } if (sc.hasNextLine()) { from = sc.nextLine(); } if (sc.hasNextLine()) { to = sc.nextLine(); } List sol = livingPeopleALGraph.shortestPath(from,to); int len = sol.size(); if (len > 6) { m2bonusPoints = (int) (m2weight * (len - 6)); } if (verbose) { System.out.printf("Challenge pair [%s, %s] has shortest path length %d: %d bonus points awarded%n",from,to,len,m2bonusPoints); } }

// @Test // public void testWikiSurfingFindChallengePairAlgorithm() { // assertTrue(runLivingPeopleGraphTests); // Pair bestPair = livingPeopleALGraph.findChallengePair(); // String from = bestPair.from; // String to = bestPair.to; // List sol = livingPeopleALGraph.shortestPath(from,to); // int len = sol.size(); // if (len > 5) { // m2bonusPoints = (int) (2*m2weight * (len - 5)); // } // if (verbose) { // System.out.printf("ALGORITHM: Challenge pair [%s, %s] has shortest path length %d: %d bonus points awarded%n",from,to,len,m2bonusPoints); // } // }

@AfterClass public static void printSummary() { if (livingPeopleShortestPathWorking) { m2points += m2bonusPoints; } System.out.print(" =============== "); System.out.print("Total points: "); System.out.print(m2points + "/" + MAX_POINTS); System.out.println(" ==============="); } }