KezvhLib/src-junit/net/kezvh/algorithms/graph/TestSingleSourceShortestPath.java

   1 package net.kezvh.algorithms.graph;
   2
   3 import java.util.Comparator;
   4
   5 import junit.framework.Assert;
   6 import junit.framework.TestCase;
   7 import net.kezvh.collections.graphs.directed.DirectedGraphWithEdgeValues;
   8 import net.kezvh.collections.graphs.directed.DirectedGraphWithEdgeValuesBuilder;
   9 import net.kezvh.collections.graphs.directed.GraphWithEdgeValuesTemplate;
  10 import net.kezvh.collections.graphs.directed.HashDirectedGraphSetBuilder;
  11 import net.kezvh.collections.heaps.Heap;
  12 import net.kezvh.collections.heaps.PairingHeap;
  13 import net.kezvh.patterns.AbstractFactory;
  14
  15 import org.junit.Test;
  16
  17 /**
  18  * @author mjacob
  19  */
  20 public abstract class TestSingleSourceShortestPath extends TestCase {
  21         private final DirectedGraphWithEdgeValuesBuilder GRAPH_BUILDER = new HashDirectedGraphSetBuilder();
  22         private final AbstractFactory<Heap<Integer, Integer>> HEAP_MAKER = new AbstractFactory<Heap<Integer, Integer>>() {
  23                 @Override
  24                 public Heap<Integer, Integer> create() throws net.kezvh.patterns.AbstractFactory.CreationFailedException {
  25                         return new PairingHeap<Integer, Integer>(new Comparator<Integer>() {
  26                                 public int compare(final Integer o1, final Integer o2) {
  27                                         if (o1.equals(-1)) {
  28                                                 if (o2.equals(-1))
  29                                                         return 0;
  30                                                 return 1;
  31                                         } else if (o2.equals(-1))
  32                                                 return -1;
  33                                         else
  34                                                 return o1.compareTo(o2);
  35                                 }
  36                         });
  37                 }
  38         };
  39
  40         /**
  41          * @param graph graph
  42          * @param source source node
  43          * @param heapMaker something to make a heap
  44          * @return all pairs shortest path object for queries
  45          */
  46         protected abstract SingleSourceShortestPath<Integer> getSingleSourceShortedPath(final DirectedGraphWithEdgeValues<Integer, Integer> graph, final Integer source, final AbstractFactory<Heap<Integer, Integer>> heapMaker);
  47
  48         /**
  49          * @throws Exception might throw an exception
  50          */
  51         @Test
  52         public void testCreate() throws Exception {
  53                 final DirectedGraphWithEdgeValues<Integer, Integer> graph = this.GRAPH_BUILDER.buildGraph(GraphWithEdgeValuesTemplate.TRIVIAL);
  54                 final SingleSourceShortestPath<Integer> it = this.getSingleSourceShortedPath(graph, 1, this.HEAP_MAKER);
  55                 Assert.assertNotNull(it);
  56         }
  57
  58         /**
  59          * @throws Exception might throw an exception
  60          */
  61         @Test
  62         public void testTrivial() throws Exception {
  63                 final DirectedGraphWithEdgeValues<Integer, Integer> graph = this.GRAPH_BUILDER.buildGraph(GraphWithEdgeValuesTemplate.TRIVIAL);
  64                 final SingleSourceShortestPath<Integer> it = this.getSingleSourceShortedPath(graph, 1, this.HEAP_MAKER);
  65                 final Path<Integer> path = it.getShortestPath(1);
  66                 Assert.assertNotNull(path);
  67                 Assert.assertEquals(1, path.size());
  68                 Assert.assertEquals(0, path.getLength());
  69         }
  70
  71         /**
  72          * @throws Exception might throw an exception
  73          */
  74         @Test
  75         public void testSimple() throws Exception {
  76                 final DirectedGraphWithEdgeValues<Integer, Integer> graph = this.GRAPH_BUILDER.buildGraph(GraphWithEdgeValuesTemplate.SIMPLE);
  77                 final SingleSourceShortestPath<Integer> it = this.getSingleSourceShortedPath(graph, 1, this.HEAP_MAKER);
  78
  79                 Assert.assertTrue(it.connected(2));
  80
  81                 final Path<Integer> path = it.getShortestPath(1);
  82                 Assert.assertNotNull(path);
  83                 Assert.assertEquals(1, path.size());
  84                 Assert.assertEquals(0, path.getLength());
  85                 final Path<Integer> path2 = it.getShortestPath(2);
  86                 Assert.assertNotNull(path2);
  87                 Assert.assertEquals(path2.toString(), 2, path2.size());
  88                 Assert.assertEquals(1, path2.getLength());
  89         }
  90
  91         /**
  92          * @throws Exception might throw an exception
  93          */
  94         @Test
  95         public void testComplete() throws Exception {
  96                 final DirectedGraphWithEdgeValues<Integer, Integer> graph = this.GRAPH_BUILDER.buildGraph(GraphWithEdgeValuesTemplate.COMPLETE);
  97                 final SingleSourceShortestPath<Integer> it = this.getSingleSourceShortedPath(graph, 1, this.HEAP_MAKER);
  98
  99                 for (int i = 0; i < 16; i++) {
 100                         Assert.assertTrue(it.connected(i));
 101                         final Path<Integer> path = it.getShortestPath(i);
 102                         Assert.assertNotNull(path);
 103                         if (i == 1) {
 104                                 Assert.assertEquals(i + " " + path.size() + " " + path, 1, path.size());
 105                                 Assert.assertEquals(i + " " + path.size() + " " + path, 0, path.getLength());
 106                         } else {
 107                                 Assert.assertEquals(i + " ", 2, path.size());
 108                                 Assert.assertEquals(i + " ", 1, path.getLength());
 109                         }
 110                 }
 111         }
 112
 113         /**
 114          * @throws Exception might throw an exception
 115          */
 116         @Test
 117         public void testLinear() throws Exception {
 118                 final DirectedGraphWithEdgeValues<Integer, Integer> graph = this.GRAPH_BUILDER.buildGraph(GraphWithEdgeValuesTemplate.LINEAR);
 119                 final SingleSourceShortestPath<Integer> it = this.getSingleSourceShortedPath(graph, 0, this.HEAP_MAKER);
 120
 121                 for (int i = 0; i < 100; i++) {
 122                         Assert.assertTrue("node " + i + " in graph + ", graph.contains(i));
 123                         if (i != 99)
 124                                 Assert.assertTrue("edge " + i + " " + (i + 1) + " is in graph", graph.containsEdge(i, i + 1));
 125                         Assert.assertTrue("node " + i + " not connected?", it.connected(i));
 126                         final Path<Integer> path = it.getShortestPath(i);
 127                         Assert.assertNotNull(path);
 128                         Assert.assertEquals(i + " ", i + 1, path.size());
 129                         Assert.assertEquals(i + " ", i, path.getLength());
 130                 }
 131         }
 132 }