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!
