You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by si...@apache.org on 2012/01/11 22:31:15 UTC
svn commit: r1230260 - in /commons/sandbox/graph/trunk/src:
main/java/org/apache/commons/graph/ main/java/org/apache/commons/graph/model/
main/java/org/apache/commons/graph/spanning/
main/java/org/apache/commons/graph/weight/ main/java/org/apache/commo...
Author: simonetripodi
Date: Wed Jan 11 21:31:15 2012
New Revision: 1230260
URL: http://svn.apache.org/viewvc?rev=1230260&view=rev
Log:
[SANDBOX-356] applied monoid wheight to spanning trees algorithms - patch provided by Claudio Squarcella
Modified:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/SpanningTree.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/MutableSpanningTree.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/Kruskal.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/Prim.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/ShortestEdges.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Monoid.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/DoubleWeight.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/IntegerWeight.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
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/SpanningTree.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/SpanningTree.java?rev=1230260&r1=1230259&r2=1230260&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/SpanningTree.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/SpanningTree.java Wed Jan 11 21:31:15 2012
@@ -25,16 +25,12 @@ package org.apache.commons.graph;
*
* @param <V> the Graph vertices type
* @param <WE> the Graph weighted edges type
+ * @param <W> the weight type
*/
-public interface SpanningTree<V extends Vertex, WE extends WeightedEdge<Double>>
- extends UndirectedGraph<V, WE>
+public interface SpanningTree<V extends Vertex, WE extends WeightedEdge<W>, W>
+ extends UndirectedGraph<V, WE>, Weighted<W>
{
- /**
- * Gets the weight attribute of the {@code SpanningTree} object.
- *
- * @return the weight attribute of the {@code SpanningTree} object.
- */
- Double getWeight();
+
}
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/MutableSpanningTree.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/MutableSpanningTree.java?rev=1230260&r1=1230259&r2=1230260&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/MutableSpanningTree.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/MutableSpanningTree.java Wed Jan 11 21:31:15 2012
@@ -22,24 +22,34 @@ package org.apache.commons.graph.model;
import org.apache.commons.graph.SpanningTree;
import org.apache.commons.graph.Vertex;
import org.apache.commons.graph.WeightedEdge;
+import org.apache.commons.graph.weight.Monoid;
/**
* A memory-based implementation of a mutable spanning tree.
*
* @param <V> the Graph vertices type
* @param <WE> the Graph weighted edges type
+ * @param <W> the weight type
*/
-public final class MutableSpanningTree<V extends Vertex, WE extends WeightedEdge<Double>>
+public final class MutableSpanningTree<V extends Vertex, WE extends WeightedEdge<W>, W>
extends UndirectedMutableGraph<V, WE>
- implements SpanningTree<V, WE>
+ implements SpanningTree<V, WE, W>
{
- private Double weight = 0D;
+ private Monoid<W> monoid;
+ private W weight;
+
+ public MutableSpanningTree(Monoid<W> monoid) {
+ this.monoid = monoid;
+ this.weight = monoid.zero();
+ }
+
+
/**
* {@inheritDoc}
*/
- public Double getWeight()
+ public W getWeight()
{
return weight;
}
@@ -51,7 +61,7 @@ public final class MutableSpanningTree<V
protected void decorateAddEdge( V head, WE e, V tail )
{
super.decorateAddEdge( head, e, tail );
- weight += e.getWeight();
+ weight = monoid.append( weight, e.getWeight() );
}
/**
@@ -60,7 +70,7 @@ public final class MutableSpanningTree<V
@Override
protected void decorateRemoveEdge( WE e )
{
- weight -= e.getWeight();
+ weight = monoid.append( weight, monoid.inverse( e.getWeight() ) );
}
}
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/Kruskal.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/Kruskal.java?rev=1230260&r1=1230259&r2=1230260&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/Kruskal.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/Kruskal.java Wed Jan 11 21:31:15 2012
@@ -30,6 +30,8 @@ import org.apache.commons.graph.VertexPa
import org.apache.commons.graph.WeightedEdge;
import org.apache.commons.graph.collections.DisjointSet;
import org.apache.commons.graph.model.MutableSpanningTree;
+import org.apache.commons.graph.weight.OrderedMonoid;
+import org.apache.commons.graph.weight.primitive.DoubleWeight;
/**
* Kruskal's algorithm is an algorithm in graph theory that finds a minimum spanning tree
@@ -41,12 +43,15 @@ public final class Kruskal
/**
* Calculates the minimum spanning tree (or forest) of the input Graph.
*
- * @param <V> the Graph vertices type.
- * @param <WE> the Graph weighted edges type.
- * @param graph the Graph for which minimum spanning tree (or forest) has to be calculated.
- * @return the minimum spanning tree (or forest) of the input Graph.
+ * @param <V> the Graph vertices type
+ * @param <WE> the Graph weighted edges type
+ * @param <W> the weight type
+ * @param graph the Graph for which minimum spanning tree (or forest) has to be calculated
+ * @param orderedMonoid the OrderedMonoid needed for operations on weights
+ * @return the minimum spanning tree (or forest) of the input Graph
*/
- public static <V extends Vertex, WE extends WeightedEdge<Double>> SpanningTree<V, WE> minimumSpanningTree( Graph<V, WE> graph )
+ public static <V extends Vertex, W, WE extends WeightedEdge<W>> SpanningTree<V, WE, W> minimumSpanningTree( Graph<V, WE> graph,
+ OrderedMonoid<W> orderedMonoid)
{
final Set<V> settledNodes = new HashSet<V>();
@@ -59,7 +64,7 @@ public final class Kruskal
final DisjointSet<V> disjointSet = new DisjointSet<V>();
- MutableSpanningTree<V, WE> spanningTree = new MutableSpanningTree<V, WE>();
+ MutableSpanningTree<V, WE, W> spanningTree = new MutableSpanningTree<V, WE, W>( orderedMonoid );
while ( settledNodes.size() < graph.getOrder() )
{
@@ -87,5 +92,18 @@ public final class Kruskal
return spanningTree;
}
+
+ /**
+ * Calculates the minimum spanning tree (or forest) of the input Graph.
+ *
+ * @param <V> the Graph vertices type.
+ * @param <WE> the Graph weighted edges type.
+ * @param graph the Graph for which minimum spanning tree (or forest) has to be calculated.
+ * @return the minimum spanning tree (or forest) of the input Graph.
+ */
+ public static <V extends Vertex, WE extends WeightedEdge<Double>> SpanningTree<V, WE, Double> minimumSpanningTree( Graph<V, WE> graph )
+ {
+ return minimumSpanningTree( graph, new DoubleWeight() );
+ }
}
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/Prim.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/Prim.java?rev=1230260&r1=1230259&r2=1230260&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/Prim.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/Prim.java Wed Jan 11 21:31:15 2012
@@ -27,44 +27,52 @@ import org.apache.commons.graph.Spanning
import org.apache.commons.graph.UndirectedGraph;
import org.apache.commons.graph.Vertex;
import org.apache.commons.graph.WeightedEdge;
+import org.apache.commons.graph.weight.OrderedMonoid;
+import org.apache.commons.graph.weight.primitive.DoubleWeight;
/**
* Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a connected weighted undirected graph.
*/
public final class Prim
{
-
+
/**
* Calculates the minimum spanning tree of the input Graph,
* selecting the Vertex source from the input Graph.
*
- * @param <V> the Graph vertices type.
- * @param <WE> the Graph weighted edges type.
+ * @param <V> the Graph vertices type
+ * @param <WE> the Graph weighted edges type
+ * @param <W> the weight type
* @param <G> the weighted-undirected input graph type
- * @param graph the Graph for which minimum spanning tree has to be calculated.
- * @return the minimum spanning tree of the input Graph.
+ * @param graph the Graph for which minimum spanning tree has to be calculated
+ * @param orderedMonoid the OrderedMonoid needed to handle operations on weights
+ * @return the minimum spanning tree of the input Graph
*/
- public static <V extends Vertex, WE extends WeightedEdge<Double>, G extends UndirectedGraph<V, WE>> SpanningTree<V, WE> minimumSpanningTree( G graph )
+ public static <V extends Vertex, WE extends WeightedEdge<W>, W, G extends UndirectedGraph<V, WE>> SpanningTree<V, WE, W> minimumSpanningTree( G graph,
+ OrderedMonoid<W> orderedMonoid)
{
- return minimumSpanningTree( graph, graph.getVertices().iterator().next() );
+ return minimumSpanningTree( graph, graph.getVertices().iterator().next(), orderedMonoid );
}
/**
* Calculates the minimum spanning tree of the input Graph, given a known Vertex source.
*
- * @param <V> the Graph vertices type.
- * @param <WE> the Graph weighted edges type.
+ * @param <V> the Graph vertices type
+ * @param <WE> the Graph weighted edges type
+ * @param <W> the weight type
* @param <G> the weighted-undirected input graph type
- * @param graph the Graph for which minimum spanning tree has to be calculated.
+ * @param graph the Graph for which minimum spanning tree has to be calculated
* @param source the Prim's Vertex source
- * @return the minimum spanning tree of the input Graph.
+ * @param orderedMonoid the OrderedMonoid needed to handle operations on weights
+ * @return the minimum spanning tree of the input Graph
*/
- public static <V extends Vertex, WE extends WeightedEdge<Double>, G extends UndirectedGraph<V, WE>> SpanningTree<V, WE> minimumSpanningTree( G graph,
- V source )
+ public static <V extends Vertex, WE extends WeightedEdge<W>, W, G extends UndirectedGraph<V, WE>> SpanningTree<V, WE, W> minimumSpanningTree( G graph,
+ V source,
+ OrderedMonoid<W> orderedMonoid )
{
- final ShortestEdges<V, WE> shortesEdges = new ShortestEdges<V, WE>( graph, source );
+ final ShortestEdges<V, WE, W> shortestEdges = new ShortestEdges<V, WE, W>( graph, source, orderedMonoid );
- final PriorityQueue<V> unsettledNodes = new PriorityQueue<V>( graph.getOrder(), shortesEdges );
+ final PriorityQueue<V> unsettledNodes = new PriorityQueue<V>( graph.getOrder(), shortestEdges );
unsettledNodes.add( source );
final Set<WE> settledEdges = new HashSet<WE>();
@@ -79,19 +87,53 @@ public final class Prim
WE edge = graph.getEdge( vertex, v );
// if the edge has not been already visited and its weight is less then the current Vertex weight
- if ( settledEdges.add( edge ) && edge.getWeight().compareTo( shortesEdges.getWeight( v ) ) < 0 )
+ boolean weightLessThanCurrent = !shortestEdges.hasWeight( v )
+ || orderedMonoid.compare( edge.getWeight(), shortestEdges.getWeight( v ) ) < 0;
+ if ( settledEdges.add( edge ) && weightLessThanCurrent )
{
if ( !unsettledNodes.contains( v ) )
{
unsettledNodes.add( v );
}
- shortesEdges.addPredecessor( v, edge );
+ shortestEdges.addPredecessor( v, edge );
}
}
}
- return shortesEdges.createSpanningTree();
+ return shortestEdges.createSpanningTree();
+ }
+
+ /**
+ * Calculates the minimum spanning tree of the input edge weighted Graph with weights of type Double,
+ * selecting the Vertex source from the input Graph.
+ *
+ * @param <V> the Graph vertices type.
+ * @param <WE> the Graph weighted edges type.
+ * @param <G> the weighted-undirected input graph type
+ * @param graph the Graph for which minimum spanning tree has to be calculated.
+ * @return the minimum spanning tree of the input Graph.
+ */
+ public static <V extends Vertex, WE extends WeightedEdge<Double>, G extends UndirectedGraph<V, WE>> SpanningTree<V, WE, Double> minimumSpanningTree( G graph )
+ {
+ return minimumSpanningTree( graph, graph.getVertices().iterator().next(), new DoubleWeight() );
+ }
+
+ /**
+ * Calculates the minimum spanning tree of the input edge weighted Graph with weights of type Double,
+ * given a known Vertex source.
+ *
+ * @param <V> the Graph vertices type
+ * @param <WE> the Graph weighted edges type
+ * @param <G> the weighted-undirected input graph type
+ * @param graph the Graph for which minimum spanning tree has to be calculated
+ * @param source the Prim's Vertex source
+ * @return the minimum spanning tree of the input Graph
+ */
+ public static <V extends Vertex, WE extends WeightedEdge<Double>, G extends UndirectedGraph<V, WE>> SpanningTree<V, WE, Double> minimumSpanningTree( G graph,
+ V source )
+ {
+ return minimumSpanningTree( graph, source, new DoubleWeight() );
}
}
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/ShortestEdges.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/ShortestEdges.java?rev=1230260&r1=1230259&r2=1230260&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/ShortestEdges.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/ShortestEdges.java Wed Jan 11 21:31:15 2012
@@ -31,6 +31,7 @@ import org.apache.commons.graph.Vertex;
import org.apache.commons.graph.VertexPair;
import org.apache.commons.graph.WeightedEdge;
import org.apache.commons.graph.model.MutableSpanningTree;
+import org.apache.commons.graph.weight.OrderedMonoid;
/**
* The predecessor list is a list of {@link Vertex} of a {@link org.apache.commons.graph.Graph}.
@@ -38,21 +39,25 @@ import org.apache.commons.graph.model.Mu
*
* @param <V> the Graph vertices type
* @param <E> the Graph edges type
+ * @param <W> the weight type
*/
-final class ShortestEdges<V extends Vertex, WE extends WeightedEdge<Double>>
+final class ShortestEdges<V extends Vertex, WE extends WeightedEdge<W>, W>
implements Comparator<V>
{
private final Map<V, WE> predecessors = new HashMap<V, WE>();
+ private final OrderedMonoid<W> orderedMonoid;
+
private final Graph<V, WE> graph;
private final V source;
- public ShortestEdges(Graph<V, WE> graph, V source )
+ public ShortestEdges(Graph<V, WE> graph, V source, OrderedMonoid<W> orderedMonoid )
{
this.graph = graph;
this.source = source;
+ this.orderedMonoid = orderedMonoid;
}
/**
@@ -67,13 +72,13 @@ final class ShortestEdges<V extends Vert
}
/**
- *
+ * Creates a spanning tree using the current data.
*
- * @return
+ * @return a spanning tree using current data
*/
- public SpanningTree<V, WE> createSpanningTree()
+ public SpanningTree<V, WE, W> createSpanningTree()
{
- MutableSpanningTree<V, WE> spanningTree = new MutableSpanningTree<V, WE>();
+ MutableSpanningTree<V, WE, W> spanningTree = new MutableSpanningTree<V, WE, W>( orderedMonoid );
for ( WE edge : this.predecessors.values() )
{
@@ -91,8 +96,8 @@ final class ShortestEdges<V extends Vert
return spanningTree;
}
- private static <V extends Vertex, WE extends WeightedEdge<Double>> void addEdgeIgnoringExceptions( V vertex,
- MutableSpanningTree<V, WE> spanningTree )
+ private static <V extends Vertex, WE extends WeightedEdge<W>, W> void addEdgeIgnoringExceptions( V vertex,
+ MutableSpanningTree<V, WE, W> spanningTree )
{
try
{
@@ -115,34 +120,60 @@ final class ShortestEdges<V extends Vert
}
/**
- * Returns the distance related to input vertex, or {@code INFINITY} if it wasn't previously visited.
+ * Returns the distance related to input vertex, or null if it does not exist.
+ *
+ * <b>NOTE</b>: the method {@link hasWeight} should be used first to check if
+ * the input vertex has an assiged weight.
*
* @param vertex the vertex for which the distance has to be retrieved
- * @return the distance related to input vertex, or {@code INFINITY} if it wasn't previously visited.
+ * @return the distance related to input vertex, or null if it does not exist
*/
- public Double getWeight( V vertex )
+ public W getWeight( V vertex )
{
if ( source.equals( vertex ) )
{
- return 0D;
+ return orderedMonoid.zero();
}
WE edge = predecessors.get( vertex );
if ( edge == null )
{
- return Double.POSITIVE_INFINITY;
+ return null;
}
return edge.getWeight();
}
+
+ /**
+ * Checks if there is a weight related to the input {@code Vertex}.
+ *
+ * @param vertex the input {@code Vertex}
+ * @return true if there is a weight for the input {@code Vertex}, false otherwise
+ */
+ public boolean hasWeight( V vertex )
+ {
+ return predecessors.containsKey( vertex );
+ }
/**
* {@inheritDoc}
*/
public int compare( V left, V right )
{
- return getWeight( left ).compareTo( getWeight( right ) );
+ if ( !hasWeight( left ) && !hasWeight( right ) )
+ {
+ return 0;
+ }
+ else if ( !hasWeight( left ) )
+ {
+ return 1;
+ }
+ else if ( !hasWeight( right ) )
+ {
+ return -1;
+ }
+ return orderedMonoid.compare( getWeight( left ), getWeight( right ) );
}
/**
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Monoid.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Monoid.java?rev=1230260&r1=1230259&r2=1230260&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Monoid.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Monoid.java Wed Jan 11 21:31:15 2012
@@ -28,4 +28,11 @@ public interface Monoid<M>
extends Zero<M>, Semigroup<M>
{
+ /**
+ * Returns the inverse of the input element.
+ * @param element
+ * @return the inverse of the input element
+ */
+ public M inverse( M element );
+
}
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/DoubleWeight.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/DoubleWeight.java?rev=1230260&r1=1230259&r2=1230260&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/DoubleWeight.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/DoubleWeight.java Wed Jan 11 21:31:15 2012
@@ -48,6 +48,14 @@ public class DoubleWeight
}
return s1 + s2;
}
+
+ /**
+ * {@inheritDoc}
+ */
+ public Double inverse( Double element )
+ {
+ return -element;
+ }
/**
* {@inheritDoc}
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/IntegerWeight.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/IntegerWeight.java?rev=1230260&r1=1230259&r2=1230260&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/IntegerWeight.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/IntegerWeight.java Wed Jan 11 21:31:15 2012
@@ -22,7 +22,7 @@ package org.apache.commons.graph.weight.
import org.apache.commons.graph.weight.OrderedMonoid;
/**
- * A {@link IntegerWeight} provides operations and properties
+ * An {@link IntegerWeight} provides operations and properties
* for weights of type {@link Integer}.
*/
public class IntegerWeight
@@ -48,6 +48,14 @@ public class IntegerWeight
}
return s1 + s2;
}
+
+ /**
+ * {@inheritDoc}
+ */
+ public Integer inverse( Integer element )
+ {
+ return -element;
+ }
/**
* {@inheritDoc}
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=1230260&r1=1230259&r2=1230260&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 Wed Jan 11 21:31:15 2012
@@ -27,6 +27,7 @@ import org.apache.commons.graph.model.Ba
import org.apache.commons.graph.model.BaseLabeledWeightedEdge;
import org.apache.commons.graph.model.MutableSpanningTree;
import org.apache.commons.graph.model.UndirectedMutableWeightedGraph;
+import org.apache.commons.graph.weight.primitive.DoubleWeight;
import org.junit.Test;
public final class KruskalTestCase
@@ -77,8 +78,8 @@ public final class KruskalTestCase
// expected
- MutableSpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge> expected =
- new MutableSpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge>();
+ MutableSpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge, Double> expected =
+ new MutableSpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge, Double>( new DoubleWeight() );
for ( BaseLabeledVertex vertex : input.getVertices() )
{
@@ -94,7 +95,7 @@ public final class KruskalTestCase
// Actual
- SpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge> actual = minimumSpanningTree( input );
+ SpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge, Double> actual = minimumSpanningTree( input );
// assert!
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=1230260&r1=1230259&r2=1230260&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 Wed Jan 11 21:31:15 2012
@@ -27,6 +27,7 @@ import org.apache.commons.graph.model.Ba
import org.apache.commons.graph.model.BaseLabeledWeightedEdge;
import org.apache.commons.graph.model.MutableSpanningTree;
import org.apache.commons.graph.model.UndirectedMutableWeightedGraph;
+import org.apache.commons.graph.weight.primitive.DoubleWeight;
import org.junit.Test;
public final class PrimTestCase
@@ -74,8 +75,8 @@ public final class PrimTestCase
// expected
- MutableSpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge> expected =
- new MutableSpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge>();
+ MutableSpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge, Double> expected =
+ new MutableSpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge, Double>( new DoubleWeight() );
for ( BaseLabeledVertex vertex : input.getVertices() )
{
@@ -140,8 +141,8 @@ public final class PrimTestCase
// expected
- MutableSpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge> expected =
- new MutableSpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge>();
+ MutableSpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge, Double> expected =
+ new MutableSpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge, Double>( new DoubleWeight() );
for ( BaseLabeledVertex vertex : input.getVertices() )
{
@@ -160,11 +161,11 @@ public final class PrimTestCase
private static void internalPrimAssertion( UndirectedMutableWeightedGraph<BaseLabeledVertex, BaseLabeledWeightedEdge> input,
BaseLabeledVertex source,
- MutableSpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge> expected )
+ MutableSpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge, Double> expected )
{
// actual
- SpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge> actual = minimumSpanningTree( input, source );
+ SpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge, Double> actual = minimumSpanningTree( input, source );
// assert!