commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From c.@apache.org
Subject svn commit: r1298136 - in /commons/sandbox/graph/trunk/src: main/java/org/apache/commons/graph/flow/ main/java/org/apache/commons/graph/model/ main/java/org/apache/commons/graph/shortestpath/ main/java/org/apache/commons/graph/spanning/ main/java/org/a...
Date Wed, 07 Mar 2012 21:34:22 GMT
Author: cs
Date: Wed Mar  7 21:34:21 2012
New Revision: 1298136

URL: http://svn.apache.org/viewvc?rev=1298136&view=rev
Log:
[SANDBOX-404] simplify weight model: merge Zero and Semigroup into Monoid and get rid of OrderedMonoid (replaced by the combination Monoid & Comparator)

Removed:
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/OrderedMonoid.java
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Semigroup.java
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Zero.java
Modified:
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/DefaultMaxFlowAlgorithmSelector.java
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/FlowNetworkHandler.java
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/MaxFlowAlgorithmSelector.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/model/MutableSpanningTree.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/DefaultHeuristicBuilder.java
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultPathSourceSelector.java
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultShortestPathAlgorithmSelector.java
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultTargetSourceSelector.java
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/HeuristicBuilder.java
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PathSourceSelector.java
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/ShortestDistances.java
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/ShortestPathAlgorithmSelector.java
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/TargetSourceSelector.java
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeAlgorithmSelector.java
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeSourceSelector.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/spanning/SpanningTreeAlgorithmSelector.java
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/SpanningTreeSourceSelector.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/BigDecimalWeightBaseOperations.java
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/BigIntegerWeightBaseOperations.java
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/DoubleWeightBaseOperations.java
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/FloatWeightBaseOperations.java
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/IntegerWeightBaseOperations.java
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/LongWeightBaseOperations.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/FloydWarshallTestCase.java

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/DefaultMaxFlowAlgorithmSelector.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/DefaultMaxFlowAlgorithmSelector.java?rev=1298136&r1=1298135&r2=1298136&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/DefaultMaxFlowAlgorithmSelector.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/DefaultMaxFlowAlgorithmSelector.java Wed Mar  7 21:34:21 2012
@@ -23,13 +23,15 @@ import static org.apache.commons.graph.C
 import static org.apache.commons.graph.CommonsGraph.visit;
 import static org.apache.commons.graph.utils.Assertions.checkNotNull;
 
+import java.util.Comparator;
+
 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.builder.AbstractGraphConnection;
 import org.apache.commons.graph.model.BaseLabeledWeightedEdge;
-import org.apache.commons.graph.weight.OrderedMonoid;
+import org.apache.commons.graph.weight.Monoid;
 
 /**
  * {@link MaxFlowAlgorithmSelector} implementation.
@@ -59,7 +61,7 @@ final class DefaultMaxFlowAlgorithmSelec
     /**
      * {@inheritDoc}
      */
