Skip to content

Instantly share code, notes, and snippets.

@ashaw596
Forked from justbuchanan/BasicGraphSearchTests.java
Last active August 29, 2015 13:58
Show Gist options
  • Save ashaw596/10079528 to your computer and use it in GitHub Desktop.
Save ashaw596/10079528 to your computer and use it in GitHub Desktop.
import org.junit.After;
import org.junit.Before;
import org.junit.Test;
import com.sun.xml.internal.bind.v2.runtime.unmarshaller.XsiNilLoader.Array;
import java.util.Arrays;
import java.util.Collection;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.HashMap;
import java.util.Map.Entry;
import static org.junit.Assert.assertTrue;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertNull;
import static org.junit.Assert.assertNotNull;
import static org.junit.Assert.fail;
/**
* A few simple tests for the GraphSearch homework (hw 9)
*
* @author Justin Buchanan
*/
public class BasicGraphSearchTest {
Map<String, List<String>> adjList;
Map<String, List<String>> circularGraph;
Map<String, List<Pair<String, Integer>>> weightedGraph;
Map<String, List<Pair<String, Integer>>> weightedCircularGraph;
long startTime;
@Before
public void setUp() {
adjList = new HashMap<>();
LinkedList<String> aList = new LinkedList<>();
aList.add("B");
aList.add("D");
aList.add("F");
adjList.put("A", aList);
LinkedList<String> bList = new LinkedList<>();
bList.add("C");
bList.add("D");
adjList.put("B", bList);
LinkedList<String> cList = new LinkedList<>();
adjList.put("C", cList);
LinkedList<String> dList = new LinkedList<>();
adjList.put("D", dList);
LinkedList<String> fList = new LinkedList<>();
fList.add("G");
adjList.put("F", fList);
LinkedList<String> gList = new LinkedList<>();
gList.add("H");
adjList.put("G", gList);
LinkedList<String> hList = new LinkedList<>();
hList.add("I");
adjList.put("H", hList);
LinkedList<String> iList = new LinkedList<>();
adjList.put("I", iList);
// weighted graph
////////////////////////////////////////////////////////////////////////////////////
weightedGraph = new HashMap<>();
LinkedList<Pair<String, Integer>> aListWeighted = new LinkedList<>();
aListWeighted.add(new Pair<String, Integer>("B", 3));
aListWeighted.add(new Pair<String, Integer>("D", 2));
aListWeighted.add(new Pair<String, Integer>("F", 1));
weightedGraph.put("A", aListWeighted);
LinkedList<Pair<String, Integer>> bListWeighted = new LinkedList<>();
bListWeighted.add(new Pair<String, Integer>("C", 1));
bListWeighted.add(new Pair<String, Integer>("D", 1));
weightedGraph.put("B", bListWeighted);
LinkedList<Pair<String, Integer>> cListWeighted = new LinkedList<>();
weightedGraph.put("C", cListWeighted);
LinkedList<Pair<String, Integer>> dListWeighted = new LinkedList<>();
weightedGraph.put("D", dListWeighted);
LinkedList<Pair<String, Integer>> fListWeighted = new LinkedList<>();
fListWeighted.add(new Pair<String, Integer>("G", 2));
weightedGraph.put("F", fListWeighted);
LinkedList<Pair<String, Integer>> gListWeighted = new LinkedList<>();
gListWeighted.add(new Pair<String, Integer>("H", 3));
weightedGraph.put("G", gListWeighted);
LinkedList<Pair<String, Integer>> hListWeighted = new LinkedList<>();
weightedGraph.put("H", hListWeighted);
weightedCircularGraph = new HashMap<>();
weightedCircularGraph.put("A", new LinkedList<Pair<String,Integer>>((Collection<? extends Pair<String, Integer>>) Arrays.asList(new Pair[]{new Pair("C", 0),new Pair("D", 1),new Pair("F", 20)})));
weightedCircularGraph.put("C", new LinkedList<Pair<String,Integer>>((Collection<? extends Pair<String, Integer>>) Arrays.asList(new Pair[]{new Pair("D", 0)})));
weightedCircularGraph.put("D", new LinkedList<Pair<String,Integer>>((Collection<? extends Pair<String, Integer>>) Arrays.asList(new Pair[]{new Pair("G", 1),new Pair("F", 20)})));
weightedCircularGraph.put("G", new LinkedList<Pair<String,Integer>>((Collection<? extends Pair<String, Integer>>) Arrays.asList(new Pair[]{new Pair("E", 1)})));
weightedCircularGraph.put("E", new LinkedList<Pair<String,Integer>>((Collection<? extends Pair<String, Integer>>) Arrays.asList(new Pair[]{new Pair("H", 3)})));
weightedCircularGraph.put("H", new LinkedList<Pair<String,Integer>>((Collection<? extends Pair<String, Integer>>) Arrays.asList(new Pair[]{new Pair("E", 1),new Pair("F", 2)})));
weightedCircularGraph.put("F", new LinkedList<Pair<String,Integer>>((Collection<? extends Pair<String, Integer>>) Arrays.asList(new Pair[]{new Pair("D", 3),new Pair("H", 1),new Pair("F", 0)})));
circularGraph = new HashMap<>();
for (Entry<String, List<Pair<String,Integer>>> o: weightedCircularGraph.entrySet()) {
LinkedList<String> temp = new LinkedList<String>();
for (Pair<String, Integer> p: o.getValue()) {
temp.add(p.a);
}
circularGraph.put(o.getKey(), temp);
}
}
@Test
public void testEfficiency() {
//depthFirst
//startTimer();
//int depthFirst = endTimer();
//int breadthFirst = endTimer();
//startTimer();
//assertTrue(GraphSearch.depthFirstSearch("A", adjList, "I"));
//depthFirst = endTimer();
//System.out.println();
//startTimer();
//assertTrue(GraphSearch.breadthFirstSearch("A", adjList, "I"));
//breadthFirst = endTimer();
//System.out.println("depthFirstBetter test");
//System.out.println("depthFirst time:" + depthFirst);
//System.out.println("breadthFirst time:" + breadthFirst);
// assertTrue(depthFirst<breadthFirst);
// assertTrue(GraphSearch.depthFirstSearch("A", adjList, "H"));
// assertFalse(GraphSearch.depthFirstSearch("A", adjList, "J"));
}
@Test
public void testCircularDepthFirstSearch() {
assertTrue(GraphSearch.depthFirstSearch("A", circularGraph, "C"));
assertTrue(GraphSearch.depthFirstSearch("A", circularGraph, "D"));
assertTrue(GraphSearch.depthFirstSearch("A", circularGraph, "G"));
assertTrue(GraphSearch.depthFirstSearch("A", circularGraph, "H"));
assertTrue(GraphSearch.depthFirstSearch("C", circularGraph, "H"));
assertTrue(GraphSearch.depthFirstSearch("F", circularGraph, "E"));
assertTrue(GraphSearch.depthFirstSearch("G", circularGraph, "D"));
assertFalse(GraphSearch.depthFirstSearch("C", circularGraph, "A"));
assertFalse(GraphSearch.depthFirstSearch("D", circularGraph, "A"));
assertFalse(GraphSearch.depthFirstSearch("D", circularGraph, "A"));
assertFalse(GraphSearch.depthFirstSearch("F", circularGraph, "C"));
assertFalse(GraphSearch.depthFirstSearch("H", circularGraph, "C"));
}
@Test
public void testCircularDijkstras() {
assertEquals(0,GraphSearch.djikstraShortestPathAlgorithm("A", weightedCircularGraph, "C"));
assertEquals(0,GraphSearch.djikstraShortestPathAlgorithm("A", weightedCircularGraph, "D"));
assertEquals(1,GraphSearch.djikstraShortestPathAlgorithm("A", weightedCircularGraph, "G"));
assertEquals(5,GraphSearch.djikstraShortestPathAlgorithm("A", weightedCircularGraph, "H"));
assertEquals(5,GraphSearch.djikstraShortestPathAlgorithm("C", weightedCircularGraph, "H"));
assertEquals(2,GraphSearch.djikstraShortestPathAlgorithm("F", weightedCircularGraph, "E"));
assertEquals(9,GraphSearch.djikstraShortestPathAlgorithm("G", weightedCircularGraph, "D"));
assertEquals(-1,GraphSearch.djikstraShortestPathAlgorithm("C", weightedCircularGraph, "A"));
assertEquals(-1,GraphSearch.djikstraShortestPathAlgorithm("D", weightedCircularGraph, "A"));
assertEquals(-1,GraphSearch.djikstraShortestPathAlgorithm("D", weightedCircularGraph, "A"));
assertEquals(-1,GraphSearch.djikstraShortestPathAlgorithm("F", weightedCircularGraph, "C"));
assertEquals(-1,GraphSearch.djikstraShortestPathAlgorithm("H", weightedCircularGraph, "C"));
}
@Test
public void testCircularBreadthFirstSearch() {
assertTrue(GraphSearch.breadthFirstSearch("A", circularGraph, "C"));
assertTrue(GraphSearch.breadthFirstSearch("A", circularGraph, "D"));
assertTrue(GraphSearch.breadthFirstSearch("A", circularGraph, "G"));
assertTrue(GraphSearch.breadthFirstSearch("A", circularGraph, "H"));
assertTrue(GraphSearch.breadthFirstSearch("C", circularGraph, "H"));
assertTrue(GraphSearch.breadthFirstSearch("F", circularGraph, "E"));
assertTrue(GraphSearch.breadthFirstSearch("G", circularGraph, "D"));
assertFalse(GraphSearch.breadthFirstSearch("C", circularGraph, "A"));
assertFalse(GraphSearch.breadthFirstSearch("D", circularGraph, "A"));
assertFalse(GraphSearch.breadthFirstSearch("D", circularGraph, "A"));
assertFalse(GraphSearch.breadthFirstSearch("F", circularGraph, "C"));
assertFalse(GraphSearch.breadthFirstSearch("H", circularGraph, "C"));
}
@Test
public void testDepthFirstSearch() {
assertTrue(GraphSearch.depthFirstSearch("A", adjList, "H"));
assertFalse(GraphSearch.depthFirstSearch("A", adjList, "J"));
}
@Test
public void testBreadthFirstSearch() {
assertTrue(GraphSearch.breadthFirstSearch("A", adjList, "H"));
assertFalse(GraphSearch.breadthFirstSearch("A", adjList, "J"));
}
@Test
public void testDijkstras() {
assertEquals(GraphSearch.djikstraShortestPathAlgorithm("A", weightedGraph, "H"), 6);
assertEquals(GraphSearch.djikstraShortestPathAlgorithm("F", weightedGraph, "H"), 5);
assertEquals(GraphSearch.djikstraShortestPathAlgorithm("H", weightedGraph, "H"), 0);
assertEquals(GraphSearch.djikstraShortestPathAlgorithm("B", weightedGraph, "C"), 1);
assertEquals(GraphSearch.djikstraShortestPathAlgorithm("A", weightedGraph, "C"), 4);
assertEquals(GraphSearch.djikstraShortestPathAlgorithm("C", weightedGraph, "H"), -1);
assertEquals(GraphSearch.djikstraShortestPathAlgorithm("D", weightedGraph, "A"), -1);
assertEquals(GraphSearch.djikstraShortestPathAlgorithm("A", weightedGraph, "Z"), -1);
}
@After
public void tearDown() {
adjList = null;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment