Author: marcosperanza
Date: Fri Feb 17 22:10:26 2012
New Revision: 1245786
URL: http://svn.apache.org/viewvc?rev=1245786&view=rev
Log:
[SANDBOX-393] Add test for Spanning tree
Modified:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeSourceSelector.java
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/BoruvkaTestCase.java
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/KruskalTestCase.java
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/PrimTestCase.java
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/ReverseDeleteTestCase.java
Modified:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeSourceSelector.java
URL:
http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeSourceSelector.java?rev=1245786&r1=1245785&r2=1245786&view=diff
==============================================================================
---
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeSourceSelector.java
(original)
+++
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeSourceSelector.java
Fri Feb 17 22:10:26 2012
@@ -23,6 +23,7 @@ import static java.util.Collections.reve
import static java.util.Collections.sort;
import static org.apache.commons.graph.CommonsGraph.findShortestPath;
import static org.apache.commons.graph.utils.Assertions.checkNotNull;
+import static org.apache.commons.graph.utils.Assertions.checkState;
import java.util.ArrayList;
import java.util.Iterator;
@@ -62,6 +63,7 @@ public final class DefaultSpanningTreeSo
*/
public SpanningTreeAlgorithmSelector<V, W, WE, G> fromArbitrarySource()
{
+ checkState( graph.getOrder() > 0, "Spanning tree cannot be calculated
on an empty graph" );
return fromSource( graph.getVertices().iterator().next() );
}
Modified:
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/BoruvkaTestCase.java
URL:
http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/BoruvkaTestCase.java?rev=1245786&r1=1245785&r2=1245786&view=diff
==============================================================================
---
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/BoruvkaTestCase.java
(original)
+++
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/BoruvkaTestCase.java
Fri Feb 17 22:10:26 2012
@@ -21,9 +21,13 @@ package org.apache.commons.graph.spannin
import static junit.framework.Assert.assertEquals;
import static junit.framework.Assert.fail;
+
import static org.apache.commons.graph.CommonsGraph.minimumSpanningTree;
import org.apache.commons.graph.SpanningTree;
+import org.apache.commons.graph.Vertex;
+import org.apache.commons.graph.WeightedEdge;
+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.MutableSpanningTree;
@@ -34,6 +38,62 @@ import org.junit.Test;
public final class BoruvkaTestCase
{
+ @Test( expected = NullPointerException.class )
+ public void testNullGraph()
+ {
+ minimumSpanningTree( (WeightedGraph<Vertex, WeightedEdge<Double>,
Double>) null ).fromArbitrarySource().applyingBoruvkaAlgorithm( new
DoubleWeight() );
+ }
+
+ @Test( expected = NullPointerException.class )
+ public void testNullVertex()
+ {
+ UndirectedMutableWeightedGraph<BaseLabeledVertex,
BaseLabeledWeightedEdge<Double>, Double> input = null;
+ try
+ {
+ input = new UndirectedMutableWeightedGraph<BaseLabeledVertex,
BaseLabeledWeightedEdge<Double>, Double>();
+ input.addVertex( new BaseLabeledVertex( "A" ) );
+ }
+ catch ( NullPointerException e )
+ {
+ fail( e.getMessage() );
+ }
+
+ minimumSpanningTree( input ).fromSource( null
).applyingBoruvkaAlgorithm( new DoubleWeight() );
+ }
+
+ @Test( expected = NullPointerException.class )
+ public void testNullMonoid()
+ {
+ UndirectedMutableWeightedGraph<BaseLabeledVertex,
BaseLabeledWeightedEdge<Double>, Double> input = null;
+ BaseLabeledVertex a = null;
+ try
+ {
+ input = new UndirectedMutableWeightedGraph<BaseLabeledVertex,
BaseLabeledWeightedEdge<Double>, Double>();
+ a = new BaseLabeledVertex( "A" );
+ BaseLabeledVertex b = new BaseLabeledVertex( "B" );
+
+ input.addVertex( a );
+ input.addVertex( b );
+
+ input.addEdge( a, new BaseLabeledWeightedEdge<Double>( "a <-> b",
7D ), b );
+ }
+ catch ( NullPointerException e )
+ {
+ fail( e.getMessage() );
+ }
+
+ minimumSpanningTree( input ).fromSource( a ).applyingBoruvkaAlgorithm(
null );
+ }
+
+ @Test( expected = IllegalStateException.class )
+ public void testEmptyGraph()
+ {
+ UndirectedMutableWeightedGraph<BaseLabeledVertex,
BaseLabeledWeightedEdge<Double>, Double> input =
+ new UndirectedMutableWeightedGraph<BaseLabeledVertex,
BaseLabeledWeightedEdge<Double>, Double>();
+
+ minimumSpanningTree( input
).fromArbitrarySource().applyingBoruvkaAlgorithm( new DoubleWeight() );
+ }
+
/**
* Test Graph and boruvka's solution can be seen on
*/
@@ -118,8 +178,6 @@ public final class BoruvkaTestCase
input.addVertex( new BaseLabeledVertex( "G" ) );
minimumSpanningTree( input
).fromArbitrarySource().applyingBoruvkaAlgorithm( new DoubleWeight() );
-
- fail( "Exception not thrown!. Boruvka's algorithm cannot be calculated
on a not-connected graph." );
}
}
Modified:
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/KruskalTestCase.java
URL:
http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/KruskalTestCase.java?rev=1245786&r1=1245785&r2=1245786&view=diff
==============================================================================
---
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/KruskalTestCase.java
(original)
+++
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/KruskalTestCase.java
Fri Feb 17 22:10:26 2012
@@ -20,9 +20,13 @@ package org.apache.commons.graph.spannin
*/
import static junit.framework.Assert.assertEquals;
+import static junit.framework.Assert.fail;
import static org.apache.commons.graph.CommonsGraph.minimumSpanningTree;
import org.apache.commons.graph.SpanningTree;
+import org.apache.commons.graph.Vertex;
+import org.apache.commons.graph.WeightedEdge;
+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.MutableSpanningTree;
@@ -33,6 +37,62 @@ import org.junit.Test;
public final class KruskalTestCase
{
+ @Test( expected = NullPointerException.class )
+ public void testNullGraph()
+ {
+ minimumSpanningTree( (WeightedGraph<Vertex, WeightedEdge<Double>,
Double>) null ).fromArbitrarySource().applyingKruskalAlgorithm( new
DoubleWeight() );
+ }
+
+ @Test( expected = NullPointerException.class )
+ public void testNullVertex()
+ {
+ UndirectedMutableWeightedGraph<BaseLabeledVertex,
BaseLabeledWeightedEdge<Double>, Double> input = null;
+ try
+ {
+ input = new UndirectedMutableWeightedGraph<BaseLabeledVertex,
BaseLabeledWeightedEdge<Double>, Double>();
+ input.addVertex( new BaseLabeledVertex( "A" ) );
+ }
+ catch ( NullPointerException e )
+ {
+ fail( e.getMessage() );
+ }
+
+ minimumSpanningTree( input ).fromSource( null
).applyingKruskalAlgorithm( new DoubleWeight() );
+ }
+
+ @Test( expected = NullPointerException.class )
+ public void testNullMonoid()
+ {
+ UndirectedMutableWeightedGraph<BaseLabeledVertex,
BaseLabeledWeightedEdge<Double>, Double> input = null;
+ BaseLabeledVertex a = null;
+ try
+ {
+ input = new UndirectedMutableWeightedGraph<BaseLabeledVertex,
BaseLabeledWeightedEdge<Double>, Double>();
+ a = new BaseLabeledVertex( "A" );
+ BaseLabeledVertex b = new BaseLabeledVertex( "B" );
+
+ input.addVertex( a );
+ input.addVertex( b );
+
+ input.addEdge( a, new BaseLabeledWeightedEdge<Double>( "a <-> b",
7D ), b );
+ }
+ catch ( NullPointerException e )
+ {
+ fail( e.getMessage() );
+ }
+
+ minimumSpanningTree( input ).fromSource( a ).applyingKruskalAlgorithm(
null );
+ }
+
+ @Test( expected = IllegalStateException.class )
+ public void testEmptyGraph()
+ {
+ UndirectedMutableWeightedGraph<BaseLabeledVertex,
BaseLabeledWeightedEdge<Double>, Double> input =
+ new UndirectedMutableWeightedGraph<BaseLabeledVertex,
BaseLabeledWeightedEdge<Double>, Double>();
+
+ minimumSpanningTree( input
).fromArbitrarySource().applyingKruskalAlgorithm( new DoubleWeight() );
+ }
+
/**
* Test Graph and Prim's solution can be seen on
* <a href="http://en.wikipedia.org/wiki/Prim%27s_algorithm";>Wikipedia</a>
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=1245786&r1=1245785&r2=1245786&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
Fri Feb 17 22:10:26 2012
@@ -20,9 +20,13 @@ package org.apache.commons.graph.spannin
*/
import static junit.framework.Assert.assertEquals;
+import static junit.framework.Assert.fail;
import static org.apache.commons.graph.CommonsGraph.minimumSpanningTree;
import org.apache.commons.graph.SpanningTree;
+import org.apache.commons.graph.Vertex;
+import org.apache.commons.graph.WeightedEdge;
+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.MutableSpanningTree;
@@ -32,6 +36,61 @@ import org.junit.Test;
public final class PrimTestCase
{
+ @Test( expected = NullPointerException.class )
+ public void testNullGraph()
+ {
+ minimumSpanningTree( (WeightedGraph<Vertex, WeightedEdge<Double>,
Double>) null ).fromArbitrarySource().applyingPrimAlgorithm( new DoubleWeight()
);
+ }
+
+ @Test( expected = NullPointerException.class )
+ public void testNullVertex()
+ {
+ UndirectedMutableWeightedGraph<BaseLabeledVertex,
BaseLabeledWeightedEdge<Double>, Double> input = null;
+ try
+ {
+ input = new UndirectedMutableWeightedGraph<BaseLabeledVertex,
BaseLabeledWeightedEdge<Double>, Double>();
+ input.addVertex( new BaseLabeledVertex( "A" ) );
+ }
+ catch ( NullPointerException e )
+ {
+ fail( e.getMessage() );
+ }
+
+ minimumSpanningTree( input ).fromSource( null ).applyingPrimAlgorithm(
new DoubleWeight() );
+ }
+
+ @Test( expected = NullPointerException.class )
+ public void testNullMonoid()
+ {
+ UndirectedMutableWeightedGraph<BaseLabeledVertex,
BaseLabeledWeightedEdge<Double>, Double> input = null;
+ BaseLabeledVertex a = null;
+ try
+ {
+ input = new UndirectedMutableWeightedGraph<BaseLabeledVertex,
BaseLabeledWeightedEdge<Double>, Double>();
+ a = new BaseLabeledVertex( "A" );
+ BaseLabeledVertex b = new BaseLabeledVertex( "B" );
+
+ input.addVertex( a );
+ input.addVertex( b );
+
+ input.addEdge( a, new BaseLabeledWeightedEdge<Double>( "a <-> b",
7D ), b );
+ }
+ catch ( NullPointerException e )
+ {
+ fail( e.getMessage() );
+ }
+
+ minimumSpanningTree( input ).fromSource( a ).applyingPrimAlgorithm(
null );
+ }
+
+ @Test( expected = IllegalStateException.class )
+ public void testEmptyGraph()
+ {
+ UndirectedMutableWeightedGraph<BaseLabeledVertex,
BaseLabeledWeightedEdge<Double>, Double> input =
+ new UndirectedMutableWeightedGraph<BaseLabeledVertex,
BaseLabeledWeightedEdge<Double>, Double>();
+
+ minimumSpanningTree( input
).fromArbitrarySource().applyingPrimAlgorithm( new DoubleWeight() );
+ }
/**
* Test Graph and Prim's solution can be seen on these
Modified:
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/ReverseDeleteTestCase.java
URL:
http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/ReverseDeleteTestCase.java?rev=1245786&r1=1245785&r2=1245786&view=diff
==============================================================================
---
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/ReverseDeleteTestCase.java
(original)
+++
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/ReverseDeleteTestCase.java
Fri Feb 17 22:10:26 2012
@@ -20,9 +20,13 @@ package org.apache.commons.graph.spannin
*/
import static junit.framework.Assert.assertEquals;
+import static junit.framework.Assert.fail;
import static org.apache.commons.graph.CommonsGraph.minimumSpanningTree;
import org.apache.commons.graph.SpanningTree;
+import org.apache.commons.graph.Vertex;
+import org.apache.commons.graph.WeightedEdge;
+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.MutableSpanningTree;
@@ -36,6 +40,50 @@ import org.junit.Test;
public class ReverseDeleteTestCase
{
+ @Test( expected = NullPointerException.class )
+ public void testNullGraph()
+ {
+ minimumSpanningTree( (WeightedGraph<Vertex, WeightedEdge<Double>,
Double>) null ).applyingReverseDeleteAlgorithm( new DoubleWeight() );
+ }
+
+ @Test( expected = NullPointerException.class )
+ public void testNullMonoid()
+ {
+ UndirectedMutableWeightedGraph<BaseLabeledVertex,
BaseLabeledWeightedEdge<Double>, Double> input = null;
+ BaseLabeledVertex a = null;
+ try
+ {
+ input = new UndirectedMutableWeightedGraph<BaseLabeledVertex,
BaseLabeledWeightedEdge<Double>, Double>();
+ a = new BaseLabeledVertex( "A" );
+ BaseLabeledVertex b = new BaseLabeledVertex( "B" );
+
+ input.addVertex( a );
+ input.addVertex( b );
+
+ input.addEdge( a, new BaseLabeledWeightedEdge<Double>( "a <-> b",
7D ), b );
+ }
+ catch ( NullPointerException e )
+ {
+ fail( e.getMessage() );
+ }
+
+ minimumSpanningTree( input ).applyingReverseDeleteAlgorithm( null );
+ }
+
+ @Test
+ public void testEmptyGraph()
+ {
+ UndirectedMutableWeightedGraph<BaseLabeledVertex,
BaseLabeledWeightedEdge<Double>, Double> input =
+ new UndirectedMutableWeightedGraph<BaseLabeledVertex,
BaseLabeledWeightedEdge<Double>, Double>();
+
+ SpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>,
Double> tree =
+ minimumSpanningTree( input ).applyingReverseDeleteAlgorithm( new
DoubleWeight() );
+
+ assertEquals( 0, tree.getOrder() );
+ assertEquals( 0, tree.getSize() );
+
+ }
+
/**
* Test Graph and Reverse-Delete Algorithm
*/
