BasicGraphSearchTests.java

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;
    }
  
    
}