commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From simonetrip...@apache.org
Subject svn commit: r1228934 - in /commons/sandbox/graph/trunk/src: changes/ main/java/org/apache/commons/graph/ main/java/org/apache/commons/graph/model/ main/java/org/apache/commons/graph/shortestpath/ main/java/org/apache/commons/graph/weight/ main/java/org...
Date Sun, 08 Jan 2012 19:42:52 GMT
Author: simonetripodi
Date: Sun Jan  8 19:42:51 2012
New Revision: 1228934

URL: http://svn.apache.org/viewvc?rev=1228934&view=rev
Log:
[SANDBOX-356] Generic weight types and updated shortest path implementations - patch provided by Claudio Squarcella

Added:
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Monoid.java   (with props)
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/OrderedMonoid.java   (with props)
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Semigroup.java   (with props)
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Zero.java   (with props)
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/package-info.java   (with props)
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/DoubleWeight.java   (with props)
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/IntegerWeight.java   (with props)
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/package-info.java   (with props)
Modified:
    commons/sandbox/graph/trunk/src/changes/changes.xml
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/Weighted.java
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/WeightedEdge.java
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/InMemoryWeightedPath.java
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/AStar.java
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/AllVertexPairsShortestPath.java
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/BellmannFord.java
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/Dijkstra.java
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/FloydWarshall.java
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PredecessorsList.java
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/ShortestDistances.java
    commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/AStarTestCase.java
    commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/BellmannFordTestCase.java
    commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/DijkstraTestCase.java
    commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/FloydWarshallTestCase.java
    commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/KruskalTestCase.java

Modified: commons/sandbox/graph/trunk/src/changes/changes.xml
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/changes/changes.xml?rev=1228934&r1=1228933&r2=1228934&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/changes/changes.xml (original)
+++ commons/sandbox/graph/trunk/src/changes/changes.xml Sun Jan  8 19:42:51 2012
@@ -23,6 +23,9 @@
   </properties>
   <body>
   <release version="0.1" date="201?-??-??" description="First release.">
+    <action dev="simonetripodi" type="update" issue="SANDBOX-356">
+      Generic weight types and updated shortest path implementations - patch provided by Claudio Squarcella
+    </action>
     <action dev="simonetripodi" type="update" issue="SANDBOX-346">
       DotExporter only exports weights that extend Number - patch provided by Claudio Squarcella
     </action>

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/Weighted.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/Weighted.java?rev=1228934&r1=1228933&r2=1228934&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/Weighted.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/Weighted.java Sun Jan  8 19:42:51 2012
@@ -33,6 +33,6 @@ public interface Weighted<W>
      *
      * @return the weight of the {@code Weighted} object.
      */
-    public W getWeight();
+    W getWeight();
 
 }

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/WeightedEdge.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/WeightedEdge.java?rev=1228934&r1=1228933&r2=1228934&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/WeightedEdge.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/WeightedEdge.java Sun Jan  8 19:42:51 2012
@@ -22,6 +22,8 @@ package org.apache.commons.graph;
 /**
  * A WeightedEdge is an {@link Edge} that is assigned a weight to represent, for example,
  * costs, lengths or capacities, etc. depending on the problem.
+ * 
+ * @param <W> the weight type
  */
 public interface WeightedEdge<W>
     extends Edge, Weighted<W>, Comparable<WeightedEdge<W>>

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/InMemoryWeightedPath.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/InMemoryWeightedPath.java?rev=1228934&r1=1228933&r2=1228934&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/InMemoryWeightedPath.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/InMemoryWeightedPath.java Sun Jan  8 19:42:51 2012
@@ -24,6 +24,7 @@ import static java.lang.String.format;
 import org.apache.commons.graph.Vertex;
 import org.apache.commons.graph.WeightedEdge;
 import org.apache.commons.graph.WeightedPath;
+import org.apache.commons.graph.weight.Monoid;
 
 /**
  * Support {@link WeightedPath} implementation, optimized for algorithms (such Dijkstra's) that need to rebuild the path
@@ -31,17 +32,21 @@ import org.apache.commons.graph.Weighted
  *
  * @param <V> the Graph vertices type
  * @param <WE> the Graph weighted edges type
+ * @param <W> the weight type
  */
-public final class InMemoryWeightedPath<V extends Vertex, WE extends WeightedEdge<Double>>
+public final class InMemoryWeightedPath<V extends Vertex, WE extends WeightedEdge<W>, W>
     extends InMemoryPath<V, WE>
