//NEED TO DEAL WITH stronglyConnectedComponent method

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 AdjacencyListGraph extends Graph {

Map keyToVertex;

private class Vertex {

T key;

List successors;

List predecessors;

Vertex(T key) {

this.key = key;

this.successors = new ArrayList();

this.predecessors = new ArrayList();

}

}

AdjacencyListGraph(Set keys) {

this.keyToVertex = new HashMap();

for (T key : keys) {

Vertex v = new Vertex(key);

this.keyToVertex.put(key, v);

}

}

@Override

public int size() {

return this.keyToVertex.size();

}

@Override

public int numEdges() {

int count = 0;

for (Vertex v : this.keyToVertex.values()) {

count += v.successors.size();

}

return count;

}

@Override

public boolean addEdge(T from, T to) {

if (!this.keyToVertex.containsKey(from)) {

throw new NoSuchElementException("Could not find vertex with key " + from.toString());

}

if (!this.keyToVertex.containsKey(to)) {

throw new NoSuchElementException("Could not find vertex with key " + to.toString());

}

Vertex fromV = this.keyToVertex.get(from);

Vertex toV = this.keyToVertex.get(to);

List fromSuccs = fromV.successors;

List toPreds = toV.predecessors;

if (fromSuccs.contains(toV)) {

return false;

}

fromSuccs.add(toV);

toPreds.add(fromV);

return true;

}

@Override

public boolean hasVertex(T key) {

return this.keyToVertex.containsKey(key);

}

@Override

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

if (!this.keyToVertex.containsKey(from)) {

throw new NoSuchElementException("Could not find vertex with key " + from.toString());

}

if (!this.keyToVertex.containsKey(to)) {

throw new NoSuchElementException("Could not find vertex with key " + to.toString());

}

Vertex fromV = this.keyToVertex.get(from);

Vertex toV = this.keyToVertex.get(to);

List fromSuccs = fromV.successors;

List toPreds = toV.predecessors;

if (fromSuccs.contains(toV)) {

return true;

}

return false;

}

@Override

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

if (!this.keyToVertex.containsKey(from)) {

throw new NoSuchElementException("Could not find vertex with key " + from.toString());

}

if (!this.keyToVertex.containsKey(to)) {

throw new NoSuchElementException("Could not find vertex with key " + to.toString());

}

Vertex fromV = this.keyToVertex.get(from);

Vertex toV = this.keyToVertex.get(to);

if (!this.hasEdge(from, to)) {

return false;

}

List fromSuccs = fromV.successors;

List toPreds = toV.predecessors;

fromSuccs.remove(toV);

toPreds.remove(fromV);

if (!fromSuccs.contains(toV)) {

return true;

}

return false;

}

@Override

public int outDegree(T key) {

return this.keyToVertex.get(key).successors.size();

}

@Override

public int inDegree(T key) {

return this.keyToVertex.get(key).predecessors.size();

}

@Override

public Set vertexSet() {

Set vertexSet = new HashSet();

for (T v : this.keyToVertex.keySet()) {

vertexSet.add(v);

}

return vertexSet;

}

@Override

public List successorList(T key) {

List successorList = new ArrayList();

for (Vertex v : this.keyToVertex.get(key).successors) {

successorList.add(v.key);

}

return successorList;

}

@Override

public List predecessorList(T key) {

List predecessorList = new ArrayList();

for (Vertex v : this.keyToVertex.get(key).predecessors) {

predecessorList.add(v.key);

}

return predecessorList;

}

@Override

public Iterator successorIterator(T key) {

return new theIterator(this.successorList(key));

}

@Override

public Iterator predecessorIterator(T key) {

return new theIterator(this.predecessorList(key));

}

private class theIterator implements Iterator {

List target;

int index = 0;

public theIterator(List theList) {

this.target = theList;

}

@Override

public boolean hasNext() {

return this.index < this.target.size();

}

@Override

public T next() {

if (hasNext()) {

this.index += 1;

return this.target.get(this.index - 1);

}

return null;

}

}

@Override

public Set stronglyConnectedComponent(T key) {

this.keyToVertex.get(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(" ==============="); } }