svn commit: r1137101 - /commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/DijkstraTestCase.java

[si...@apache.org]

Author: simonetripodi
Date: Sat Jun 18 00:36:06 2011
New Revision: 1137101

URL: http://svn.apache.org/viewvc?rev=1137101&view=rev
Log:
Dijkstra's algorithm tested on both (un)directed graphs

Modified:
    commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/DijkstraTestCase.java

Modified: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/DijkstraTestCase.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/DijkstraTestCase.java?rev=1137101&r1=1137100&r2=1137101&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/DijkstraTestCase.java (original)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/DijkstraTestCase.java Sat Jun 18 00:36:06 2011
@@ -3,11 +3,14 @@ package org.apache.commons.graph.shortes
 import static junit.framework.Assert.assertEquals;
 import static org.apache.commons.graph.shortestpath.Dijkstra.findShortestPath;
 
+import org.apache.commons.graph.MutableGraph;
 import org.apache.commons.graph.Path;
+import org.apache.commons.graph.WeightedGraph;
 import org.apache.commons.graph.model.BaseLabeledVertex;
 import org.apache.commons.graph.model.BaseLabeledWeightedEdge;
 import org.apache.commons.graph.model.DirectedMutableWeightedGraph;
 import org.apache.commons.graph.model.InMemoryWeightedPath;
+import org.apache.commons.graph.model.UndirectedMutableWeightedGraph;
 import org.junit.Test;
 
 public final class DijkstraTestCase
@@ -18,9 +21,23 @@ public final class DijkstraTestCase
      * Wikipedia {@link http://en.wikipedia.org/wiki/Dijkstra's_algorithm}
      */
     @Test
-    public void shortestPath1()
+    public void undirectedShortestPath()
     {
-        // test Graph
+        findShortestPathAndVerify( new UndirectedMutableWeightedGraph<BaseLabeledVertex, BaseLabeledWeightedEdge>() );
+    }
+
+    @Test
+    public void directedShortestPath()
+    {
+        findShortestPathAndVerify( new DirectedMutableWeightedGraph<BaseLabeledVertex, BaseLabeledWeightedEdge>() );
+    }
+
+    private void findShortestPathAndVerify( WeightedGraph<BaseLabeledVertex, BaseLabeledWeightedEdge> weighted )
+    {
+        @SuppressWarnings( "unchecked" ) // mutable by definition, generic types driven by input arg
+        MutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge> mutable = (MutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge>) weighted;
+
+        // building Graph
 
         BaseLabeledVertex one = new BaseLabeledVertex( "1" );
         BaseLabeledVertex two = new BaseLabeledVertex( "2" );
@@ -29,33 +46,28 @@ public final class DijkstraTestCase
         BaseLabeledVertex five = new BaseLabeledVertex( "5" );
         BaseLabeledVertex six = new BaseLabeledVertex( "6" );
 
-        DirectedMutableWeightedGraph<BaseLabeledVertex, BaseLabeledWeightedEdge> testGraph =
-            new DirectedMutableWeightedGraph<BaseLabeledVertex, BaseLabeledWeightedEdge>();
-
-        testGraph.addVertex( one );
-        testGraph.addVertex( two );
-        testGraph.addVertex( three );
-        testGraph.addVertex( four );
-        testGraph.addVertex( five );
-        testGraph.addVertex( six );
-
-        testGraph.addEdge( new BaseLabeledWeightedEdge( "", one, six, 14D ) );
-        testGraph.addEdge( new BaseLabeledWeightedEdge( "", one, three, 9D ) );
-        testGraph.addEdge( new BaseLabeledWeightedEdge( "", one, two, 7D ) );
+        mutable.addVertex( one );
+        mutable.addVertex( two );
+        mutable.addVertex( three );
+        mutable.addVertex( four );
+        mutable.addVertex( five );
+        mutable.addVertex( six );
+
+        mutable.addEdge( new BaseLabeledWeightedEdge( "", one, six, 14D ) );
+        mutable.addEdge( new BaseLabeledWeightedEdge( "", one, three, 9D ) );
+        mutable.addEdge( new BaseLabeledWeightedEdge( "", one, two, 7D ) );
 
-        testGraph.addEdge( new BaseLabeledWeightedEdge( "", two, three, 10D ) );
-        testGraph.addEdge( new BaseLabeledWeightedEdge( "", two, four, 15D ) );
+        mutable.addEdge( new BaseLabeledWeightedEdge( "", two, three, 10D ) );
+        mutable.addEdge( new BaseLabeledWeightedEdge( "", two, four, 15D ) );
 
-        testGraph.addEdge( new BaseLabeledWeightedEdge( "", three, six, 2D ) );
-        testGraph.addEdge( new BaseLabeledWeightedEdge( "", three, four, 11D ) );
+        mutable.addEdge( new BaseLabeledWeightedEdge( "", three, six, 2D ) );
+        mutable.addEdge( new BaseLabeledWeightedEdge( "", three, four, 11D ) );
 
-        testGraph.addEdge( new BaseLabeledWeightedEdge( "", four, five, 6D ) );
-        testGraph.addEdge( new BaseLabeledWeightedEdge( "", six, five, 9D ) );
+        mutable.addEdge( new BaseLabeledWeightedEdge( "", four, five, 6D ) );
+        mutable.addEdge( new BaseLabeledWeightedEdge( "", six, five, 9D ) );
 
         // expected path
 
-        Path<BaseLabeledVertex, BaseLabeledWeightedEdge> actual = findShortestPath( testGraph, one, five );
-
         InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge> expected =
             new InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge>( one, five, 20D );
 
@@ -67,6 +79,12 @@ public final class DijkstraTestCase
         expected.addEdgeInTail( new BaseLabeledWeightedEdge( "", three, six, 2D ) );
         expected.addEdgeInTail( new BaseLabeledWeightedEdge( "", six, five, 9D ) );
 
+        // actual path
+
+        Path<BaseLabeledVertex, BaseLabeledWeightedEdge> actual = findShortestPath( weighted, one, five );
+
+        // assert!
+
         assertEquals( expected, actual );
     }