You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by cs...@apache.org on 2012/03/07 22:34:22 UTC
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...
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 )