-    implements WeightedPath<V, WE, Double>
+    implements WeightedPath<V, WE, W>
 {
 
-    private Double weigth = 0D;
+    private W weight;
+    private Monoid<W> monoid;
 
-    public InMemoryWeightedPath( V start, V target )
+    public InMemoryWeightedPath( V start, V target, Monoid<W> monoid )
     {
         super( start, target );
+        this.monoid = monoid;
+        this.weight = monoid.zero();
     }
 
     /**
@@ -65,21 +70,21 @@ public final class InMemoryWeightedPath<
     }
 
     /**
-     * Increase the path weight
+     * Increase the path weight with the weight of the input weighted edge.
      *
-     * @param edge the edge which weigth increase the path weigth
+     * @param edge the edge whose weight is used to increase the path weight
      */
     private void increaseWeight( WE edge )
     {
-        weigth = edge.getWeight().doubleValue() + weigth.doubleValue();
+        weight = monoid.append( edge.getWeight(), weight );
     }
 
     /**
      * {@inheritDoc}
      */
-    public Double getWeight()
+    public W getWeight()
     {
-        return weigth;
+        return weight;
     }
 
     /**
@@ -90,7 +95,7 @@ public final class InMemoryWeightedPath<
     {
         final int prime = 31;
         int result = super.hashCode();
-        result = prime * result + ( ( weigth == null ) ? 0 : weigth.hashCode() );
+        result = prime * result + ( ( weight == null ) ? 0 : weight.hashCode() );
         return result;
     }
 
@@ -116,8 +121,8 @@ public final class InMemoryWeightedPath<
         }
 
         @SuppressWarnings( "unchecked" ) // test against any WeightedPath typed instance
-        InMemoryWeightedPath<Vertex, WeightedEdge<Double>> other = (InMemoryWeightedPath<Vertex, WeightedEdge<Double>>) obj;
-        if ( !weigth.equals( other.getWeight() ) )
+        InMemoryWeightedPath<Vertex, WeightedEdge<W>, W> other = (InMemoryWeightedPath<Vertex, WeightedEdge<W>, W>) obj;
+        if ( !weight.equals( other.getWeight() ) )
         {
             return false;
         }
@@ -130,7 +135,7 @@ public final class InMemoryWeightedPath<
     @Override
     public String toString()
     {
-        return format( "InMemoryPath [weigth=%s, vertices=%s, edges=%s]", weigth, getVertices(), getEdges() );
+        return format( "InMemoryPath [weigth=%s, vertices=%s, edges=%s]", weight, getVertices(), getEdges() );
     }
 
 }

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/AStar.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/AStar.java?rev=1228934&r1=1228933&r2=1228934&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/AStar.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/AStar.java Sun Jan  8 19:42:51 2012
@@ -29,6 +29,7 @@ import org.apache.commons.graph.Vertex;
 import org.apache.commons.graph.WeightedEdge;
 import org.apache.commons.graph.WeightedPath;
 import org.apache.commons.graph.collections.FibonacciHeap;
+import org.apache.commons.graph.weight.primitive.DoubleWeight;
 
 /**
  * Contains the A* shortest path algorithm implementation.
@@ -36,6 +37,8 @@ import org.apache.commons.graph.collecti
 public final class AStar
 {
 
+    private static final DoubleWeight DOUBLE_WEIGHT = new DoubleWeight();
+
     /**
      * This class can not be instantiated directly
      */
@@ -61,11 +64,11 @@ public final class AStar
                                                                                                                     Heuristic<V> heuristic )
     {
         // Cost from start along best known path.
-        final ShortestDistances<V> gScores = new ShortestDistances<V>();
+        final ShortestDistances<V, Double> gScores = new ShortestDistances<V, Double>( DOUBLE_WEIGHT );
         gScores.setWeight( start, 0D );
 
         // Estimated total cost from start to goal through y.
-        final ShortestDistances<V> fScores = new ShortestDistances<V>();
+        final ShortestDistances<V, Double> fScores = new ShortestDistances<V, Double>( DOUBLE_WEIGHT );
         Double hScore = heuristic.applyHeuristic( start, goal );
         fScores.setWeight( start, hScore );
 
@@ -77,7 +80,7 @@ public final class AStar
         openSet.add( start );
 
         // The of navigated nodes
-        final PredecessorsList<V, WE> predecessors = new PredecessorsList<V, WE>( graph );
+        final PredecessorsList<V, WE, Double> predecessors = new PredecessorsList<V, WE, Double>( graph, DOUBLE_WEIGHT );
 
         // extract the node in openset having the lowest f_score[] value
         while ( !openSet.isEmpty() )
@@ -99,8 +102,10 @@ public final class AStar
                 if ( !closedSet.contains( v ) )
                 {
                     WE edge = graph.getEdge( current, v );
+                    // note that the weight of current can never be undefined
                     Double tentativeGScore = gScores.getWeight( current ) + edge.getWeight();
 
+                    // if the first condition fails, v has already been visited (its weight is defined)
                     if ( openSet.add( v ) || tentativeGScore.compareTo( gScores.getWeight( v ) ) < 0 )
                     {
                         predecessors.addPredecessor( v, current );

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/AllVertexPairsShortestPath.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/AllVertexPairsShortestPath.java?rev=1228934&r1=1228933&r2=1228934&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/AllVertexPairsShortestPath.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/AllVertexPairsShortestPath.java Sun Jan  8 19:42:51 2012
@@ -26,26 +26,30 @@ import org.apache.commons.graph.Vertex;
 import org.apache.commons.graph.VertexPair;
 import org.apache.commons.graph.WeightedEdge;
 import org.apache.commons.graph.WeightedPath;
+import org.apache.commons.graph.weight.OrderedMonoid;
 
 /**
  * Represents all shortest paths between all vertex pairs calculated by {@link FloydWarshall} algorithm.
- * 
+ *
  * @param <V> the Graph vertices type
- * @param <E> the Graph edges type
+ * @param <WE> the Graph weighted edges type
+ * @param <W> the weight type
  */
-public final class AllVertexPairsShortestPath<V extends Vertex, WE extends WeightedEdge<Double>>
+public final class AllVertexPairsShortestPath<V extends Vertex, WE extends WeightedEdge<W>, W>
 {
 
-    private final Map<VertexPair<V>, WeightedPath<V, WE, Double>> paths = new HashMap<VertexPair<V>, WeightedPath<V, WE, Double>>();
+    private final Map<VertexPair<V>, WeightedPath<V, WE, W>> paths = new HashMap<VertexPair<V>, WeightedPath<V, WE, W>>();
 
-    private final Map<VertexPair<V>, Double> shortestDistances = new HashMap<VertexPair<V>, Double>();
+    private final Map<VertexPair<V>, W> shortestDistances = new HashMap<VertexPair<V>, W>();
+
+    private final OrderedMonoid<W> orderedMonoid;
 
     /**
      * Constructor visible only inside the package
      */
-    AllVertexPairsShortestPath()
+    AllVertexPairsShortestPath( OrderedMonoid<W> orderedMonoid )
     {
-        // do nothing
+        this.orderedMonoid = orderedMonoid;
     }
 
     /**
@@ -53,7 +57,7 @@ public final class AllVertexPairsShortes
      * @param target
      * @param weightedPath
      */
-    void addShortestPath( V source, V target, WeightedPath<V, WE, Double> weightedPath )
+    void addShortestPath( V source, V target, WeightedPath<V, WE, W> weightedPath )
     {
         if ( source == null )
         {
@@ -73,12 +77,12 @@ public final class AllVertexPairsShortes
 
     /**
      * Returns the shortest path between source and target
-     * 
+     *
      * @param source The source Vertex
      * @param target The target Vertex
      * @return Returns the shortest path between source and target
      */
-    public WeightedPath<V, WE, Double> findShortestPath( V source, V target )
+    public WeightedPath<V, WE, W> findShortestPath( V source, V target )
     {
         if ( source == null )
         {
@@ -89,7 +93,7 @@ public final class AllVertexPairsShortes
             throw new IllegalArgumentException( "Impossible to find the shortest path to a null target" );
         }
 
-        WeightedPath<V, WE, Double> path = paths.get( new VertexPair<V>( source, target ) );
+        WeightedPath<V, WE, W> path = paths.get( new VertexPair<V>( source, target ) );
 
         if ( path == null )
         {
@@ -104,7 +108,7 @@ public final class AllVertexPairsShortes
      * @param target
      * @param distance
      */
-    void addShortestDistance( V source, V target, Double distance )
+    void addShortestDistance( V source, V target, W distance )
     {
         if ( source == null )
         {
@@ -124,12 +128,12 @@ public final class AllVertexPairsShortes
 
     /**
      * Returns the shortest distance between source and target.
-     * 
+     *
      * @param source The source Vertex
      * @param target The target Vertex
      * @return Returns the shortest distance between source and target.
      */
-    Double getShortestDistance( V source, V target )
+    W getShortestDistance( V source, V target )
     {
         if ( source == null )
         {
@@ -142,17 +146,36 @@ public final class AllVertexPairsShortes
 
         if ( source.equals( target ) )
         {
-            return 0D;
+            return orderedMonoid.zero();
         }
 
-        Double distance = shortestDistances.get( new VertexPair<V>( source, target ) );
+        return shortestDistances.get( new VertexPair<V>( source, target ) );
+    }
 
-        if ( distance == null )
+    /**
+     * Checks if there is a shortest distance between source and target.
+     *
+     * @param source The source Vertex
+     * @param target The target Vertex
+     * @return Returns true if there is a shortest distance between source and target, false otherwise.
+     */
+    boolean hasShortestDistance( V source, V target )
+    {
+        if ( source == null )
+        {
+            throw new IllegalArgumentException( "Impossible to get the shortest distance from a null source" );
+        }
+        if ( target == null )
+        {
+            throw new IllegalArgumentException( "Impossible to get the shortest distance to a null target" );
+        }
+
+        if ( source.equals( target ) )
         {
-            return Double.POSITIVE_INFINITY;
+            return true;
         }
 
-        return distance;
+        return shortestDistances.containsKey( new VertexPair<V>( source, target ) );
     }
 
     @Override

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/BellmannFord.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/BellmannFord.java?rev=1228934&r1=1228933&r2=1228934&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/BellmannFord.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/BellmannFord.java Sun Jan  8 19:42:51 2012
@@ -1,11 +1,5 @@
 package org.apache.commons.graph.shortestpath;
 
-import org.apache.commons.graph.DirectedGraph;
-import org.apache.commons.graph.Vertex;
-import org.apache.commons.graph.VertexPair;
-import org.apache.commons.graph.WeightedEdge;
-import org.apache.commons.graph.WeightedPath;
-
 /*
  * Licensed to the Apache Software Foundation (ASF) under one
  * or more contributor license agreements.  See the NOTICE file
@@ -25,6 +19,14 @@ import org.apache.commons.graph.Weighted
  * under the License.
  */
 
+import org.apache.commons.graph.DirectedGraph;
+import org.apache.commons.graph.Vertex;
+import org.apache.commons.graph.VertexPair;
+import org.apache.commons.graph.WeightedEdge;
+import org.apache.commons.graph.WeightedPath;
+import org.apache.commons.graph.weight.OrderedMonoid;
+import org.apache.commons.graph.weight.primitive.DoubleWeight;
+
 /**
  * Contains the BellmanÐFord's shortest path algorithm implementation.
  */
@@ -42,20 +44,23 @@ public final class BellmannFord
     /**
      * Applies the classical BellmanÐFord's algorithm to find the shortest path from the source to the target, if exists.
      *
-     * @param <V> the Graph vertices type.
+     * @param <V> the Graph vertices type
      * @param <WE> the Graph weighted edges type
-     * @param graph the Graph which shortest path from {@code source} to {@code target} has to be found
+     * @param <W> the weight type
+     * @param <G> the Graph type
+     * @param graph the Graph whose shortest path from {@code source} to {@code target} has to be found
      * @param source the shortest path source Vertex
-     * @param target the shortest path target Vertex
+     * @param orderedMonoid the {@code OrderedMonoid} needed to handle weights
      * @return a path which describes the shortest path, if any, otherwise a {@link PathNotFoundException} will be thrown
      */
-    public static <V extends Vertex, WE extends WeightedEdge<Double>, G extends DirectedGraph<V, WE>> AllVertexPairsShortestPath<V, WE> findShortestPath( G graph,
-                                                                                                                                                          V source)
+    public static <V extends Vertex, W, WE extends WeightedEdge<W>, G extends DirectedGraph<V, WE>> AllVertexPairsShortestPath<V, WE, W> findShortestPath( G graph,
+                                                                                                                                                           V source,
+                                                                                                                                                           OrderedMonoid<W> orderedMonoid )
     {
-        final ShortestDistances<V> shortestDistances = new ShortestDistances<V>();
-        shortestDistances.setWeight( source, 0D );
+        final ShortestDistances<V, W> shortestDistances = new ShortestDistances<V, W>( orderedMonoid );
+        shortestDistances.setWeight( source, orderedMonoid.zero() );
 
-        final PredecessorsList<V, WE> predecessors = new PredecessorsList<V, WE>( graph );
+        final PredecessorsList<V, WE, W> predecessors = new PredecessorsList<V, WE, W>( graph, orderedMonoid );
 
         for ( int i = 0; i < graph.getOrder(); i++ )
         {
@@ -65,15 +70,19 @@ public final class BellmannFord
                 V u = vertexPair.getHead();
                 V v = vertexPair.getTail();
 
-                Double shortDist = shortestDistances.getWeight( u ) + edge.getWeight();
-
-                if ( shortDist.compareTo( shortestDistances.getWeight( v ) ) < 0 )
+                if ( shortestDistances.alreadyVisited( u ) )
                 {
-                    // assign new shortest distance and mark unsettled
-                    shortestDistances.setWeight( v, shortDist );
+                    W shortDist = orderedMonoid.append( shortestDistances.getWeight( u ), edge.getWeight() );
 
-                    // assign predecessor in shortest path
-                    predecessors.addPredecessor( v, u );
+                    if ( !shortestDistances.alreadyVisited( v )
+                            || orderedMonoid.compare( shortDist, shortestDistances.getWeight( v ) ) < 0 )
+                    {
+                        // assign new shortest distance and mark unsettled
+                        shortestDistances.setWeight( v, shortDist );
+
+                        // assign predecessor in shortest path
+                        predecessors.addPredecessor( v, u );
+                    }
                 }
             }
         }
@@ -84,23 +93,27 @@ public final class BellmannFord
             V u = vertexPair.getHead();
             V v = vertexPair.getTail();
 
-            Double shortDist = shortestDistances.getWeight( u ) + edge.getWeight();
-
-            if ( shortDist.compareTo( shortestDistances.getWeight( v ) ) < 0 )
+            if ( shortestDistances.alreadyVisited( u ) )
             {
-                // TODO it would be nice printing the cycle
-                throw new NegativeWeightedCycleException( "Graph contains a negative-weight cycle in vertex %s",
-                                                          v, graph );
+                W shortDist = orderedMonoid.append( shortestDistances.getWeight( u ), edge.getWeight() );
+
+                if ( !shortestDistances.alreadyVisited( v )
+                        || orderedMonoid.compare( shortDist, shortestDistances.getWeight( v ) ) < 0 )
+                {
+                    // TODO it would be nice printing the cycle
+                    throw new NegativeWeightedCycleException( "Graph contains a negative-weight cycle in vertex %s",
+                                                              v, graph );
+                }
             }
         }
 
-        AllVertexPairsShortestPath<V, WE> allVertexPairsShortestPath = new AllVertexPairsShortestPath<V, WE>();
+        AllVertexPairsShortestPath<V, WE, W> allVertexPairsShortestPath = new AllVertexPairsShortestPath<V, WE, W>( orderedMonoid );
 
         for ( V target : graph.getVertices() )
         {
             if ( !source.equals( target ) )
             {
-                WeightedPath<V, WE, Double> weightedPath = predecessors.buildPath( source, target );
+                WeightedPath<V, WE, W> weightedPath = predecessors.buildPath( source, target );
                 allVertexPairsShortestPath.addShortestPath( source, target, weightedPath );
             }
         }
@@ -108,4 +121,21 @@ public final class BellmannFord
         return allVertexPairsShortestPath;
     }
 
+    /**
+     * Applies the classical BellmanÐFord's algorithm to an edge weighted graph with weights of type Double
+     * to find the shortest path from the source to the target, if exists.
+     *
+     * @param <V> the Graph vertices type
+     * @param <WE> the Graph weighted edges type
+     * @param <G> the Graph type
+     * @param graph the Graph whose shortest path from {@code source} to {@code target} has to be found
+     * @param source the shortest path source Vertex
+     * @return a path which describes the shortest path, if any, otherwise a {@link PathNotFoundException} will be thrown
+     */
+    public static <V extends Vertex, WE extends WeightedEdge<Double>, G extends DirectedGraph<V, WE>> AllVertexPairsShortestPath<V, WE, Double> findShortestPath( G graph,
+                                                                                                                                                                  V source )
+    {
+        return findShortestPath( graph, source, new DoubleWeight() );
+    }
+
 }

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/Dijkstra.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/Dijkstra.java?rev=1228934&r1=1228933&r2=1228934&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/Dijkstra.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/Dijkstra.java Sun Jan  8 19:42:51 2012
@@ -28,6 +28,8 @@ import org.apache.commons.graph.Vertex;
 import org.apache.commons.graph.WeightedEdge;
 import org.apache.commons.graph.WeightedPath;
 import org.apache.commons.graph.collections.FibonacciHeap;
+import org.apache.commons.graph.weight.OrderedMonoid;
+import org.apache.commons.graph.weight.primitive.DoubleWeight;
 
 /**
  * Contains the Dijkstra's shortest path algorithm implementation.
@@ -46,27 +48,31 @@ public final class Dijkstra
     /**
      * Applies the classical Dijkstra's algorithm to find the shortest path from the source to the target, if exists.
      *
-     * @param <V> the Graph vertices type.
+     * @param <V> the Graph vertices type
+     * @param <W> the weight type
      * @param <WE> the Graph weighted edges type
-     * @param graph the Graph which shortest path from {@code source} to {@code target} has to be found
+     * @param <G> the Graph type
+     * @param graph the Graph whose shortest path from {@code source} to {@code target} has to be found
      * @param source the shortest path source Vertex
      * @param target the shortest path target Vertex
+     * @param orderedMonoid the {@link OrderedMonoid} needed to handle operations on weights
      * @return a path which describes the shortest path, if any,
      *         otherwise a {@link PathNotFoundException} will be thrown
      */
-    public static <V extends Vertex, WE extends WeightedEdge<Double>, G extends DirectedGraph<V, WE>> WeightedPath<V, WE, Double> findShortestPath( G graph,
-                                                                                                                                                    V source,
-                                                                                                                                                    V target )
+    public static <V extends Vertex, W, WE extends WeightedEdge<W>, G extends DirectedGraph<V, WE>> WeightedPath<V, WE, W> findShortestPath( G graph,
+                                                                                                                                             V source,
+                                                                                                                                             V target,
+                                                                                                                                             OrderedMonoid<W> orderedMonoid )
     {
-        final ShortestDistances<V> shortestDistances = new ShortestDistances<V>();
-        shortestDistances.setWeight( source, 0D );
+        final ShortestDistances<V, W> shortestDistances = new ShortestDistances<V, W>( orderedMonoid );
+        shortestDistances.setWeight( source, orderedMonoid.zero() );
 
         final Queue<V> unsettledNodes = new FibonacciHeap<V>( shortestDistances );
         unsettledNodes.add( source );
 
         final Set<V> settledNodes = new HashSet<V>();
 
-        final PredecessorsList<V, WE> predecessors = new PredecessorsList<V, WE>( graph );
+        final PredecessorsList<V, WE, W> predecessors = new PredecessorsList<V, WE, W>( graph, orderedMonoid );
 
         // extract the node with the shortest distance
         while ( !unsettledNodes.isEmpty() )
@@ -87,17 +93,22 @@ public final class Dijkstra
                 if ( !settledNodes.contains( v ) )
                 {
                     WE edge = graph.getEdge( vertex, v );
-                    Double shortDist = shortestDistances.getWeight( vertex ) + edge.getWeight();
-
-                    if ( shortDist.compareTo( shortestDistances.getWeight( v ) ) < 0 )
+                    if ( shortestDistances.alreadyVisited( vertex ) )
                     {
-                        // assign new shortest distance and mark unsettled
-                        shortestDistances.setWeight( v, shortDist );
-                        unsettledNodes.add( v );
+                        W shortDist = orderedMonoid.append( shortestDistances.getWeight( vertex ), edge.getWeight() );
 
-                        // assign predecessor in shortest path
-                        predecessors.addPredecessor( v, vertex );
+                        if ( !shortestDistances.alreadyVisited( v ) 
+                                || orderedMonoid.compare( shortDist, shortestDistances.getWeight( v ) ) < 0 )
+                        {
+                            // assign new shortest distance and mark unsettled
+                            shortestDistances.setWeight( v, shortDist );
+                            unsettledNodes.add( v );
+
+                            // assign predecessor in shortest path
+                            predecessors.addPredecessor( v, vertex );
+                        }
                     }
+
                 }
             }
         }
@@ -105,4 +116,24 @@ public final class Dijkstra
         throw new PathNotFoundException( "Path from '%s' to '%s' doesn't exist in Graph '%s'", source, target, graph );
     }
 
+    /**
+     * Applies the classical Dijkstra's algorithm to an edge weighted graph with weights of type Double
+     * to find the shortest path from the source to the target, if exists.
+     *
+     * @param <V> the Graph vertices type
+     * @param <WE> the Graph weighted edges type
+     * @param <G> the Graph type
+     * @param graph the Graph whose shortest path from {@code source} to {@code target} has to be found
+     * @param source the shortest path source Vertex
+     * @param target the shortest path target Vertex
+     * @return a path which describes the shortest path, if any,
+     *         otherwise a {@link PathNotFoundException} will be thrown
+     */
+    public static <V extends Vertex, WE extends WeightedEdge<Double>, G extends DirectedGraph<V, WE>> WeightedPath<V, WE, Double> findShortestPath( G graph,
+                                                                                                                                                    V source,
+                                                                                                                                                    V target )
+    {
+        return findShortestPath( graph, source, target, new DoubleWeight() );
+    }
+
 }

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/FloydWarshall.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/FloydWarshall.java?rev=1228934&r1=1228933&r2=1228934&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/FloydWarshall.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/FloydWarshall.java Sun Jan  8 19:42:51 2012
@@ -28,6 +28,8 @@ import org.apache.commons.graph.Vertex;
 import org.apache.commons.graph.VertexPair;
 import org.apache.commons.graph.WeightedEdge;
 import org.apache.commons.graph.WeightedPath;
+import org.apache.commons.graph.weight.OrderedMonoid;
+import org.apache.commons.graph.weight.primitive.DoubleWeight;
 
 /**
  * Contains the Floyd-Warshall's shortest paths algorithm implementation.
@@ -45,25 +47,28 @@ public final class FloydWarshall
 
     /**
      * Applies the classical Floyd-Warshall's algorithm to find all vertex shortest path
-     * 
+     *
      * @param <V> the Graph vertices type.
      * @param <WE> the Graph weighted edges type
+     * @param <W> the weight type
+     * @param graph the input graph
+     * @param orderedMonoid the {@link OrderedMonoid} needed to handle operations on weights
      * @return a data structure which contains all vertex pairs shortest path.
      */
-    public static <V extends Vertex, WE extends WeightedEdge<Double>> AllVertexPairsShortestPath<V, WE> findAllVertexPairsShortestPath( Graph<V, WE> graph )
+    public static <V extends Vertex, W, WE extends WeightedEdge<W>> AllVertexPairsShortestPath<V, WE, W> findAllVertexPairsShortestPath( Graph<V, WE> graph, OrderedMonoid<W> orderedMonoid )
     {
-        AllVertexPairsShortestPath<V, WE> shortesPaths = new AllVertexPairsShortestPath<V, WE>();
+        AllVertexPairsShortestPath<V, WE, W> shortestPaths = new AllVertexPairsShortestPath<V, WE, W>( orderedMonoid );
         Map<VertexPair<V>, V> next = new HashMap<VertexPair<V>, V>();
 
         // init
         for ( WE we : graph.getEdges() )
         {
             VertexPair<V> vertexPair = graph.getVertices( we );
-            shortesPaths.addShortestDistance( vertexPair.getHead(), vertexPair.getTail(), we.getWeight() );
+            shortestPaths.addShortestDistance( vertexPair.getHead(), vertexPair.getTail(), we.getWeight() );
 
             if ( graph instanceof UndirectedGraph )
             {
-                shortesPaths.addShortestDistance( vertexPair.getTail(), vertexPair.getHead(), we.getWeight() );
+                shortestPaths.addShortestDistance( vertexPair.getTail(), vertexPair.getHead(), we.getWeight() );
             }
         }
 
@@ -74,15 +79,19 @@ public final class FloydWarshall
             {
                 for ( V j : graph.getVertices() )
                 {
-                    Double newDistance =
-                        shortesPaths.getShortestDistance( i, k ) + shortesPaths.getShortestDistance( k, j );
-                    if ( newDistance.compareTo( shortesPaths.getShortestDistance( i, j ) ) < 0 )
+                    if ( shortestPaths.hasShortestDistance( i, k ) && shortestPaths.hasShortestDistance( k, j ) )
                     {
-                        shortesPaths.addShortestDistance( i, j, newDistance );
+                        W newDistance = orderedMonoid.append( shortestPaths.getShortestDistance( i, k ), shortestPaths.getShortestDistance( k, j ) );
+                        if ( !shortestPaths.hasShortestDistance( i, j )
+                                || orderedMonoid.compare( newDistance, shortestPaths.getShortestDistance( i, j ) ) < 0 )
+                        {
+                            shortestPaths.addShortestDistance( i, j, newDistance );
 
-                        // store the intermediate vertex
-                        next.put( new VertexPair<V>( i, j ), k );
+                            // store the intermediate vertex
+                            next.put( new VertexPair<V>( i, j ), k );
+                        }
                     }
+
                 }
             }
         }
@@ -94,25 +103,39 @@ public final class FloydWarshall
             {
                 if ( !source.equals( target ) )
                 {
-                    PredecessorsList<V, WE> predecessorsList = new PredecessorsList<V, WE>( graph );
+                    PredecessorsList<V, WE, W> predecessorsList = new PredecessorsList<V, WE, W>( graph, orderedMonoid );
 
                     pathReconstruction( predecessorsList, source, target, next, graph );
                     if ( !predecessorsList.isEmpty() )
                     {
-                        WeightedPath<V, WE, Double> weightedPath = predecessorsList.buildPath( source, target );
+                        WeightedPath<V, WE, W> weightedPath = predecessorsList.buildPath( source, target );
                         if ( weightedPath.getOrder() > 0 )
                         {
-                            shortesPaths.addShortestPath( source, target, weightedPath );
+                            shortestPaths.addShortestPath( source, target, weightedPath );
                         }
                     }
                 }
             }
         }
 
-        return shortesPaths;
+        return shortestPaths;
+    }
+
+    /**
+     * Applies the classical Floyd-Warshall's algorithm to an edge weighted graph with weights of type Double
+     * to find all vertex shortest path.
+     *
+     * @param <V> the Graph vertices type.
+     * @param <WE> the Graph weighted edges type
+     * @param graph the input graph
+     * @return a data structure which contains all vertex pairs shortest path.
+     */
+    public static <V extends Vertex, WE extends WeightedEdge<Double>> AllVertexPairsShortestPath<V, WE, Double> findAllVertexPairsShortestPath( Graph<V, WE> graph )
+    {
+        return findAllVertexPairsShortestPath( graph, new DoubleWeight() );
     }
 
-    private static <V extends Vertex, WE extends WeightedEdge<Double>> void pathReconstruction( PredecessorsList<V, WE> path,
+    private static <V extends Vertex, WE extends WeightedEdge<W>, W> void pathReconstruction( PredecessorsList<V, WE, W> path,
                                                                                                 V source, V target,
                                                                                                 Map<VertexPair<V>, V> next,
                                                                                                 Graph<V, WE> graph )

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PredecessorsList.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PredecessorsList.java?rev=1228934&r1=1228933&r2=1228934&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PredecessorsList.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PredecessorsList.java Sun Jan  8 19:42:51 2012
@@ -22,30 +22,34 @@ package org.apache.commons.graph.shortes
 import java.util.HashMap;
 import java.util.Map;
 
-import org.apache.commons.graph.Edge;
 import org.apache.commons.graph.Graph;
 import org.apache.commons.graph.Vertex;
 import org.apache.commons.graph.WeightedEdge;
 import org.apache.commons.graph.WeightedPath;
 import org.apache.commons.graph.model.InMemoryWeightedPath;
+import org.apache.commons.graph.weight.Monoid;
 
 /**
  * The predecessor list is a list of {@link Vertex} of a {@link org.apache.commons.graph.Graph}.
  * Each {@link Vertex}' entry contains the index of its predecessor in a path through the graph.
  *
  * @param <V> the Graph vertices type
- * @param <E> the Graph edges type
+ * @param <WE> the Graph weighted edges type
+ * @param <W> the weight type
  */
-final class PredecessorsList<V extends Vertex, WE extends WeightedEdge<Double>>
+final class PredecessorsList<V extends Vertex, WE extends WeightedEdge<W>, W>
 {
 
     private final Graph<V, WE> graph;
+    
+    private final Monoid<W> monoid;
 
     private final Map<V, V> predecessors = new HashMap<V, V>();
 
-    public PredecessorsList(Graph<V, WE> graph )
+    public PredecessorsList( Graph<V, WE> graph, Monoid<W> monoid )
     {
         this.graph = graph;
+        this.monoid = monoid;
     }
 
     /**
@@ -67,9 +71,9 @@ final class PredecessorsList<V extends V
      * @param cost the path cost
      * @return the weighted path related to source to target
      */
-    public WeightedPath<V, WE, Double> buildPath( V source, V target )
+    public WeightedPath<V, WE, W> buildPath( V source, V target )
     {
-        InMemoryWeightedPath<V, WE> path = new InMemoryWeightedPath<V, WE>( source, target );
+        InMemoryWeightedPath<V, WE, W> path = new InMemoryWeightedPath<V, WE, W>( source, target, monoid );
 
         V vertex = target;
         while ( !source.equals( vertex ) )

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/ShortestDistances.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/ShortestDistances.java?rev=1228934&r1=1228933&r2=1228934&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/ShortestDistances.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/ShortestDistances.java Sun Jan  8 19:42:51 2012
@@ -24,36 +24,52 @@ import java.util.HashMap;
 import java.util.Map;
 
 import org.apache.commons.graph.Vertex;
+import org.apache.commons.graph.weight.OrderedMonoid;
 
 /**
  * Stores and compares Graph Vertices weights.
  *
  * @param <V> the Graph vertices type
+ * @param <W> the weight type
  */
-final class ShortestDistances<V extends Vertex>
+final class ShortestDistances<V extends Vertex, W>
     implements Comparator<V>
 {
 
     private static final long serialVersionUID = 568538689459177637L;
 
-    private final Map<V, Double> distances = new HashMap<V, Double>();
+    private final Map<V, W> distances = new HashMap<V, W>();
+
+    private final OrderedMonoid<W> orderedMonoid;
+
+    public ShortestDistances( OrderedMonoid<W> orderedMonoid )
+    {
+        this.orderedMonoid = orderedMonoid;
+    }
 
     /**
-     * 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 wasn't previously visited.
+     *
+     * <b>NOTE</b>: the method {@link alreadyVisited} should be used first to check if
+     * the input vertex was already visited and a distance value is available for it.
      *
-     * @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.
+     * @param vertex the vertex whose distance has to be retrieved
+     * @return the distance related to input vertex, or null if it wasn't previously visited.
      */
-    public Double getWeight( V vertex )
+    public W getWeight( V vertex )
     {
-        Double distance = distances.get( vertex );
-
-        if ( distance == null )
-        {
-            return Double.POSITIVE_INFINITY;
-        }
+        return distances.get( vertex );
+    }
 
-        return distance;
+    /**
+     * Checks if the input {@code Vertex} was already visited.
+     *
+     * @param vertex the input {@code Vertex}
+     * @return true if the input {@code Vertex} was already visited, false otherwise.
+     */
+    public boolean alreadyVisited( V vertex )
+    {
+        return distances.containsKey( vertex );
     }
 
     /**
@@ -62,7 +78,7 @@ final class ShortestDistances<V extends 
      * @param vertex the vertex for which the distance has to be updated
      * @param distance the new input vertex distance
      */
-    public void setWeight( V vertex, Double distance )
+    public void setWeight( V vertex, W distance )
     {
         distances.put( vertex, distance );
     }
@@ -72,7 +88,19 @@ final class ShortestDistances<V extends 
      */
     public int compare( V left, V right )
     {
-        return getWeight( left ).compareTo( getWeight( right ) );
+        if ( !alreadyVisited( left ) && !alreadyVisited( right ) )
+        {
+            return 0;
+        }
+        else if ( !alreadyVisited( left ) )
+        {
+            return 1;
+        }
+        else if ( !alreadyVisited( right ) )
+        {
+            return -1;
+        }
+        return orderedMonoid.compare( getWeight( left ), getWeight( right ) );
     }
 
 }

Added: 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=1228934&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Monoid.java (added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Monoid.java Sun Jan  8 19:42:51 2012
@@ -0,0 +1,31 @@
+package org.apache.commons.graph.weight;
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+/**
+ * A {@link Monoid} is a {@link Semigroup} with an identity value.
+ *
+ * @param <M> the type of the elements in the {@link Monoid}
+ */
+public interface Monoid<M>
+    extends Zero<M>, Semigroup<M>
+{
+
+}

Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Monoid.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Monoid.java
------------------------------------------------------------------------------
    svn:keywords = Date Author Id Revision HeadURL

Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Monoid.java
------------------------------------------------------------------------------
    svn:mime-type = text/plain

Added: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/OrderedMonoid.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/OrderedMonoid.java?rev=1228934&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/OrderedMonoid.java (added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/OrderedMonoid.java Sun Jan  8 19:42:51 2012
@@ -0,0 +1,33 @@
+package org.apache.commons.graph.weight;
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+import java.util.Comparator;
+
+/**
+ * An {@link OrderedMonoid} is a {@link Monoid} with a total order defined on it.
+ *
+ * @param <M> the type of the elements in the {@link OrderedMonoid}
+ */
+public interface OrderedMonoid<M>
+    extends Monoid<M>, Comparator<M>
+{
+
+}

Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/OrderedMonoid.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/OrderedMonoid.java
------------------------------------------------------------------------------
    svn:keywords = Date Author Id Revision HeadURL

Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/OrderedMonoid.java
------------------------------------------------------------------------------
    svn:mime-type = text/plain

Added: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Semigroup.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Semigroup.java?rev=1228934&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Semigroup.java (added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Semigroup.java Sun Jan  8 19:42:51 2012
@@ -0,0 +1,41 @@
+package org.apache.commons.graph.weight;
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+/**
+ * A {@link Semigroup} defines an associative binary operation
+ * on a set of elements of the same type.
+ *
+ * @param <S> the type of the elements in the {@link Semigroup}
+ */
+public interface Semigroup<S>
+{
+
+    /**
+     * Returns the result of the associative binary operation defined by this
+     * {@link Semigroup} between two elements of appropriate type.
+     *
+     * @param s1 the first element
+     * @param s2 the second element
+     * @return the result of the associative binary operation
+     */
+    S append( S s1, S s2 );
+
+}

Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Semigroup.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Semigroup.java
------------------------------------------------------------------------------
    svn:keywords = Date Author Id Revision HeadURL

Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Semigroup.java
------------------------------------------------------------------------------
    svn:mime-type = text/plain

Added: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Zero.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Zero.java?rev=1228934&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Zero.java (added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Zero.java Sun Jan  8 19:42:51 2012
@@ -0,0 +1,38 @@
+package org.apache.commons.graph.weight;
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+/**
+ * An object implementing {@link Zero} provides access to an identity value,
+ * also called zero, for the specified type.
+ *
+ * @param <Z> the type of the identity value
+ */
+public interface Zero<Z>
+{
+
+    /**
+     * Returns the identity value.
+     *
+     * @return the identity value
+     */
+    Z zero();
+
+}

Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Zero.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Zero.java
------------------------------------------------------------------------------
    svn:keywords = Date Author Id Revision HeadURL

Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Zero.java
------------------------------------------------------------------------------
    svn:mime-type = text/plain

Added: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/package-info.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/package-info.java?rev=1228934&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/package-info.java (added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/package-info.java Sun Jan  8 19:42:51 2012
@@ -0,0 +1,23 @@
+/**
+ * Interfaces that define properties and operations on weights.
+ */
+package org.apache.commons.graph.weight;
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
\ No newline at end of file

Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/package-info.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/package-info.java
------------------------------------------------------------------------------
    svn:keywords = Date Author Id Revision HeadURL

Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/package-info.java
------------------------------------------------------------------------------
    svn:mime-type = text/plain

Added: 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=1228934&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/DoubleWeight.java (added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/DoubleWeight.java Sun Jan  8 19:42:51 2012
@@ -0,0 +1,60 @@
+package org.apache.commons.graph.weight.primitive;
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+import org.apache.commons.graph.weight.OrderedMonoid;
+
+/**
+ * A {@link DoubleWeight} provides operations and properties 
+ * for weights of type {@link Double}.
+ */
+public class DoubleWeight
+    implements OrderedMonoid<Double>
+{
+
+    /**
+     * {@inheritDoc}
+     */
+    public Double zero()
+    {
+        return 0.0;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public Double append( Double s1, Double s2 )
+    {
+        if ( s1 == null || s2 == null )
+        {
+            return null;
+        }
+        return s1 + s2;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public int compare( Double s1, Double s2 )
+    {
+        return s1.compareTo( s2 );
+    }
+
+}

Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/DoubleWeight.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/DoubleWeight.java
------------------------------------------------------------------------------
    svn:keywords = Date Author Id Revision HeadURL

Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/DoubleWeight.java
------------------------------------------------------------------------------
    svn:mime-type = text/plain

Added: 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=1228934&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/IntegerWeight.java (added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/IntegerWeight.java Sun Jan  8 19:42:51 2012
@@ -0,0 +1,60 @@
+package org.apache.commons.graph.weight.primitive;
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+import org.apache.commons.graph.weight.OrderedMonoid;
+
+/**
+ * A {@link IntegerWeight} provides operations and properties 
+ * for weights of type {@link Integer}.
+ */
+public class IntegerWeight
+    implements OrderedMonoid<Integer>
+{
+
+    /**
+     * {@inheritDoc}
+     */
+    public Integer zero()
+    {
+        return 0;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public Integer append( Integer s1, Integer s2 )
+    {
+        if ( s1 == null || s2 == null )
+        {
+            return null;
+        }
+        return s1 + s2;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public int compare( Integer o1, Integer o2 )
+    {
+        return o1.compareTo( o2 );
+    }
+
+}

Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/IntegerWeight.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/IntegerWeight.java
------------------------------------------------------------------------------
    svn:keywords = Date Author Id Revision HeadURL

Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/IntegerWeight.java
------------------------------------------------------------------------------
    svn:mime-type = text/plain

Added: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/package-info.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/package-info.java?rev=1228934&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/package-info.java (added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/package-info.java Sun Jan  8 19:42:51 2012
@@ -0,0 +1,23 @@
+/**
+ * Primitive weight implementations.
+ */
+package org.apache.commons.graph.weight.primitive;
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
\ No newline at end of file

Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/package-info.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/package-info.java
------------------------------------------------------------------------------
    svn:keywords = Date Author Id Revision HeadURL

Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/package-info.java
------------------------------------------------------------------------------
    svn:mime-type = text/plain

Modified: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/AStarTestCase.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/AStarTestCase.java?rev=1228934&r1=1228933&r2=1228934&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/AStarTestCase.java (original)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/AStarTestCase.java Sun Jan  8 19:42:51 2012
@@ -30,6 +30,7 @@ import org.apache.commons.graph.model.Ba
 import org.apache.commons.graph.model.BaseLabeledWeightedEdge;
 import org.apache.commons.graph.model.InMemoryWeightedPath;
 import org.apache.commons.graph.model.UndirectedMutableWeightedGraph;
+import org.apache.commons.graph.weight.primitive.DoubleWeight;
 import org.junit.Test;
 
 public final class AStarTestCase
@@ -95,8 +96,8 @@ public final class AStarTestCase
 
         // expected path
 
-        InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge> expected =
-            new InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge>( start, goal );
+        InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge, Double> expected =
+            new InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge, Double>( start, goal, new DoubleWeight() );
 
         expected.addConnectionInTail( start, new BaseLabeledWeightedEdge( "start <-> a", 1.5D ), a );
         expected.addConnectionInTail( a, new BaseLabeledWeightedEdge( "a <-> b", 2D ), b );

Modified: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/BellmannFordTestCase.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/BellmannFordTestCase.java?rev=1228934&r1=1228933&r2=1228934&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/BellmannFordTestCase.java (original)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/BellmannFordTestCase.java Sun Jan  8 19:42:51 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.DirectedMutableWeightedGraph;
 import org.apache.commons.graph.model.InMemoryWeightedPath;
+import org.apache.commons.graph.weight.primitive.DoubleWeight;
 import org.junit.Test;
 
 public final class BellmannFordTestCase
@@ -71,13 +72,13 @@ public final class BellmannFordTestCase
         graph.addEdge( five, new BaseLabeledWeightedEdge( "5 -> 1", 2D ), one );
 
         // the expected weighted path
-        InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge> expected =
-            new InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge>( one, three );
+        InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge, Double> expected =
+            new InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge, Double>( one, three, new DoubleWeight() );
         expected.addConnectionInTail( one, new BaseLabeledWeightedEdge( "1 -> 4", 7D ), four );
         expected.addConnectionInTail( four, new BaseLabeledWeightedEdge( "4 -> 3", -3D ), three );
 
         // the actual weighted path
-        AllVertexPairsShortestPath<BaseLabeledVertex, BaseLabeledWeightedEdge> allVertexPairsShortestPath =
+        AllVertexPairsShortestPath<BaseLabeledVertex, BaseLabeledWeightedEdge, Double> allVertexPairsShortestPath =
             findShortestPath( graph, one );
 
         WeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge, Double> actual =

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=1228934&r1=1228933&r2=1228934&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 Sun Jan  8 19:42:51 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.DirectedMutableWeightedGraph;
 import org.apache.commons.graph.model.InMemoryWeightedPath;
+import org.apache.commons.graph.weight.primitive.DoubleWeight;
 import org.junit.Test;
 
 public final class DijkstraTestCase
@@ -73,8 +74,8 @@ public final class DijkstraTestCase
 
         // expected path
 
-        InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge> expected =
-            new InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge>( one, five );
+        InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge, Double> expected =
+            new InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge, Double>( one, five, new DoubleWeight() );
 
         expected.addConnectionInTail( one, new BaseLabeledWeightedEdge( "1 -> 3", 9D ), three );
         expected.addConnectionInTail( three, new BaseLabeledWeightedEdge( "3 -> 6", 2D ), six );

Modified: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/FloydWarshallTestCase.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/FloydWarshallTestCase.java?rev=1228934&r1=1228933&r2=1228934&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/FloydWarshallTestCase.java (original)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/FloydWarshallTestCase.java Sun Jan  8 19:42:51 2012
@@ -20,6 +20,7 @@ package org.apache.commons.graph.shortes
  */
 
 import static junit.framework.Assert.assertEquals;
+import static junit.framework.Assert.assertFalse;
 import static junit.framework.Assert.fail;
 import static org.apache.commons.graph.shortestpath.FloydWarshall.findAllVertexPairsShortestPath;
 
@@ -32,6 +33,7 @@ import org.apache.commons.graph.model.Ba
 import org.apache.commons.graph.model.DirectedMutableWeightedGraph;
 import org.apache.commons.graph.model.InMemoryWeightedPath;
 import org.apache.commons.graph.model.UndirectedMutableWeightedGraph;
+import org.apache.commons.graph.weight.primitive.DoubleWeight;
 import org.junit.Test;
 
 /**
@@ -86,7 +88,7 @@ public class FloydWarshallTestCase
         mutable.addEdge( four, new BaseLabeledWeightedEdge( "4 -> 5", 6D ), five );
         mutable.addEdge( six, new BaseLabeledWeightedEdge( "6 -> 5", 9D ), five );
 
-        AllVertexPairsShortestPath<BaseLabeledVertex, BaseLabeledWeightedEdge> p =
+        AllVertexPairsShortestPath<BaseLabeledVertex, BaseLabeledWeightedEdge, Double> p =
             findAllVertexPairsShortestPath( weighted );
 
         if ( weighted instanceof UndirectedGraph )
@@ -107,8 +109,8 @@ public class FloydWarshallTestCase
             WeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge, Double> wp = p.findShortestPath( one, six );
 
             // Expected
-            InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge> expected =
-                new InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge>( one, six );
+            InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge, Double> expected =
+                new InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge, Double>( one, six, new DoubleWeight() );
             expected.addConnectionInTail( one, new BaseLabeledWeightedEdge( "1 -> 3", 9D ), three );
             expected.addConnectionInTail( three, new BaseLabeledWeightedEdge( "3 -> 6", 2D ), six );
 
@@ -122,7 +124,7 @@ public class FloydWarshallTestCase
             assertEquals( 6D, p.getShortestDistance( four, five ) );
 
             assertEquals( 20D, p.getShortestDistance( one, five ) );
-            assertEquals( Double.POSITIVE_INFINITY, p.getShortestDistance( five, one ) );
+            assertFalse( p.hasShortestDistance( five, one ) );
 
             WeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge, Double> wp;
             // Verify shortest paths
@@ -135,8 +137,8 @@ public class FloydWarshallTestCase
                 // wallow it
             }
 
-            InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge> expected =
-                new InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge>( one, six );
+            InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge, Double> expected =
+                new InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge, Double>( one, six, new DoubleWeight() );
             expected.addConnectionInTail( one, new BaseLabeledWeightedEdge( "1 -> 3", 9D ), three );
             expected.addConnectionInTail( three, new BaseLabeledWeightedEdge( "3 -> 6", 2D ), six );
 

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=1228934&r1=1228933&r2=1228934&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 Sun Jan  8 19:42:51 2012
@@ -95,7 +95,7 @@ public final class KruskalTestCase
         // Actual
 
         SpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge> actual = minimumSpanningTree( input );
-
+        
         // assert!
 
         assertEquals( expected, actual );



Mime
View raw message