-    public <WO extends OrderedMonoid<W>> W applyingFordFulkerson( WO weightOperations )
+    public <WO extends Monoid<W> & Comparator<W>> W applyingFordFulkerson( WO weightOperations )
     {
         final WO checkedWeightOperations = checkNotNull( weightOperations, "Weight operations can not be null to find the max flow in the graph" );
 
@@ -67,7 +69,7 @@ final class DefaultMaxFlowAlgorithmSelec
         final DirectedGraph<V, WeightedEdge<W>> flowNetwork = newFlowNetwok( graph, checkedWeightOperations );
 
         // create flow network handler
-        final FlowNetworkHandler<V, W> flowNetworkHandler = new FlowNetworkHandler<V, W>( flowNetwork, source, target, checkedWeightOperations );
+        final FlowNetworkHandler<V, W, WO> flowNetworkHandler = new FlowNetworkHandler<V, W, WO>( flowNetwork, source, target, checkedWeightOperations );
 
         // perform depth first search
         visit( flowNetwork ).from( source ).applyingDepthFirstSearch( flowNetworkHandler );
@@ -86,7 +88,7 @@ final class DefaultMaxFlowAlgorithmSelec
     /**
      * {@inheritDoc}
      */
-    public <WO extends OrderedMonoid<W>> W applyingEdmondsKarp( WO weightOperations )
+    public <WO extends Monoid<W> & Comparator<W>> W applyingEdmondsKarp( WO weightOperations )
     {
         final WO checkedWeightOperations = checkNotNull( weightOperations, "Weight operations can not be null to find the max flow in the graph" );
 
@@ -94,7 +96,7 @@ final class DefaultMaxFlowAlgorithmSelec
         final DirectedGraph<V, WeightedEdge<W>> flowNetwork = newFlowNetwok( graph, checkedWeightOperations );
 
         // create flow network handler
-        final FlowNetworkHandler<V, W> flowNetworkHandler = new FlowNetworkHandler<V, W>( flowNetwork, source, target, checkedWeightOperations );
+        final FlowNetworkHandler<V, W, WO> flowNetworkHandler = new FlowNetworkHandler<V, W, WO>( flowNetwork, source, target, checkedWeightOperations );
 
         // perform breadth first search
         visit( flowNetwork ).from( source ).applyingBreadthFirstSearch( flowNetworkHandler );
@@ -110,7 +112,7 @@ final class DefaultMaxFlowAlgorithmSelec
         return flowNetworkHandler.onCompleted();
     }
 
-    private <WO extends OrderedMonoid<W>> DirectedGraph<V, WeightedEdge<W>> newFlowNetwok( final G graph, final WO weightOperations )
+    private <WO extends Monoid<W> & Comparator<W>> DirectedGraph<V, WeightedEdge<W>> newFlowNetwok( final G graph, final WO weightOperations )
     {
         return newDirectedMutableWeightedGraph( new AbstractGraphConnection<V, WeightedEdge<W>>()
         {
@@ -134,7 +136,7 @@ final class DefaultMaxFlowAlgorithmSelec
                     if ( graph.getEdge( tail, head ) == null )
                     {
                         // complete the flow network with a zero-capacity inverse edge
-                        addEdge( new BaseLabeledWeightedEdge<W>( "Inverse edge for " + edge, weightOperations.zero() ) )
+                        addEdge( new BaseLabeledWeightedEdge<W>( "Inverse edge for " + edge, weightOperations.identity() ) )
                             .from( tail ).to( head );
                     }
                 }

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/FlowNetworkHandler.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/FlowNetworkHandler.java?rev=1298136&r1=1298135&r2=1298136&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/FlowNetworkHandler.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/FlowNetworkHandler.java Wed Mar  7 21:34:21 2012
@@ -19,6 +19,7 @@ package org.apache.commons.graph.flow;
  * under the License.
  */
 
+import java.util.Comparator;
 import java.util.HashMap;
 import java.util.Map;
 
@@ -29,7 +30,7 @@ import org.apache.commons.graph.Weighted
 import org.apache.commons.graph.WeightedPath;
 import org.apache.commons.graph.shortestpath.PredecessorsList;
 import org.apache.commons.graph.visit.BaseGraphVisitHandler;
-import org.apache.commons.graph.weight.OrderedMonoid;
+import org.apache.commons.graph.weight.Monoid;
 
 /**
  * Provides standard operations for max-flow algorithms,
@@ -38,7 +39,7 @@ import org.apache.commons.graph.weight.O
  * @param <V> the vertex type
  * @param <W> the weight type
  */
-class FlowNetworkHandler<V extends Vertex, W>
+class FlowNetworkHandler<V extends Vertex, W, WO extends Monoid<W> & Comparator<W>>
     extends BaseGraphVisitHandler<V, WeightedEdge<W>, DirectedGraph<V, WeightedEdge<W>>, W>
 {
 
@@ -48,7 +49,7 @@ class FlowNetworkHandler<V extends Verte
 
     private final V target;
 
-    private final OrderedMonoid<W> weightOperations;
+    private final WO weightOperations;
 
     private W maxFlow;
 
@@ -59,14 +60,14 @@ class FlowNetworkHandler<V extends Verte
 
     private boolean foundAugmentingPath;
 
-    FlowNetworkHandler( DirectedGraph<V, WeightedEdge<W>> flowNetwork, V source, V target, OrderedMonoid<W> weightOperations )
+    FlowNetworkHandler( DirectedGraph<V, WeightedEdge<W>> flowNetwork, V source, V target, WO weightOperations )
     {
         this.flowNetwork = flowNetwork;
         this.source = source;
         this.target = target;
         this.weightOperations = weightOperations;
 
-        maxFlow = weightOperations.zero();
+        maxFlow = weightOperations.identity();
 
         for ( WeightedEdge<W> edge : flowNetwork.getEdges() )
         {
@@ -142,7 +143,7 @@ class FlowNetworkHandler<V extends Verte
     {
         W residualEdgeCapacity = residualEdgeCapacities.get( edge );
         // avoid expanding the edge when it has no residual capacity
-        if ( weightOperations.compare( residualEdgeCapacity, weightOperations.zero() ) <= 0 )
+        if ( weightOperations.compare( residualEdgeCapacity, weightOperations.identity() ) <= 0 )
         {
             return false;
         }

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/MaxFlowAlgorithmSelector.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/MaxFlowAlgorithmSelector.java?rev=1298136&r1=1298135&r2=1298136&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/MaxFlowAlgorithmSelector.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/MaxFlowAlgorithmSelector.java Wed Mar  7 21:34:21 2012
@@ -19,10 +19,12 @@ package org.apache.commons.graph.flow;
  * under the License.
  */
 
+import java.util.Comparator;
+
 import org.apache.commons.graph.DirectedGraph;
 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.Monoid;
 
 public interface MaxFlowAlgorithmSelector<V extends Vertex, WE extends WeightedEdge<W>, W, G extends DirectedGraph<V, WE>>
 {
@@ -34,7 +36,7 @@ public interface MaxFlowAlgorithmSelecto
      * @param weightOperations the class responsible for operations on weights
      * @return
      */
-    <WO extends OrderedMonoid<W>> W applyingFordFulkerson( WO weightOperations );
+    <WO extends Monoid<W> & Comparator<W>> W applyingFordFulkerson( WO weightOperations );
 
     /**
      * Calculates the maximum flow using the Edmonds-Karp algorithm.
@@ -43,6 +45,6 @@ public interface MaxFlowAlgorithmSelecto
      * @param weightOperations the class responsible for operations on weights
      * @return
      */
-    <WO extends OrderedMonoid<W>> W applyingEdmondsKarp( WO weightOperations );
+    <WO extends Monoid<W> & Comparator<W>> W applyingEdmondsKarp( WO weightOperations );
 
 }

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=1298136&r1=1298135&r2=1298136&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 Wed Mar  7 21:34:21 2012
@@ -52,7 +52,7 @@ public final class InMemoryWeightedPath<
     {
         super( start, target );
         this.weightOperations = weightOperations;
-        this.weight = weightOperations.zero();
+        this.weight = weightOperations.identity();
     }
 
     /**

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=1298136&r1=1298135&r2=1298136&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 Mar  7 21:34:21 2012
@@ -46,7 +46,7 @@ public final class MutableSpanningTree<V
 
     public MutableSpanningTree(Monoid<W> weightOperations) {
         this.weightOperations = weightOperations;
-        this.weight = weightOperations.zero();
+        this.weight = weightOperations.identity();
     }
 
     /**

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=1298136&r1=1298135&r2=1298136&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 Wed Mar  7 21:34:21 2012
@@ -21,6 +21,7 @@ package org.apache.commons.graph.shortes
 
 import static org.apache.commons.graph.utils.Assertions.checkNotNull;
 
+import java.util.Comparator;
 import java.util.HashMap;
 import java.util.Map;
 
@@ -28,7 +29,7 @@ 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.Monoid;
 
 /**
  * Represents all shortest paths between all vertex pairs calculated by {@link FloydWarshall} algorithm.
@@ -37,19 +38,19 @@ import org.apache.commons.graph.weight.O
  * @param <WE> the Graph weighted edges type
  * @param <W> the weight type
  */
-public final class AllVertexPairsShortestPath<V extends Vertex, WE extends WeightedEdge<W>, W>
+public final class AllVertexPairsShortestPath<V extends Vertex, WE extends WeightedEdge<W>, W, WO extends Monoid<W> & Comparator<W>>
 {
 
     private final Map<VertexPair<V>, WeightedPath<V, WE, W>> paths = new HashMap<VertexPair<V>, WeightedPath<V, WE, W>>();
 
     private final Map<VertexPair<V>, W> shortestDistances = new HashMap<VertexPair<V>, W>();
 
-    private final OrderedMonoid<W> weightOperations;
+    private final WO weightOperations;
 
     /**
      * Constructor visible only inside the package
      */
-    AllVertexPairsShortestPath( OrderedMonoid<W> weightOperations )
+    AllVertexPairsShortestPath( WO weightOperations )
     {
         this.weightOperations = weightOperations;
     }
@@ -118,7 +119,7 @@ public final class AllVertexPairsShortes
 
         if ( source.equals( target ) )
         {
-            return weightOperations.zero();
+            return weightOperations.identity();
         }
 
         return shortestDistances.get( new VertexPair<V>( source, target ) );

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultHeuristicBuilder.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultHeuristicBuilder.java?rev=1298136&r1=1298135&r2=1298136&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultHeuristicBuilder.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultHeuristicBuilder.java Wed Mar  7 21:34:21 2012
@@ -21,6 +21,7 @@ package org.apache.commons.graph.shortes
 
 import static org.apache.commons.graph.utils.Assertions.checkNotNull;
 
+import java.util.Comparator;
 import java.util.HashSet;
 import java.util.Queue;
 import java.util.Set;
@@ -31,9 +32,9 @@ import org.apache.commons.graph.Weighted
 import org.apache.commons.graph.WeightedGraph;
 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.Monoid;
 
-final class DefaultHeuristicBuilder<V extends Vertex, WE extends WeightedEdge<W>, W, G extends WeightedGraph<V, WE, W>, WO extends OrderedMonoid<W>>
+final class DefaultHeuristicBuilder<V extends Vertex, WE extends WeightedEdge<W>, W, G extends WeightedGraph<V, WE, W>, WO extends Monoid<W> & Comparator<W>>
     implements HeuristicBuilder<V, WE, W, G, WO>
 {
 
@@ -61,11 +62,11 @@ final class DefaultHeuristicBuilder<V ex
         heuristic = checkNotNull( heuristic, "A* algorithm can not be applied using a null heuristic" );
 
         // Cost from start along best known path.
-        final ShortestDistances<V, W> gScores = new ShortestDistances<V, W>( weightOperations );
-        gScores.setWeight( start, weightOperations.zero() );
+        final ShortestDistances<V, W, WO> gScores = new ShortestDistances<V, W, WO>( weightOperations );
+        gScores.setWeight( start, weightOperations.identity() );
 
         // Estimated total cost from start to goal through y.
-        final ShortestDistances<V, W> fScores = new ShortestDistances<V, W>( weightOperations );
+        final ShortestDistances<V, W, WO> fScores = new ShortestDistances<V, W, WO>( weightOperations );
         W hScore = heuristic.applyHeuristic( start, goal );
         fScores.setWeight( start, hScore );
 

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultPathSourceSelector.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultPathSourceSelector.java?rev=1298136&r1=1298135&r2=1298136&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultPathSourceSelector.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultPathSourceSelector.java Wed Mar  7 21:34:21 2012
@@ -21,6 +21,7 @@ package org.apache.commons.graph.shortes
 
 import static org.apache.commons.graph.utils.Assertions.checkNotNull;
 
+import java.util.Comparator;
 import java.util.HashMap;
 import java.util.Map;
 
@@ -30,7 +31,7 @@ import org.apache.commons.graph.VertexPa
 import org.apache.commons.graph.WeightedEdge;
 import org.apache.commons.graph.WeightedGraph;
 import org.apache.commons.graph.WeightedPath;
-import org.apache.commons.graph.weight.OrderedMonoid;
+import org.apache.commons.graph.weight.Monoid;
 
 public final class DefaultPathSourceSelector<V extends Vertex, WE extends WeightedEdge<W>, W, G extends WeightedGraph<V, WE, W>>
     implements PathSourceSelector<V, WE, W, G>
@@ -46,11 +47,11 @@ public final class DefaultPathSourceSele
     /**
      * {@inheritDoc}
      */
-    public <WO extends OrderedMonoid<W>> AllVertexPairsShortestPath<V, WE, W> applyingFloydWarshall( WO weightOperations )
+    public <WO extends Monoid<W> & Comparator<W>> AllVertexPairsShortestPath<V, WE, W, WO> applyingFloydWarshall( WO weightOperations )
     {
         weightOperations = checkNotNull( weightOperations, "Floyd-Warshall algorithm can not be applied using null weight operations" );
 
-        AllVertexPairsShortestPath<V, WE, W> shortestPaths = new AllVertexPairsShortestPath<V, WE, W>( weightOperations );
+        AllVertexPairsShortestPath<V, WE, W, WO> shortestPaths = new AllVertexPairsShortestPath<V, WE, W, WO>( weightOperations );
         Map<VertexPair<V>, V> next = new HashMap<VertexPair<V>, V>();
 
         // init

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultShortestPathAlgorithmSelector.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultShortestPathAlgorithmSelector.java?rev=1298136&r1=1298135&r2=1298136&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultShortestPathAlgorithmSelector.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultShortestPathAlgorithmSelector.java Wed Mar  7 21:34:21 2012
@@ -21,6 +21,7 @@ package org.apache.commons.graph.shortes
 
 import static org.apache.commons.graph.utils.Assertions.checkNotNull;
 
+import java.util.Comparator;
 import java.util.HashSet;
 import java.util.Queue;
 import java.util.Set;
@@ -30,7 +31,7 @@ import org.apache.commons.graph.Weighted
 import org.apache.commons.graph.WeightedGraph;
 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.Monoid;
 
 final class DefaultShortestPathAlgorithmSelector<V extends Vertex, WE extends WeightedEdge<W>, W, G extends WeightedGraph<V, WE, W>>
     implements ShortestPathAlgorithmSelector<V, WE, W, G>
@@ -52,7 +53,7 @@ final class DefaultShortestPathAlgorithm
     /**
      * {@inheritDoc}
      */
-    public <WO extends OrderedMonoid<W>> HeuristicBuilder<V, WE, W, G, WO> applyingAStar( WO weightOperations )
+    public <WO extends Monoid<W> & Comparator<W>> HeuristicBuilder<V, WE, W, G, WO> applyingAStar( WO weightOperations )
     {
         weightOperations = checkNotNull( weightOperations, "A* algorithm can not be applied using null weight operations" );
         return new DefaultHeuristicBuilder<V, WE, W, G, WO>( graph, source, target, weightOperations );
@@ -61,12 +62,12 @@ final class DefaultShortestPathAlgorithm
     /**
      * {@inheritDoc}
      */
-    public <WO extends OrderedMonoid<W>> WeightedPath<V, WE, W> applyingDijkstra( WO weightOperations )
+    public <WO extends Monoid<W> & Comparator<W>> WeightedPath<V, WE, W> applyingDijkstra( WO weightOperations )
     {
         weightOperations = checkNotNull( weightOperations, "Dijkstra algorithm can not be applied using null weight operations" );
 
-        final ShortestDistances<V, W> shortestDistances = new ShortestDistances<V, W>( weightOperations );
-        shortestDistances.setWeight( source, weightOperations.zero() );
+        final ShortestDistances<V, W, WO> shortestDistances = new ShortestDistances<V, W, WO>( weightOperations );
+        shortestDistances.setWeight( source, weightOperations.identity() );
 
         final Queue<V> unsettledNodes = new FibonacciHeap<V>( shortestDistances );
         unsettledNodes.add( source );

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultTargetSourceSelector.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultTargetSourceSelector.java?rev=1298136&r1=1298135&r2=1298136&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultTargetSourceSelector.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultTargetSourceSelector.java Wed Mar  7 21:34:21 2012
@@ -21,12 +21,14 @@ package org.apache.commons.graph.shortes
 
 import static org.apache.commons.graph.utils.Assertions.checkNotNull;
 
+import java.util.Comparator;
+
 import org.apache.commons.graph.Vertex;
 import org.apache.commons.graph.VertexPair;
 import org.apache.commons.graph.WeightedEdge;
 import org.apache.commons.graph.WeightedGraph;
 import org.apache.commons.graph.WeightedPath;
-import org.apache.commons.graph.weight.OrderedMonoid;
+import org.apache.commons.graph.weight.Monoid;
 
 final class DefaultTargetSourceSelector<V extends Vertex, WE extends WeightedEdge<W>, W, G extends WeightedGraph<V, WE, W>>
     implements TargetSourceSelector<V, WE, W, G>
@@ -45,12 +47,12 @@ final class DefaultTargetSourceSelector<
     /**
      * {@inheritDoc}
      */
-    public <WO extends OrderedMonoid<W>> AllVertexPairsShortestPath<V, WE, W> applyingBelmannFord( WO weightOperations )
+    public <WO extends Monoid<W> & Comparator<W>> AllVertexPairsShortestPath<V, WE, W, WO> applyingBelmannFord( WO weightOperations )
     {
         weightOperations = checkNotNull( weightOperations, "Belmann-Ford algorithm can not be applied using null weight operations" );
 
-        final ShortestDistances<V, W> shortestDistances = new ShortestDistances<V, W>( weightOperations );
-        shortestDistances.setWeight( source, weightOperations.zero() );
+        final ShortestDistances<V, W, WO> shortestDistances = new ShortestDistances<V, W, WO>( weightOperations );
+        shortestDistances.setWeight( source, weightOperations.identity() );
 
         final PredecessorsList<V, WE, W> predecessors = new PredecessorsList<V, WE, W>( graph, weightOperations );
 
@@ -99,7 +101,7 @@ final class DefaultTargetSourceSelector<
             }
         }
 
-        AllVertexPairsShortestPath<V, WE, W> allVertexPairsShortestPath = new AllVertexPairsShortestPath<V, WE, W>( weightOperations );
+        AllVertexPairsShortestPath<V, WE, W, WO> allVertexPairsShortestPath = new AllVertexPairsShortestPath<V, WE, W, WO>( weightOperations );
 
         for ( V target : graph.getVertices() )
         {

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/HeuristicBuilder.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/HeuristicBuilder.java?rev=1298136&r1=1298135&r2=1298136&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/HeuristicBuilder.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/HeuristicBuilder.java Wed Mar  7 21:34:21 2012
@@ -19,11 +19,13 @@ package org.apache.commons.graph.shortes
  * under the License.
  */
 
+import java.util.Comparator;
+
 import org.apache.commons.graph.Vertex;
 import org.apache.commons.graph.WeightedEdge;
 import org.apache.commons.graph.WeightedGraph;
 import org.apache.commons.graph.WeightedPath;
-import org.apache.commons.graph.weight.OrderedMonoid;
+import org.apache.commons.graph.weight.Monoid;
 
 /**
  *
@@ -32,7 +34,7 @@ import org.apache.commons.graph.weight.O
  * @param <W>
  * @param <G>
  */
-public interface HeuristicBuilder<V extends Vertex, WE extends WeightedEdge<W>, W, G extends WeightedGraph<V, WE, W>, WO extends OrderedMonoid<W>>
+public interface HeuristicBuilder<V extends Vertex, WE extends WeightedEdge<W>, W, G extends WeightedGraph<V, WE, W>, WO extends Comparator<W> & Monoid<W>>
 {
 
     /**

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PathSourceSelector.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PathSourceSelector.java?rev=1298136&r1=1298135&r2=1298136&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PathSourceSelector.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PathSourceSelector.java Wed Mar  7 21:34:21 2012
@@ -19,10 +19,12 @@ package org.apache.commons.graph.shortes
  * under the License.
  */
 
+import java.util.Comparator;
+
 import org.apache.commons.graph.Vertex;
 import org.apache.commons.graph.WeightedEdge;
 import org.apache.commons.graph.WeightedGraph;
-import org.apache.commons.graph.weight.OrderedMonoid;
+import org.apache.commons.graph.weight.Monoid;
 
 /**
  *
@@ -42,7 +44,7 @@ public interface PathSourceSelector<V ex
      * @param weightOperations the weight operations needed for the algorithm
      * @return a data structure which contains all vertex pairs shortest path.
      */
-    <WO extends OrderedMonoid<W>> AllVertexPairsShortestPath<V, WE, W> applyingFloydWarshall( WO weightOperations );
+    <WO extends Monoid<W> & Comparator<W>> AllVertexPairsShortestPath<V, WE, W, WO> applyingFloydWarshall( WO weightOperations );
 
     /**
      * Specifies the shortest path source.

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=1298136&r1=1298135&r2=1298136&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 Wed Mar  7 21:34:21 2012
@@ -24,7 +24,7 @@ import java.util.HashMap;
 import java.util.Map;
 
 import org.apache.commons.graph.Vertex;
-import org.apache.commons.graph.weight.OrderedMonoid;
+import org.apache.commons.graph.weight.Monoid;
 
 /**
  * Stores and compares Graph Vertices weights.
@@ -32,15 +32,15 @@ import org.apache.commons.graph.weight.O
  * @param <V> the Graph vertices type
  * @param <W> the weight type
  */
-final class ShortestDistances<V extends Vertex, W>
+final class ShortestDistances<V extends Vertex, W, WO extends Monoid<W> & Comparator<W>>
     implements Comparator<V>
 {
 
     private final Map<V, W> distances = new HashMap<V, W>();
 
-    private final OrderedMonoid<W> weightOperations;
+    private final WO weightOperations;
 
-    public ShortestDistances( OrderedMonoid<W> weightOperations )
+    public ShortestDistances( WO weightOperations )
     {
         this.weightOperations = weightOperations;
     }

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/ShortestPathAlgorithmSelector.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/ShortestPathAlgorithmSelector.java?rev=1298136&r1=1298135&r2=1298136&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/ShortestPathAlgorithmSelector.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/ShortestPathAlgorithmSelector.java Wed Mar  7 21:34:21 2012
@@ -19,11 +19,13 @@ package org.apache.commons.graph.shortes
  * under the License.
  */
 
+import java.util.Comparator;
+
 import org.apache.commons.graph.Vertex;
 import org.apache.commons.graph.WeightedEdge;
 import org.apache.commons.graph.WeightedGraph;
 import org.apache.commons.graph.WeightedPath;
-import org.apache.commons.graph.weight.OrderedMonoid;
+import org.apache.commons.graph.weight.Monoid;
 
 /**
  *
@@ -43,7 +45,7 @@ public interface ShortestPathAlgorithmSe
      * @param weightOperations the class responsible for operations on weights
      * @return
      */
-    <WO extends OrderedMonoid<W>> HeuristicBuilder<V, WE, W, G, WO> applyingAStar( WO weightOperations );
+    <WO extends Monoid<W> & Comparator<W>> HeuristicBuilder<V, WE, W, G, WO> applyingAStar( WO weightOperations );
 
     /**
      *  Calculates the shortest path using Dijkstra's algorithm.
@@ -52,6 +54,6 @@ public interface ShortestPathAlgorithmSe
      * @param weightOperations the class responsible for operations on weights
      * @return a path which describes the shortest path, if any, otherwise a {@link PathNotFoundException} will be thrown
      */
-    <WO extends OrderedMonoid<W>> WeightedPath<V, WE, W> applyingDijkstra( WO weightOperations );
+    <WO extends Monoid<W> & Comparator<W>> WeightedPath<V, WE, W> applyingDijkstra( WO weightOperations );
 
 }

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/TargetSourceSelector.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/TargetSourceSelector.java?rev=1298136&r1=1298135&r2=1298136&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/TargetSourceSelector.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/TargetSourceSelector.java Wed Mar  7 21:34:21 2012
@@ -19,10 +19,12 @@ package org.apache.commons.graph.shortes
  * under the License.
  */
 
+import java.util.Comparator;
+
 import org.apache.commons.graph.Vertex;
 import org.apache.commons.graph.WeightedEdge;
 import org.apache.commons.graph.WeightedGraph;
-import org.apache.commons.graph.weight.OrderedMonoid;
+import org.apache.commons.graph.weight.Monoid;
 
 /**
  *
@@ -42,7 +44,7 @@ public interface TargetSourceSelector<V 
      * @param weightOperations the weight operations needed for the algorithm
      * @return a data structure which contains all vertex pairs shortest path.
      */
-    <WO extends OrderedMonoid<W>> AllVertexPairsShortestPath<V, WE, W> applyingBelmannFord( WO weightOperations );
+    <WO extends Monoid<W> & Comparator<W>> AllVertexPairsShortestPath<V, WE, W, WO> applyingBelmannFord( WO weightOperations );
 
     /**
      * Specifies the shortest path source.

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeAlgorithmSelector.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeAlgorithmSelector.java?rev=1298136&r1=1298135&r2=1298136&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeAlgorithmSelector.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeAlgorithmSelector.java Wed Mar  7 21:34:21 2012
@@ -23,6 +23,7 @@ import static org.apache.commons.graph.u
 import static org.apache.commons.graph.utils.Assertions.checkNotNull;
 
 
+import java.util.Comparator;
 import java.util.HashMap;
 import java.util.HashSet;
 import java.util.LinkedList;
@@ -38,7 +39,7 @@ 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.Monoid;
 
 /**
  * {@link SpanningTreeAlgorithmSelector} implementation.
@@ -71,7 +72,7 @@ final class DefaultSpanningTreeAlgorithm
     }
 
     /** {@inheritDoc} */
-    public <WO extends OrderedMonoid<W>> SpanningTree<V, WE, W> applyingBoruvkaAlgorithm( WO weightOperations )
+    public <WO extends Monoid<W> & Comparator<W>> SpanningTree<V, WE, W> applyingBoruvkaAlgorithm( WO weightOperations )
     {
         /*
          * <pre>
@@ -170,7 +171,7 @@ final class DefaultSpanningTreeAlgorithm
     /**
      * {@inheritDoc}
      */
-    public <WO extends OrderedMonoid<W>> SpanningTree<V, WE, W> applyingKruskalAlgorithm( WO weightOperations )
+    public <WO extends Monoid<W> & Comparator<W>> SpanningTree<V, WE, W> applyingKruskalAlgorithm( WO weightOperations )
     {
         checkNotNull( weightOperations, "The Kruskal algorithm cannot be calculated with null weight operations" );
         final Set<V> settledNodes = new HashSet<V>();
@@ -216,11 +217,11 @@ final class DefaultSpanningTreeAlgorithm
     /**
      * {@inheritDoc}
      */
-    public <WO extends OrderedMonoid<W>> SpanningTree<V, WE, W> applyingPrimAlgorithm( WO weightOperations )
+    public <WO extends Monoid<W> & Comparator<W>> SpanningTree<V, WE, W> applyingPrimAlgorithm( WO weightOperations )
     {
         checkNotNull( weightOperations, "The Prim algorithm cannot be calculated with null weight operations" );
 
-        final ShortestEdges<V, WE, W> shortestEdges = new ShortestEdges<V, WE, W>( graph, source, weightOperations );
+        final ShortestEdges<V, WE, W, WO> shortestEdges = new ShortestEdges<V, WE, W, WO>( graph, source, weightOperations );
 
         final PriorityQueue<V> unsettledNodes = new PriorityQueue<V>( graph.getOrder(), shortestEdges );
         unsettledNodes.add( source );

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeSourceSelector.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeSourceSelector.java?rev=1298136&r1=1298135&r2=1298136&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeSourceSelector.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeSourceSelector.java Wed Mar  7 21:34:21 2012
@@ -26,6 +26,7 @@ import static org.apache.commons.graph.u
 import static org.apache.commons.graph.utils.Assertions.checkState;
 
 import java.util.ArrayList;
+import java.util.Comparator;
 import java.util.Iterator;
 import java.util.List;
 
@@ -37,7 +38,7 @@ import org.apache.commons.graph.Weighted
 import org.apache.commons.graph.WeightedGraph;
 import org.apache.commons.graph.model.MutableSpanningTree;
 import org.apache.commons.graph.shortestpath.PathNotFoundException;
-import org.apache.commons.graph.weight.OrderedMonoid;
+import org.apache.commons.graph.weight.Monoid;
 
 /**
  * {@link SpanningTreeSourceSelector} implementation.
@@ -80,7 +81,7 @@ public final class DefaultSpanningTreeSo
     /**
      * {@inheritDoc}
      */
-    public <WO extends OrderedMonoid<W>> SpanningTree<V, WE, W> applyingReverseDeleteAlgorithm( WO weightOperations )
+    public <WO extends Monoid<W> & Comparator<W>> SpanningTree<V, WE, W> applyingReverseDeleteAlgorithm( WO weightOperations )
     {
 
         checkNotNull( weightOperations, "The Reverse-Delete algorithm cannot be calulated with null weight operations" );

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=1298136&r1=1298135&r2=1298136&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 Mar  7 21:34:21 2012
@@ -31,7 +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;
+import org.apache.commons.graph.weight.Monoid;
 
 /**
  * The predecessor list is a list of {@link Vertex} of a {@link org.apache.commons.graph.Graph}.
@@ -41,19 +41,19 @@ import org.apache.commons.graph.weight.O
  * @param <E> the Graph edges type
  * @param <W> the weight type
  */
-final class ShortestEdges<V extends Vertex, WE extends WeightedEdge<W>, W>
+final class ShortestEdges<V extends Vertex, WE extends WeightedEdge<W>, W, WO extends Monoid<W> & Comparator<W>>
     implements Comparator<V>
 {
 
     private final Map<V, WE> predecessors = new HashMap<V, WE>();
 
-    private final OrderedMonoid<W> weightOperations;
+    private final WO weightOperations;
     
     private final Graph<V, WE> graph;
 
     private final V source;
 
-    public ShortestEdges(Graph<V, WE> graph, V source, OrderedMonoid<W> weightOperations )
+    public ShortestEdges(Graph<V, WE> graph, V source, WO weightOperations )
     {
         this.graph = graph;
         this.source = source;
@@ -132,7 +132,7 @@ final class ShortestEdges<V extends Vert
     {
         if ( source.equals( vertex ) )
         {
-            return weightOperations.zero();
+            return weightOperations.identity();
         }
 
         WE edge = predecessors.get( vertex );

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/SpanningTreeAlgorithmSelector.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/SpanningTreeAlgorithmSelector.java?rev=1298136&r1=1298135&r2=1298136&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/SpanningTreeAlgorithmSelector.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/SpanningTreeAlgorithmSelector.java Wed Mar  7 21:34:21 2012
@@ -19,11 +19,13 @@ package org.apache.commons.graph.spannin
  * under the License.
  */
 
+import java.util.Comparator;
+
 import org.apache.commons.graph.Graph;
 import org.apache.commons.graph.SpanningTree;
 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.Monoid;
 
 /**
  * Spanning Tree algoritms selector.
@@ -43,7 +45,7 @@ public interface SpanningTreeAlgorithmSe
      * @param weightOperations the class responsible for operations on weights
      * @return the calculated spanning tree
      */
-    <WO extends OrderedMonoid<W>> SpanningTree<V, WE, W> applyingBoruvkaAlgorithm( WO weightOperations );
+    <WO extends Monoid<W> & Comparator<W>> SpanningTree<V, WE, W> applyingBoruvkaAlgorithm( WO weightOperations );
 
     /**
      * Applies the <a href="http://en.wikipedia.org/wiki/Kruskal%27s_algorithm">Kruskal</a>'s algorithm.
@@ -52,7 +54,7 @@ public interface SpanningTreeAlgorithmSe
      * @param weightOperations the class responsible for operations on weights
      * @return the calculated spanning tree
      */
-    <WO extends OrderedMonoid<W>> SpanningTree<V, WE, W> applyingKruskalAlgorithm( WO weightOperations );
+    <WO extends Monoid<W> & Comparator<W>> SpanningTree<V, WE, W> applyingKruskalAlgorithm( WO weightOperations );
 
     /**
      * Applies the <a href="http://en.wikipedia.org/wiki/Prim%27s_algorithm">Prim</a>'s algorithm.
@@ -61,6 +63,6 @@ public interface SpanningTreeAlgorithmSe
      * @param weightOperations the class responsible for operations on weights
      * @return the calculated spanning tree
      */
-    <WO extends OrderedMonoid<W>> SpanningTree<V, WE, W> applyingPrimAlgorithm( WO weightOperations );
+    <WO extends Monoid<W> & Comparator<W>> SpanningTree<V, WE, W> applyingPrimAlgorithm( WO weightOperations );
 
 }

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/SpanningTreeSourceSelector.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/SpanningTreeSourceSelector.java?rev=1298136&r1=1298135&r2=1298136&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/SpanningTreeSourceSelector.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/SpanningTreeSourceSelector.java Wed Mar  7 21:34:21 2012
@@ -19,11 +19,13 @@ package org.apache.commons.graph.spannin
  * under the License.
  */
 
+import java.util.Comparator;
+
 import org.apache.commons.graph.Graph;
 import org.apache.commons.graph.SpanningTree;
 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.Monoid;
 
 /**
  * Spanning Tree source selector.
@@ -71,6 +73,6 @@ public interface SpanningTreeSourceSelec
      * @param weightOperations the weight operations
      * @return the calculated spanning tree
      */
-    <WO extends OrderedMonoid<W>> SpanningTree<V, WE, W> applyingReverseDeleteAlgorithm( WO weightOperations );
+    <WO extends Monoid<W> & Comparator<W>> SpanningTree<V, WE, W> applyingReverseDeleteAlgorithm( WO weightOperations );
 
 }

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=1298136&r1=1298135&r2=1298136&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 Mar  7 21:34:21 2012
@@ -22,17 +22,34 @@ package org.apache.commons.graph.weight;
 /**
  * A {@link Monoid} is a {@link Semigroup} with an identity value.
  *
- * @param <M> the type of the elements in the {@link Monoid}
+ * @param <E> the type of the elements in the {@link Monoid}
  */
-public interface Monoid<M>
-    extends Zero<M>, Semigroup<M>
+public interface Monoid<E>
 {
 
     /**
+     * Returns the identity value.
+     *
+     * @return the identity value
+     */
+    E identity();
+
+    /**
+     * Returns the result of the associative binary operation defined by this
+     * monoid between two elements of appropriate type.
+     *
+     * @param s1 the first element
+     * @param element2 the second element
+     * @return the result of the associative binary operation
+     */
+    E append( E element1, E element2 );
+
+    /**
      * Returns the inverse of the input element.
+     *
      * @param element the input element
      * @return the inverse of the input element
      */
-    M inverse( M element );
+    E inverse( E element );
 
 }

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/BigDecimalWeightBaseOperations.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/BigDecimalWeightBaseOperations.java?rev=1298136&r1=1298135&r2=1298136&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/BigDecimalWeightBaseOperations.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/BigDecimalWeightBaseOperations.java Wed Mar  7 21:34:21 2012
@@ -22,21 +22,22 @@ package org.apache.commons.graph.weight.
 import static java.math.BigDecimal.ZERO;
 
 import java.math.BigDecimal;
+import java.util.Comparator;
 
-import org.apache.commons.graph.weight.OrderedMonoid;
+import org.apache.commons.graph.weight.Monoid;
 
 /**
  * The class {@link BigDecimalWeightBaseOperations} provides operations and properties
  * for weights of type {@link BigDecimal}.
  */
 public class BigDecimalWeightBaseOperations
-    implements OrderedMonoid<BigDecimal>
+    implements Monoid<BigDecimal>, Comparator<BigDecimal>
 {
 
     /**
      * {@inheritDoc}
      */
-    public BigDecimal zero()
+    public BigDecimal identity()
     {
         return ZERO;
     }

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/BigIntegerWeightBaseOperations.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/BigIntegerWeightBaseOperations.java?rev=1298136&r1=1298135&r2=1298136&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/BigIntegerWeightBaseOperations.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/BigIntegerWeightBaseOperations.java Wed Mar  7 21:34:21 2012
@@ -22,21 +22,22 @@ package org.apache.commons.graph.weight.
 import static java.math.BigInteger.ZERO;
 
 import java.math.BigInteger;
+import java.util.Comparator;
 
-import org.apache.commons.graph.weight.OrderedMonoid;
+import org.apache.commons.graph.weight.Monoid;
 
 /**
  * The class {@link BigIntegerWeightBaseOperations} provides operations and properties
  * for weights of type {@link BigInteger}.
  */
 public class BigIntegerWeightBaseOperations
-    implements OrderedMonoid<BigInteger>
+    implements Monoid<BigInteger>, Comparator<BigInteger>
 {
 
     /**
      * {@inheritDoc}
      */
-    public BigInteger zero()
+    public BigInteger identity()
     {
         return ZERO;
     }

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/DoubleWeightBaseOperations.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/DoubleWeightBaseOperations.java?rev=1298136&r1=1298135&r2=1298136&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/DoubleWeightBaseOperations.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/DoubleWeightBaseOperations.java Wed Mar  7 21:34:21 2012
@@ -19,20 +19,22 @@ package org.apache.commons.graph.weight.
  * under the License.
  */
 
-import org.apache.commons.graph.weight.OrderedMonoid;
+import java.util.Comparator;
+
+import org.apache.commons.graph.weight.Monoid;
 
 /**
  * The class {@link DoubleWeightBaseOperations} provides operations and properties
  * for weights of type {@link Double}.
  */
 public class DoubleWeightBaseOperations
-    implements OrderedMonoid<Double>
+    implements Monoid<Double>, Comparator<Double>
 {
 
     /**
      * {@inheritDoc}
      */
-    public Double zero()
+    public Double identity()
     {
         return 0.0;
     }

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/FloatWeightBaseOperations.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/FloatWeightBaseOperations.java?rev=1298136&r1=1298135&r2=1298136&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/FloatWeightBaseOperations.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/FloatWeightBaseOperations.java Wed Mar  7 21:34:21 2012
@@ -19,20 +19,22 @@ package org.apache.commons.graph.weight.
  * under the License.
  */
 
-import org.apache.commons.graph.weight.OrderedMonoid;
+import java.util.Comparator;
+
+import org.apache.commons.graph.weight.Monoid;
 
 /**
  * The class {@link FloatWeightBaseOperations} provides operations and properties
  * for weights of type {@link Float}.
  */
 public class FloatWeightBaseOperations
-    implements OrderedMonoid<Float>
+    implements Monoid<Float>, Comparator<Float>
 {
 
     /**
      * {@inheritDoc}
      */
-    public Float zero()
+    public Float identity()
     {
         return 0.0F;
     }

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/IntegerWeightBaseOperations.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/IntegerWeightBaseOperations.java?rev=1298136&r1=1298135&r2=1298136&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/IntegerWeightBaseOperations.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/IntegerWeightBaseOperations.java Wed Mar  7 21:34:21 2012
@@ -19,20 +19,22 @@ package org.apache.commons.graph.weight.
  * under the License.
  */
 
-import org.apache.commons.graph.weight.OrderedMonoid;
+import java.util.Comparator;
+
+import org.apache.commons.graph.weight.Monoid;
 
 /**
  * The class {@link IntegerWeightBaseOperations} provides operations and properties
  * for weights of type {@link Integer}.
  */
 public class IntegerWeightBaseOperations
-    implements OrderedMonoid<Integer>
+    implements Monoid<Integer>, Comparator<Integer>
 {
 
     /**
      * {@inheritDoc}
      */
-    public Integer zero()
+    public Integer identity()
     {
         return 0;
     }

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/LongWeightBaseOperations.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/LongWeightBaseOperations.java?rev=1298136&r1=1298135&r2=1298136&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/LongWeightBaseOperations.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/LongWeightBaseOperations.java Wed Mar  7 21:34:21 2012
@@ -19,20 +19,22 @@ package org.apache.commons.graph.weight.
  * under the License.
  */
 
-import org.apache.commons.graph.weight.OrderedMonoid;
+import java.util.Comparator;
+
+import org.apache.commons.graph.weight.Monoid;
 
 /**
  * The class {@link LongWeightBaseOperations} provides operations and properties
  * for weights of type {@link Long}.
  */
 public class LongWeightBaseOperations
-    implements OrderedMonoid<Long>
+    implements Monoid<Long>, Comparator<Long>
 {
 
     /**
      * {@inheritDoc}
      */
-    public Long zero()
+    public Long identity()
     {
         return 0L;
     }

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=1298136&r1=1298135&r2=1298136&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 Wed Mar  7 21:34:21 2012
@@ -83,7 +83,7 @@ public final class BellmannFordTestCase
         BaseLabeledVertex a = null;
         BaseLabeledVertex b = null;
         // the actual weighted path
-        AllVertexPairsShortestPath<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> allVertexPairsShortestPath =
+        AllVertexPairsShortestPath<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double, DoubleWeightBaseOperations> allVertexPairsShortestPath =
             null;
         try
         {
@@ -149,7 +149,7 @@ public final class BellmannFordTestCase
         expected.addConnectionInTail( four, new BaseLabeledWeightedEdge<Double>( "4 -> 3", -3D ), three );
 
         // the actual weighted path
-        AllVertexPairsShortestPath<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> allVertexPairsShortestPath =
+        AllVertexPairsShortestPath<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double, DoubleWeightBaseOperations> allVertexPairsShortestPath =
             findShortestPath( graph ).from( one ).applyingBelmannFord( new DoubleWeightBaseOperations() );
 
         WeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> actual =

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=1298136&r1=1298135&r2=1298136&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 Wed Mar  7 21:34:21 2012
@@ -62,7 +62,7 @@ public class FloydWarshallTestCase
         graph.addVertex( b );
 
         // the actual weighted path
-        AllVertexPairsShortestPath<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> p =
+        AllVertexPairsShortestPath<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double, DoubleWeightBaseOperations> p =
             findShortestPath( graph ).applyingFloydWarshall( new DoubleWeightBaseOperations() );
 
         p.findShortestPath( a, b );
@@ -115,7 +115,7 @@ public class FloydWarshallTestCase
         mutable.addEdge( four, new BaseLabeledWeightedEdge<Double>( "4 -> 5", 6D ), five );
         mutable.addEdge( six, new BaseLabeledWeightedEdge<Double>( "6 -> 5", 9D ), five );
 
-        AllVertexPairsShortestPath<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> p =
+        AllVertexPairsShortestPath<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double, DoubleWeightBaseOperations> p =
             findShortestPath( weighted ).applyingFloydWarshall( new DoubleWeightBaseOperations() );
 
         if ( weighted instanceof UndirectedGraph )



Mime
View raw message