commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From simonetrip...@apache.org
Subject svn commit: r1143157 - /commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/PrimTestCase.java
Date Tue, 05 Jul 2011 18:14:29 GMT
Author: simonetripodi
Date: Tue Jul  5 18:14:29 2011
New Revision: 1143157

URL: http://svn.apache.org/viewvc?rev=1143157&view=rev
Log:
added graph on Wikipedia page to test Prim's algorithm

Modified:
    commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/PrimTestCase.java

Modified: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/PrimTestCase.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/PrimTestCase.java?rev=1143157&r1=1143156&r2=1143157&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/PrimTestCase.java
(original)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/PrimTestCase.java
Tue Jul  5 18:14:29 2011
@@ -92,9 +92,79 @@ public final class PrimTestCase
 
         expected.addEdge( f, new BaseLabeledWeightedEdge( "f <-> g", 4D ), g );
 
-        // actual
+        internalPrimAssertion( input, a, expected );
+    }
+
+    /**
+     * Test Graph and Prim's solution can be seen on
+     * <a href="http://en.wikipedia.org/wiki/Prim%27s_algorithm">Wikipedia</a>
+     */
+    @Test
+    public void verifyWikipediaMinimumSpanningTree()
+    {
+        UndirectedMutableWeightedGraph<BaseLabeledVertex, BaseLabeledWeightedEdge>
input
+            = new UndirectedMutableWeightedGraph<BaseLabeledVertex, BaseLabeledWeightedEdge>();
+
+        BaseLabeledVertex a = new BaseLabeledVertex( "A" );
+        BaseLabeledVertex b = new BaseLabeledVertex( "B" );
+        BaseLabeledVertex c = new BaseLabeledVertex( "C" );
+        BaseLabeledVertex d = new BaseLabeledVertex( "D" );
+        BaseLabeledVertex e = new BaseLabeledVertex( "E" );
+        BaseLabeledVertex f = new BaseLabeledVertex( "F" );
+        BaseLabeledVertex g = new BaseLabeledVertex( "G" );
+
+        input.addVertex( a );
+        input.addVertex( b );
+        input.addVertex( c );
+        input.addVertex( d );
+        input.addVertex( e );
+        input.addVertex( f );
+        input.addVertex( g );
+
+        input.addEdge( a, new BaseLabeledWeightedEdge( "a <-> b", 7D ), b );
+        input.addEdge( a, new BaseLabeledWeightedEdge( "a <-> d", 5D ), d );
+
+        input.addEdge( b, new BaseLabeledWeightedEdge( "b <-> c", 8D ), c );
+        input.addEdge( b, new BaseLabeledWeightedEdge( "b <-> d", 9D ), d );
+        input.addEdge( b, new BaseLabeledWeightedEdge( "b <-> e", 7D ), e );
+
+        input.addEdge( c, new BaseLabeledWeightedEdge( "c <-> e", 5D ), e );
+
+        input.addEdge( d, new BaseLabeledWeightedEdge( "d <-> e", 15D ), e );
+        input.addEdge( d, new BaseLabeledWeightedEdge( "d <-> f", 6D ), f );
+
+        input.addEdge( e, new BaseLabeledWeightedEdge( "e <-> f", 8D ), f );
+        input.addEdge( e, new BaseLabeledWeightedEdge( "e <-> g", 9D ), g );
+
+        input.addEdge( f, new BaseLabeledWeightedEdge( "f <-> g", 11D ), g );
+
+        // expected
+
+        MutableSpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge> expected =
+            new MutableSpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge>();
+
+        for ( BaseLabeledVertex vertex : input.getVertices() )
+        {
+            expected.addVertex( vertex );
+        }
+
+        expected.addEdge( a, new BaseLabeledWeightedEdge( "a <-> b", 7D ), b );
+        expected.addEdge( a, new BaseLabeledWeightedEdge( "a <-> d", 5D ), d );
+        expected.addEdge( b, new BaseLabeledWeightedEdge( "b <-> e", 9D ), e );
+        expected.addEdge( c, new BaseLabeledWeightedEdge( "c <-> e", 5D ), e );
+        expected.addEdge( d, new BaseLabeledWeightedEdge( "d <-> f", 6D ), f );
+        expected.addEdge( e, new BaseLabeledWeightedEdge( "e <-> g", 9D ), g );
+
+        internalPrimAssertion( input, d, expected );
+    }
+
+    private static void internalPrimAssertion( UndirectedMutableWeightedGraph<BaseLabeledVertex,
BaseLabeledWeightedEdge> input,
+                                               BaseLabeledVertex source,
+                                               MutableSpanningTree<BaseLabeledVertex,
BaseLabeledWeightedEdge> expected )
+    {
+     // actual
 
-        SpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge> actual = minimumSpanningTree(
input, a );
+        SpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge> actual = minimumSpanningTree(
input, source );
 
         // assert!
 



Mime
View raw message