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/02/22 14:21:05 UTC
svn commit: r1292272 [1/2] - in /commons/sandbox/graph/trunk/src: changes/
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/ ...
Author: cs
Date: Wed Feb 22 13:21:03 2012
New Revision: 1292272
URL: http://svn.apache.org/viewvc?rev=1292272&view=rev
Log:
corrected names for classes and variables related to operations on weights
Added:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/BigDecimalWeightBaseOperations.java
- copied, changed from r1290988, commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/BigDecimalWeight.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/BigIntegerWeightBaseOperations.java
- copied, changed from r1290988, commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/BigIntegerWeight.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/DoubleWeightBaseOperations.java
- copied, changed from r1290988, commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/DoubleWeight.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/FloatWeightBaseOperations.java
- copied, changed from r1290988, commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/FloatWeight.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/IntegerWeightBaseOperations.java
- copied, changed from r1290988, commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/IntegerWeight.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/LongWeightBaseOperations.java
- copied, changed from r1290988, commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/LongWeight.java
Removed:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/BigDecimalWeight.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/BigIntegerWeight.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/DoubleWeight.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/FloatWeight.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/IntegerWeight.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/LongWeight.java
Modified:
commons/sandbox/graph/trunk/src/changes/changes.xml
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/PredecessorsList.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/spanning/SuperVertex.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/WeightedEdgesComparator.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/package-info.java
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/flow/EdmondsKarpTestCase.java
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/flow/FordFulkersonTestCase.java
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/AStarTestCase.java
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/BellmannFordTestCase.java
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/DijkstraTestCase.java
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/FloydWarshallTestCase.java
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/BoruvkaTestCase.java
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/KruskalTestCase.java
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/PrimTestCase.java
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/ReverseDeleteTestCase.java
Modified: commons/sandbox/graph/trunk/src/changes/changes.xml
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/changes/changes.xml?rev=1292272&r1=1292271&r2=1292272&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/changes/changes.xml (original)
+++ commons/sandbox/graph/trunk/src/changes/changes.xml Wed Feb 22 13:21:03 2012
@@ -23,6 +23,9 @@
</properties>
<body>
<release version="0.1" date="201?-??-??" description="First release.">
+ <action dev="cs" type="fix" issue="SANDBOX-395">
+ Correct names for classes and variables related to operations on weights
+ </action>
<action dev="marcosperanza" type="fix" issue="SANDBOX-394">
Add containsEdge and containsVertex into Graph interface
</action>
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=1292272&r1=1292271&r2=1292272&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 Feb 22 13:21:03 2012
@@ -59,15 +59,15 @@ final class DefaultMaxFlowAlgorithmSelec
/**
* {@inheritDoc}
*/
- public <OM extends OrderedMonoid<W>> W applyingFordFulkerson( OM orderedMonoid )
+ public <WO extends OrderedMonoid<W>> W applyingFordFulkerson( WO weightOperations )
{
- final OM checkedOrderedMonoid = checkNotNull( orderedMonoid, "Weight monoid can not be null to find the max flow in the graph" );
+ final WO checkedWeightOperations = checkNotNull( weightOperations, "Weight operations can not be null to find the max flow in the graph" );
// create flow network
- final DirectedGraph<V, WeightedEdge<W>> flowNetwork = newFlowNetwok( graph, checkedOrderedMonoid );
+ 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, checkedOrderedMonoid );
+ final FlowNetworkHandler<V, W> flowNetworkHandler = new FlowNetworkHandler<V, W>( flowNetwork, source, target, checkedWeightOperations );
// perform depth first search
visit( flowNetwork ).from( source ).applyingDepthFirstSearch( flowNetworkHandler );
@@ -86,15 +86,15 @@ final class DefaultMaxFlowAlgorithmSelec
/**
* {@inheritDoc}
*/
- public <OM extends OrderedMonoid<W>> W applyingEdmondsKarp( OM orderedMonoid )
+ public <WO extends OrderedMonoid<W>> W applyingEdmondsKarp( WO weightOperations )
{
- final OM checkedOrderedMonoid = checkNotNull( orderedMonoid, "Weight monoid can not be null to find the max flow in the graph" );
+ final WO checkedWeightOperations = checkNotNull( weightOperations, "Weight operations can not be null to find the max flow in the graph" );
// create flow network
- final DirectedGraph<V, WeightedEdge<W>> flowNetwork = newFlowNetwok( graph, checkedOrderedMonoid );
+ 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, checkedOrderedMonoid );
+ final FlowNetworkHandler<V, W> flowNetworkHandler = new FlowNetworkHandler<V, W>( flowNetwork, source, target, checkedWeightOperations );
// perform breadth first search
visit( flowNetwork ).from( source ).applyingBreadthFirstSearch( flowNetworkHandler );
@@ -110,7 +110,7 @@ final class DefaultMaxFlowAlgorithmSelec
return flowNetworkHandler.onCompleted();
}
- private <OM extends OrderedMonoid<W>> DirectedGraph<V, WeightedEdge<W>> newFlowNetwok( final G graph, final OM orderedMonoid )
+ private <WO extends OrderedMonoid<W>> DirectedGraph<V, WeightedEdge<W>> newFlowNetwok( final G graph, final WO weightOperations )
{
return newDirectedMutableWeightedGraph( new AbstractGraphConnection<V, WeightedEdge<W>>()
{
@@ -134,7 +134,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, orderedMonoid.zero() ) )
+ addEdge( new BaseLabeledWeightedEdge<W>( "Inverse edge for " + edge, weightOperations.zero() ) )
.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=1292272&r1=1292271&r2=1292272&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 Feb 22 13:21:03 2012
@@ -48,7 +48,7 @@ class FlowNetworkHandler<V extends Verte
private final V target;
- private final OrderedMonoid<W> orderedMonoid;
+ private final OrderedMonoid<W> weightOperations;
private W maxFlow;
@@ -59,14 +59,14 @@ class FlowNetworkHandler<V extends Verte
private boolean foundAugmentingPath;
- FlowNetworkHandler( DirectedGraph<V, WeightedEdge<W>> flowNetwork, V source, V target, OrderedMonoid<W> orderedMonoid )
+ FlowNetworkHandler( DirectedGraph<V, WeightedEdge<W>> flowNetwork, V source, V target, OrderedMonoid<W> weightOperations )
{
this.flowNetwork = flowNetwork;
this.source = source;
this.target = target;
- this.orderedMonoid = orderedMonoid;
+ this.weightOperations = weightOperations;
- maxFlow = orderedMonoid.zero();
+ maxFlow = weightOperations.zero();
for ( WeightedEdge<W> edge : flowNetwork.getEdges() )
{
@@ -101,25 +101,25 @@ class FlowNetworkHandler<V extends Verte
{
W edgeCapacity = residualEdgeCapacities.get( edge );
if ( flowIncrement == null
- || orderedMonoid.compare( edgeCapacity, flowIncrement ) < 0 )
+ || weightOperations.compare( edgeCapacity, flowIncrement ) < 0 )
{
flowIncrement = edgeCapacity;
}
}
// update max flow and capacities accordingly
- maxFlow = orderedMonoid.append( maxFlow, flowIncrement );
+ maxFlow = weightOperations.append( maxFlow, flowIncrement );
for ( WeightedEdge<W> edge : augmentingPath.getEdges() )
{
// decrease capacity for direct edge
W directCapacity = residualEdgeCapacities.get( edge );
- residualEdgeCapacities.put( edge, orderedMonoid.append( directCapacity, orderedMonoid.inverse( flowIncrement ) ) );
+ residualEdgeCapacities.put( edge, weightOperations.append( directCapacity, weightOperations.inverse( flowIncrement ) ) );
// increase capacity for inverse edge
VertexPair<V> vertexPair = flowNetwork.getVertices( edge );
WeightedEdge<W> inverseEdge = flowNetwork.getEdge( vertexPair.getTail(), vertexPair.getHead() );
W inverseCapacity = residualEdgeCapacities.get( inverseEdge );
- residualEdgeCapacities.put( inverseEdge, orderedMonoid.append( inverseCapacity, flowIncrement ) );
+ residualEdgeCapacities.put( inverseEdge, weightOperations.append( inverseCapacity, flowIncrement ) );
}
}
@@ -130,7 +130,7 @@ class FlowNetworkHandler<V extends Verte
public void discoverGraph( DirectedGraph<V, WeightedEdge<W>> graph )
{
// reset ausiliary structures for a new graph visit
- predecessors = new PredecessorsList<V, WeightedEdge<W>, W>( graph, orderedMonoid );
+ predecessors = new PredecessorsList<V, WeightedEdge<W>, W>( graph, weightOperations );
foundAugmentingPath = false;
}
@@ -142,7 +142,7 @@ class FlowNetworkHandler<V extends Verte
{
W residualEdgeCapacity = residualEdgeCapacities.get( edge );
// avoid expanding the edge when it has no residual capacity
- if ( orderedMonoid.compare( residualEdgeCapacity, orderedMonoid.zero() ) <= 0 )
+ if ( weightOperations.compare( residualEdgeCapacity, weightOperations.zero() ) <= 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=1292272&r1=1292271&r2=1292272&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 Feb 22 13:21:03 2012
@@ -28,19 +28,21 @@ public interface MaxFlowAlgorithmSelecto
{
/**
+ * Calculates the maximum flow using the Ford-Fulkerson method.
*
- *
- * @param orderedMonoid
+ * @param <WO> the type of weight operations
+ * @param weightOperations the class responsible for operations on weights
* @return
*/
- <OM extends OrderedMonoid<W>> W applyingFordFulkerson( OM orderedMonoid );
+ <WO extends OrderedMonoid<W>> W applyingFordFulkerson( WO weightOperations );
/**
+ * Calculates the maximum flow using the Edmonds-Karp algorithm.
*
- *
- * @param orderedMonoid
+ * @param <WO> the type of weight operations
+ * @param weightOperations the class responsible for operations on weights
* @return
*/
- <OM extends OrderedMonoid<W>> W applyingEdmondsKarp( OM orderedMonoid );
+ <WO extends OrderedMonoid<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=1292272&r1=1292271&r2=1292272&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 Feb 22 13:21:03 2012
@@ -46,13 +46,13 @@ public final class InMemoryWeightedPath<
private W weight;
- private Monoid<W> monoid;
+ private Monoid<W> weightOperations;
- public InMemoryWeightedPath( V start, V target, Monoid<W> monoid )
+ public InMemoryWeightedPath( V start, V target, Monoid<W> weightOperations )
{
super( start, target );
- this.monoid = monoid;
- this.weight = monoid.zero();
+ this.weightOperations = weightOperations;
+ this.weight = weightOperations.zero();
}
/**
@@ -82,7 +82,7 @@ public final class InMemoryWeightedPath<
*/
private void increaseWeight( WE edge )
{
- weight = monoid.append( edge.getWeight(), weight );
+ weight = weightOperations.append( edge.getWeight(), weight );
}
/**
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=1292272&r1=1292271&r2=1292272&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 Feb 22 13:21:03 2012
@@ -38,13 +38,13 @@ public final class MutableSpanningTree<V
private static final long serialVersionUID = -4371938772248573879L;
- private Monoid<W> monoid;
+ private Monoid<W> weightOperations;
private W weight;
- public MutableSpanningTree(Monoid<W> monoid) {
- this.monoid = monoid;
- this.weight = monoid.zero();
+ public MutableSpanningTree(Monoid<W> weightOperations) {
+ this.weightOperations = weightOperations;
+ this.weight = weightOperations.zero();
}
/**
@@ -62,7 +62,7 @@ public final class MutableSpanningTree<V
protected void decorateAddEdge( V head, WE e, V tail )
{
super.decorateAddEdge( head, e, tail );
- weight = monoid.append( weight, e.getWeight() );
+ weight = weightOperations.append( weight, e.getWeight() );
}
/**
@@ -71,7 +71,7 @@ public final class MutableSpanningTree<V
@Override
protected void decorateRemoveEdge( WE e )
{
- weight = monoid.append( weight, monoid.inverse( e.getWeight() ) );
+ weight = weightOperations.append( weight, weightOperations.inverse( e.getWeight() ) );
}
}
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=1292272&r1=1292271&r2=1292272&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 Feb 22 13:21:03 2012
@@ -44,14 +44,14 @@ public final class AllVertexPairsShortes
private final Map<VertexPair<V>, W> shortestDistances = new HashMap<VertexPair<V>, W>();
- private final OrderedMonoid<W> orderedMonoid;
+ private final OrderedMonoid<W> weightOperations;
/**
* Constructor visible only inside the package
*/
- AllVertexPairsShortestPath( OrderedMonoid<W> orderedMonoid )
+ AllVertexPairsShortestPath( OrderedMonoid<W> weightOperations )
{
- this.orderedMonoid = orderedMonoid;
+ this.weightOperations = weightOperations;
}
/**
@@ -118,7 +118,7 @@ public final class AllVertexPairsShortes
if ( source.equals( target ) )
{
- return orderedMonoid.zero();
+ return weightOperations.zero();
}
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=1292272&r1=1292271&r2=1292272&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 Feb 22 13:21:03 2012
@@ -33,8 +33,8 @@ import org.apache.commons.graph.Weighted
import org.apache.commons.graph.collections.FibonacciHeap;
import org.apache.commons.graph.weight.OrderedMonoid;
-final class DefaultHeuristicBuilder<V extends Vertex, WE extends WeightedEdge<W>, W, G extends WeightedGraph<V, WE, W>, OM extends OrderedMonoid<W>>
- implements HeuristicBuilder<V, WE, W, G, OM>
+final class DefaultHeuristicBuilder<V extends Vertex, WE extends WeightedEdge<W>, W, G extends WeightedGraph<V, WE, W>, WO extends OrderedMonoid<W>>
+ implements HeuristicBuilder<V, WE, W, G, WO>
{
private final G graph;
@@ -43,14 +43,14 @@ final class DefaultHeuristicBuilder<V ex
private final V goal;
- private final OM orderedMonoid;
+ private final WO weightOperations;
- public DefaultHeuristicBuilder( G graph, V source, V target, OM orderedMonoid )
+ public DefaultHeuristicBuilder( G graph, V source, V target, WO weightOperations )
{
this.graph = graph;
this.start = source;
this.goal = target;
- this.orderedMonoid = orderedMonoid;
+ this.weightOperations = weightOperations;
}
/**
@@ -61,11 +61,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>( orderedMonoid );
- gScores.setWeight( start, orderedMonoid.zero() );
+ final ShortestDistances<V, W> gScores = new ShortestDistances<V, W>( weightOperations );
+ gScores.setWeight( start, weightOperations.zero() );
// Estimated total cost from start to goal through y.
- final ShortestDistances<V, W> fScores = new ShortestDistances<V, W>( orderedMonoid );
+ final ShortestDistances<V, W> fScores = new ShortestDistances<V, W>( weightOperations );
W hScore = heuristic.applyHeuristic( start, goal );
fScores.setWeight( start, hScore );
@@ -77,7 +77,7 @@ final class DefaultHeuristicBuilder<V ex
openSet.add( start );
// The of navigated nodes
- final PredecessorsList<V, WE, W> predecessors = new PredecessorsList<V, WE, W>( graph, orderedMonoid );
+ final PredecessorsList<V, WE, W> predecessors = new PredecessorsList<V, WE, W>( graph, weightOperations );
// extract the node in openset having the lowest f_score[] value
while ( !openSet.isEmpty() )
@@ -101,15 +101,15 @@ final class DefaultHeuristicBuilder<V ex
{
WE edge = graph.getEdge( current, v );
// note that the weight of current can never be undefined
- W tentativeGScore = orderedMonoid.append( gScores.getWeight( current ), edge.getWeight() );
+ W tentativeGScore = weightOperations.append( gScores.getWeight( current ), edge.getWeight() );
// if the first condition fails, v has already been visited (its weight is defined)
- if ( openSet.add( v ) || orderedMonoid.compare( tentativeGScore, gScores.getWeight( v ) ) < 0 )
+ if ( openSet.add( v ) || weightOperations.compare( tentativeGScore, gScores.getWeight( v ) ) < 0 )
{
predecessors.addPredecessor( v, current );
gScores.setWeight( v, tentativeGScore );
hScore = heuristic.applyHeuristic( v, goal );
- fScores.setWeight( v, orderedMonoid.append( gScores.getWeight( v ), hScore ) );
+ fScores.setWeight( v, weightOperations.append( gScores.getWeight( v ), 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=1292272&r1=1292271&r2=1292272&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 Feb 22 13:21:03 2012
@@ -46,11 +46,11 @@ public final class DefaultPathSourceSele
/**
* {@inheritDoc}
*/
- public <OM extends OrderedMonoid<W>> AllVertexPairsShortestPath<V, WE, W> applyingFloydWarshall( OM orderedMonoid )
+ public <WO extends OrderedMonoid<W>> AllVertexPairsShortestPath<V, WE, W> applyingFloydWarshall( WO weightOperations )
{
- orderedMonoid = checkNotNull( orderedMonoid, "Floyd-Warshall algorithm can not be applied using a null weight monoid" );
+ weightOperations = checkNotNull( weightOperations, "Floyd-Warshall algorithm can not be applied using null weight operations" );
- AllVertexPairsShortestPath<V, WE, W> shortestPaths = new AllVertexPairsShortestPath<V, WE, W>( orderedMonoid );
+ AllVertexPairsShortestPath<V, WE, W> shortestPaths = new AllVertexPairsShortestPath<V, WE, W>( weightOperations );
Map<VertexPair<V>, V> next = new HashMap<VertexPair<V>, V>();
// init
@@ -74,9 +74,9 @@ public final class DefaultPathSourceSele
{
if ( shortestPaths.hasShortestDistance( i, k ) && shortestPaths.hasShortestDistance( k, j ) )
{
- W newDistance = orderedMonoid.append( shortestPaths.getShortestDistance( i, k ), shortestPaths.getShortestDistance( k, j ) );
+ W newDistance = weightOperations.append( shortestPaths.getShortestDistance( i, k ), shortestPaths.getShortestDistance( k, j ) );
if ( !shortestPaths.hasShortestDistance( i, j )
- || orderedMonoid.compare( newDistance, shortestPaths.getShortestDistance( i, j ) ) < 0 )
+ || weightOperations.compare( newDistance, shortestPaths.getShortestDistance( i, j ) ) < 0 )
{
shortestPaths.addShortestDistance( i, j, newDistance );
@@ -96,7 +96,7 @@ public final class DefaultPathSourceSele
{
if ( !source.equals( target ) )
{
- PredecessorsList<V, WE, W> predecessorsList = new PredecessorsList<V, WE, W>( graph, orderedMonoid );
+ PredecessorsList<V, WE, W> predecessorsList = new PredecessorsList<V, WE, W>( graph, weightOperations );
pathReconstruction( predecessorsList, source, target, next );
if ( !predecessorsList.isEmpty() )
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=1292272&r1=1292271&r2=1292272&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 Feb 22 13:21:03 2012
@@ -52,28 +52,28 @@ final class DefaultShortestPathAlgorithm
/**
* {@inheritDoc}
*/
- public <OM extends OrderedMonoid<W>> HeuristicBuilder<V, WE, W, G, OM> applyingAStar( OM orderedMonoid )
+ public <WO extends OrderedMonoid<W>> HeuristicBuilder<V, WE, W, G, WO> applyingAStar( WO weightOperations )
{
- orderedMonoid = checkNotNull( orderedMonoid, "A* algorithm can not be applied using a null weight monoid" );
- return new DefaultHeuristicBuilder<V, WE, W, G, OM>( graph, source, target, orderedMonoid );
+ 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 );
}
/**
* {@inheritDoc}
*/
- public <OM extends OrderedMonoid<W>> WeightedPath<V, WE, W> applyingDijkstra( OM orderedMonoid )
+ public <WO extends OrderedMonoid<W>> WeightedPath<V, WE, W> applyingDijkstra( WO weightOperations )
{
- orderedMonoid = checkNotNull( orderedMonoid, "Dijkstra algorithm can not be applied using a null weight monoid" );
+ weightOperations = checkNotNull( weightOperations, "Dijkstra algorithm can not be applied using null weight operations" );
- final ShortestDistances<V, W> shortestDistances = new ShortestDistances<V, W>( orderedMonoid );
- shortestDistances.setWeight( source, orderedMonoid.zero() );
+ final ShortestDistances<V, W> shortestDistances = new ShortestDistances<V, W>( weightOperations );
+ shortestDistances.setWeight( source, weightOperations.zero() );
final Queue<V> unsettledNodes = new FibonacciHeap<V>( shortestDistances );
unsettledNodes.add( source );
final Set<V> settledNodes = new HashSet<V>();
- final PredecessorsList<V, WE, W> predecessors = new PredecessorsList<V, WE, W>( graph, orderedMonoid );
+ final PredecessorsList<V, WE, W> predecessors = new PredecessorsList<V, WE, W>( graph, weightOperations );
// extract the node with the shortest distance
while ( !unsettledNodes.isEmpty() )
@@ -96,10 +96,10 @@ final class DefaultShortestPathAlgorithm
WE edge = graph.getEdge( vertex, v );
if ( shortestDistances.alreadyVisited( vertex ) )
{
- W shortDist = orderedMonoid.append( shortestDistances.getWeight( vertex ), edge.getWeight() );
+ W shortDist = weightOperations.append( shortestDistances.getWeight( vertex ), edge.getWeight() );
if ( !shortestDistances.alreadyVisited( v )
- || orderedMonoid.compare( shortDist, shortestDistances.getWeight( v ) ) < 0 )
+ || weightOperations.compare( shortDist, shortestDistances.getWeight( v ) ) < 0 )
{
// assign new shortest distance and mark unsettled
shortestDistances.setWeight( v, shortDist );
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=1292272&r1=1292271&r2=1292272&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 Feb 22 13:21:03 2012
@@ -45,14 +45,14 @@ final class DefaultTargetSourceSelector<
/**
* {@inheritDoc}
*/
- public <OM extends OrderedMonoid<W>> AllVertexPairsShortestPath<V, WE, W> applyingBelmannFord( OM orderedMonoid )
+ public <WO extends OrderedMonoid<W>> AllVertexPairsShortestPath<V, WE, W> applyingBelmannFord( WO weightOperations )
{
- orderedMonoid = checkNotNull( orderedMonoid, "Belmann-Ford algorithm can not be applied using a null weight monoid" );
+ weightOperations = checkNotNull( weightOperations, "Belmann-Ford algorithm can not be applied using null weight operations" );
- final ShortestDistances<V, W> shortestDistances = new ShortestDistances<V, W>( orderedMonoid );
- shortestDistances.setWeight( source, orderedMonoid.zero() );
+ final ShortestDistances<V, W> shortestDistances = new ShortestDistances<V, W>( weightOperations );
+ shortestDistances.setWeight( source, weightOperations.zero() );
- final PredecessorsList<V, WE, W> predecessors = new PredecessorsList<V, WE, W>( graph, orderedMonoid );
+ final PredecessorsList<V, WE, W> predecessors = new PredecessorsList<V, WE, W>( graph, weightOperations );
for ( int i = 0; i < graph.getOrder(); i++ )
{
@@ -64,10 +64,10 @@ final class DefaultTargetSourceSelector<
if ( shortestDistances.alreadyVisited( u ) )
{
- W shortDist = orderedMonoid.append( shortestDistances.getWeight( u ), edge.getWeight() );
+ W shortDist = weightOperations.append( shortestDistances.getWeight( u ), edge.getWeight() );
if ( !shortestDistances.alreadyVisited( v )
- || orderedMonoid.compare( shortDist, shortestDistances.getWeight( v ) ) < 0 )
+ || weightOperations.compare( shortDist, shortestDistances.getWeight( v ) ) < 0 )
{
// assign new shortest distance and mark unsettled
shortestDistances.setWeight( v, shortDist );
@@ -87,10 +87,10 @@ final class DefaultTargetSourceSelector<
if ( shortestDistances.alreadyVisited( u ) )
{
- W shortDist = orderedMonoid.append( shortestDistances.getWeight( u ), edge.getWeight() );
+ W shortDist = weightOperations.append( shortestDistances.getWeight( u ), edge.getWeight() );
if ( !shortestDistances.alreadyVisited( v )
- || orderedMonoid.compare( shortDist, shortestDistances.getWeight( v ) ) < 0 )
+ || weightOperations.compare( shortDist, shortestDistances.getWeight( v ) ) < 0 )
{
// TODO it would be nice printing the cycle
throw new NegativeWeightedCycleException( "Graph contains a negative-weight cycle in vertex %s",
@@ -99,7 +99,7 @@ final class DefaultTargetSourceSelector<
}
}
- AllVertexPairsShortestPath<V, WE, W> allVertexPairsShortestPath = new AllVertexPairsShortestPath<V, WE, W>( orderedMonoid );
+ AllVertexPairsShortestPath<V, WE, W> allVertexPairsShortestPath = new AllVertexPairsShortestPath<V, WE, W>( 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=1292272&r1=1292271&r2=1292272&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 Feb 22 13:21:03 2012
@@ -32,7 +32,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>, OM extends OrderedMonoid<W>>
+public interface HeuristicBuilder<V extends Vertex, WE extends WeightedEdge<W>, W, G extends WeightedGraph<V, WE, W>, WO extends OrderedMonoid<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=1292272&r1=1292271&r2=1292272&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 Feb 22 13:21:03 2012
@@ -38,11 +38,11 @@ public interface PathSourceSelector<V ex
/**
* Calculates all vertices shortest paths using the FloydWarshall's algorithm.
*
- * @param <OM>
- * @param orderedMonoid the ordered monoid needed to handle operations on weights
+ * @param <WO> the type of weight operations
+ * @param weightOperations the weight operations needed for the algorithm
* @return a data structure which contains all vertex pairs shortest path.
*/
- <OM extends OrderedMonoid<W>> AllVertexPairsShortestPath<V, WE, W> applyingFloydWarshall( OM orderedMonoid );
+ <WO extends OrderedMonoid<W>> AllVertexPairsShortestPath<V, WE, W> applyingFloydWarshall( WO weightOperations );
/**
* Specifies the shortest path source.
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PredecessorsList.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PredecessorsList.java?rev=1292272&r1=1292271&r2=1292272&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PredecessorsList.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PredecessorsList.java Wed Feb 22 13:21:03 2012
@@ -43,14 +43,14 @@ public final class PredecessorsList<V ex
private final Graph<V, WE> graph;
- private final Monoid<W> monoid;
+ private final Monoid<W> weightOperations;
private final Map<V, V> predecessors = new HashMap<V, V>();
- public PredecessorsList( Graph<V, WE> graph, Monoid<W> monoid )
+ public PredecessorsList( Graph<V, WE> graph, Monoid<W> weightOperations )
{
this.graph = graph;
- this.monoid = monoid;
+ this.weightOperations = weightOperations;
}
/**
@@ -74,7 +74,7 @@ public final class PredecessorsList<V ex
*/
public WeightedPath<V, WE, W> buildPath( V source, V target )
{
- InMemoryWeightedPath<V, WE, W> path = new InMemoryWeightedPath<V, WE, W>( source, target, monoid );
+ InMemoryWeightedPath<V, WE, W> path = new InMemoryWeightedPath<V, WE, W>( source, target, weightOperations );
V vertex = target;
while ( !source.equals( vertex ) )
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/ShortestDistances.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/ShortestDistances.java?rev=1292272&r1=1292271&r2=1292272&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 Feb 22 13:21:03 2012
@@ -38,11 +38,11 @@ final class ShortestDistances<V extends
private final Map<V, W> distances = new HashMap<V, W>();
- private final OrderedMonoid<W> orderedMonoid;
+ private final OrderedMonoid<W> weightOperations;
- public ShortestDistances( OrderedMonoid<W> orderedMonoid )
+ public ShortestDistances( OrderedMonoid<W> weightOperations )
{
- this.orderedMonoid = orderedMonoid;
+ this.weightOperations = weightOperations;
}
/**
@@ -98,7 +98,7 @@ final class ShortestDistances<V extends
{
return -1;
}
- return orderedMonoid.compare( getWeight( left ), getWeight( right ) );
+ return weightOperations.compare( getWeight( left ), getWeight( right ) );
}
}
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=1292272&r1=1292271&r2=1292272&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 Feb 22 13:21:03 2012
@@ -39,19 +39,19 @@ public interface ShortestPathAlgorithmSe
/**
* Calculates the shortest path using the A* algorithm.
*
- * @param <OM>
- * @param orderedMonoid the ordered monoid needed to handle operations on weights
+ * @param <WO> the type of weight operations
+ * @param weightOperations the class responsible for operations on weights
* @return
*/
- <OM extends OrderedMonoid<W>> HeuristicBuilder<V, WE, W, G, OM> applyingAStar( OM orderedMonoid );
+ <WO extends OrderedMonoid<W>> HeuristicBuilder<V, WE, W, G, WO> applyingAStar( WO weightOperations );
/**
- * Calculates the shortest path using the Dijkstra's algorithm.
+ * Calculates the shortest path using Dijkstra's algorithm.
*
- * @param <OM>
- * @param orderedMonoid the ordered monoid needed to handle operations on weights
+ * @param <WO> the type of weight operations
+ * @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
*/
- <OM extends OrderedMonoid<W>> WeightedPath<V, WE, W> applyingDijkstra( OM orderedMonoid );
+ <WO extends OrderedMonoid<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=1292272&r1=1292271&r2=1292272&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 Feb 22 13:21:03 2012
@@ -38,11 +38,11 @@ public interface TargetSourceSelector<V
/**
* Calculates the shortest path using the BellmannFord's algorithm.
*
- * @param <OM>
- * @param orderedMonoid the ordered monoid needed to handle operations on weights
+ * @param <WO> the type of weight operations
+ * @param weightOperations the weight operations needed for the algorithm
* @return a data structure which contains all vertex pairs shortest path.
*/
- <OM extends OrderedMonoid<W>> AllVertexPairsShortestPath<V, WE, W> applyingBelmannFord( OM orderedMonoid );
+ <WO extends OrderedMonoid<W>> AllVertexPairsShortestPath<V, WE, W> 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=1292272&r1=1292271&r2=1292272&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 Feb 22 13:21:03 2012
@@ -63,7 +63,7 @@ final class DefaultSpanningTreeAlgorithm
}
/** {@inheritDoc} */
- public <OM extends OrderedMonoid<W>> SpanningTree<V, WE, W> applyingBoruvkaAlgorithm( OM orderedMonoid )
+ public <WO extends OrderedMonoid<W>> SpanningTree<V, WE, W> applyingBoruvkaAlgorithm( WO weightOperations )
{
/*
* <pre>
@@ -79,21 +79,21 @@ final class DefaultSpanningTreeAlgorithm
* end while
* <pre>
*/
- checkNotNull( orderedMonoid, "The Boruvka algorithm can't be calulated with a null monoid" );
+ checkNotNull( weightOperations, "The Boruvka algorithm cannot be calculated with null weight operations" );
final MutableSpanningTree<V, WE, W> spanningTree =
- new MutableSpanningTree<V, WE, W>( orderedMonoid );
+ new MutableSpanningTree<V, WE, W>( weightOperations );
- final Set<SuperVertex<V, W, WE, G, OM>> components =
- new HashSet<SuperVertex<V, W, WE, G, OM>>( graph.getOrder() );
+ final Set<SuperVertex<V, W, WE, G, WO>> components =
+ new HashSet<SuperVertex<V, W, WE, G, WO>>( graph.getOrder() );
- final Map<V, SuperVertex<V, W, WE, G, OM>> mapping =
- new HashMap<V, SuperVertex<V, W, WE, G, OM>>( graph.getOrder() );
+ final Map<V, SuperVertex<V, W, WE, G, WO>> mapping =
+ new HashMap<V, SuperVertex<V, W, WE, G, WO>>( graph.getOrder() );
for ( V v : graph.getVertices() )
{
// create a super vertex for each vertex
- final SuperVertex<V, W, WE, G, OM> sv =
- new SuperVertex<V, W, WE, G, OM>( v, graph, orderedMonoid );
+ final SuperVertex<V, W, WE, G, WO> sv =
+ new SuperVertex<V, W, WE, G, WO>( v, graph, weightOperations );
components.add( sv );
// add a mapping for each vertex to its corresponding super vertex
mapping.put( v, sv );
@@ -104,7 +104,7 @@ final class DefaultSpanningTreeAlgorithm
while ( components.size() > 1 )
{
List<WE> edges = new LinkedList<WE>();
- for ( SuperVertex<V, W, WE, G, OM> v : components )
+ for ( SuperVertex<V, W, WE, G, WO> v : components )
{
// get the minimum edge for each component to any other component
WE edge = v.getMinimumWeightEdge();
@@ -125,8 +125,8 @@ final class DefaultSpanningTreeAlgorithm
V tail = pair.getTail();
// find the super vertices corresponding to this edge
- SuperVertex<V, W, WE, G, OM> headSuper = mapping.get( head );
- SuperVertex<V, W, WE, G, OM> tailSuper = mapping.get( tail );
+ SuperVertex<V, W, WE, G, WO> headSuper = mapping.get( head );
+ SuperVertex<V, W, WE, G, WO> tailSuper = mapping.get( tail );
// merge them, if they are not the same
if ( headSuper != tailSuper )
@@ -157,14 +157,14 @@ final class DefaultSpanningTreeAlgorithm
/**
* {@inheritDoc}
*/
- public <OM extends OrderedMonoid<W>> SpanningTree<V, WE, W> applyingKruskalAlgorithm( OM orderedMonoid )
+ public <WO extends OrderedMonoid<W>> SpanningTree<V, WE, W> applyingKruskalAlgorithm( WO weightOperations )
{
- checkNotNull( orderedMonoid, "The Kruskal algorithm can't be calulated with a null monoid" );
+ checkNotNull( weightOperations, "The Kruskal algorithm cannot be calculated with null weight operations" );
final Set<V> settledNodes = new HashSet<V>();
final PriorityQueue<WE> orderedEdges =
- new PriorityQueue<WE>( graph.getSize(), new WeightedEdgesComparator<W, WE>( orderedMonoid ) );
+ new PriorityQueue<WE>( graph.getSize(), new WeightedEdgesComparator<W, WE>( weightOperations ) );
for ( WE edge : graph.getEdges() )
{
@@ -173,7 +173,7 @@ final class DefaultSpanningTreeAlgorithm
final DisjointSet<V> disjointSet = new DisjointSet<V>();
- final MutableSpanningTree<V, WE, W> spanningTree = new MutableSpanningTree<V, WE, W>( orderedMonoid );
+ final MutableSpanningTree<V, WE, W> spanningTree = new MutableSpanningTree<V, WE, W>( weightOperations );
// fill the spanning tree with vertices.
for ( V v : graph.getVertices() )
@@ -204,11 +204,11 @@ final class DefaultSpanningTreeAlgorithm
/**
* {@inheritDoc}
*/
- public <OM extends OrderedMonoid<W>> SpanningTree<V, WE, W> applyingPrimAlgorithm( OM orderedMonoid )
+ public <WO extends OrderedMonoid<W>> SpanningTree<V, WE, W> applyingPrimAlgorithm( WO weightOperations )
{
- checkNotNull( orderedMonoid, "The Prim algorithm can't be calulated with a null monoid" );
+ 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, orderedMonoid );
+ final ShortestEdges<V, WE, W> shortestEdges = new ShortestEdges<V, WE, W>( graph, source, weightOperations );
final PriorityQueue<V> unsettledNodes = new PriorityQueue<V>( graph.getOrder(), shortestEdges );
unsettledNodes.add( source );
@@ -227,7 +227,7 @@ final class DefaultSpanningTreeAlgorithm
// if the edge has not been already visited and its weight is
// less then the current Vertex weight
boolean weightLessThanCurrent = !shortestEdges.hasWeight( v )
- || orderedMonoid.compare( edge.getWeight(), shortestEdges.getWeight( v ) ) < 0;
+ || weightOperations.compare( edge.getWeight(), shortestEdges.getWeight( v ) ) < 0;
if ( settledEdges.add( edge ) && weightLessThanCurrent )
{
if ( !unsettledNodes.contains( v ) )
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=1292272&r1=1292271&r2=1292272&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 Feb 22 13:21:03 2012
@@ -80,10 +80,10 @@ public final class DefaultSpanningTreeSo
/**
* {@inheritDoc}
*/
- public <OM extends OrderedMonoid<W>> SpanningTree<V, WE, W> applyingReverseDeleteAlgorithm( OM orderedMonoid )
+ public <WO extends OrderedMonoid<W>> SpanningTree<V, WE, W> applyingReverseDeleteAlgorithm( WO weightOperations )
{
- checkNotNull( orderedMonoid, "The Reverse-Delete algorithm can't be calulated with a null monoid" );
+ checkNotNull( weightOperations, "The Reverse-Delete algorithm cannot be calulated with null weight operations" );
final List<WE> sortedEdge = new ArrayList<WE>();
final List<WE> visitedEdge = new ArrayList<WE>();
@@ -94,7 +94,7 @@ public final class DefaultSpanningTreeSo
sortedEdge.add( we );
}
- sort( sortedEdge, reverseOrder( new WeightedEdgesComparator<W, WE>( orderedMonoid ) ) );
+ sort( sortedEdge, reverseOrder( new WeightedEdgesComparator<W, WE>( weightOperations ) ) );
WeightedGraph<V, WE, W> tmpGraph = new ReverseDeleteGraph<V, WE, W>( graph, sortedEdge, visitedEdge );
@@ -107,7 +107,7 @@ public final class DefaultSpanningTreeSo
try
{
- findShortestPath( tmpGraph ).from( vertices.getHead() ).to( vertices.getTail() ).applyingDijkstra( orderedMonoid );
+ findShortestPath( tmpGraph ).from( vertices.getHead() ).to( vertices.getTail() ).applyingDijkstra( weightOperations );
}
catch ( PathNotFoundException ex )
{
@@ -116,7 +116,7 @@ public final class DefaultSpanningTreeSo
}
}
- final MutableSpanningTree<V, WE, W> res = new MutableSpanningTree<V, WE, W>( orderedMonoid );
+ final MutableSpanningTree<V, WE, W> res = new MutableSpanningTree<V, WE, W>( weightOperations );
for ( V v : graph.getVertices() )
{
res.addVertex( v );
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=1292272&r1=1292271&r2=1292272&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 Feb 22 13:21:03 2012
@@ -47,17 +47,17 @@ final class ShortestEdges<V extends Vert
private final Map<V, WE> predecessors = new HashMap<V, WE>();
- private final OrderedMonoid<W> orderedMonoid;
+ private final OrderedMonoid<W> weightOperations;
private final Graph<V, WE> graph;
private final V source;
- public ShortestEdges(Graph<V, WE> graph, V source, OrderedMonoid<W> orderedMonoid )
+ public ShortestEdges(Graph<V, WE> graph, V source, OrderedMonoid<W> weightOperations )
{
this.graph = graph;
this.source = source;
- this.orderedMonoid = orderedMonoid;
+ this.weightOperations = weightOperations;
}
/**
@@ -78,7 +78,7 @@ final class ShortestEdges<V extends Vert
*/
public SpanningTree<V, WE, W> createSpanningTree()
{
- MutableSpanningTree<V, WE, W> spanningTree = new MutableSpanningTree<V, WE, W>( orderedMonoid );
+ MutableSpanningTree<V, WE, W> spanningTree = new MutableSpanningTree<V, WE, W>( weightOperations );
for ( WE edge : this.predecessors.values() )
{
@@ -132,7 +132,7 @@ final class ShortestEdges<V extends Vert
{
if ( source.equals( vertex ) )
{
- return orderedMonoid.zero();
+ return weightOperations.zero();
}
WE edge = predecessors.get( vertex );
@@ -173,7 +173,7 @@ final class ShortestEdges<V extends Vert
{
return -1;
}
- return orderedMonoid.compare( getWeight( left ), getWeight( right ) );
+ return weightOperations.compare( getWeight( left ), getWeight( right ) );
}
/**
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=1292272&r1=1292271&r2=1292272&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 Feb 22 13:21:03 2012
@@ -39,25 +39,28 @@ public interface SpanningTreeAlgorithmSe
/**
* Applies the <a href="http://en.wikipedia.org/wiki/Bor%C5%AFvka's_algorithm">Boruvka</a>'s algorithm.
*
- * @param orderedMonoid the graph weights monoid
+ * @param <WO> the type of weight operations
+ * @param weightOperations the class responsible for operations on weights
* @return the calculated spanning tree
*/
- <OM extends OrderedMonoid<W>> SpanningTree<V, WE, W> applyingBoruvkaAlgorithm( OM orderedMonoid );
+ <WO extends OrderedMonoid<W>> SpanningTree<V, WE, W> applyingBoruvkaAlgorithm( WO weightOperations );
/**
* Applies the <a href="http://en.wikipedia.org/wiki/Kruskal%27s_algorithm">Kruskal</a>'s algorithm.
*
- * @param orderedMonoid the graph weights monoid
+ * @param <WO> the type of weight operations
+ * @param weightOperations the class responsible for operations on weights
* @return the calculated spanning tree
*/
- <OM extends OrderedMonoid<W>> SpanningTree<V, WE, W> applyingKruskalAlgorithm( OM orderedMonoid );
+ <WO extends OrderedMonoid<W>> SpanningTree<V, WE, W> applyingKruskalAlgorithm( WO weightOperations );
/**
* Applies the <a href="http://en.wikipedia.org/wiki/Prim%27s_algorithm">Prim</a>'s algorithm.
*
- * @param orderedMonoid the graph weights monoid
+ * @param <WO> the type of weight operations
+ * @param weightOperations the class responsible for operations on weights
* @return the calculated spanning tree
*/
- <OM extends OrderedMonoid<W>> SpanningTree<V, WE, W> applyingPrimAlgorithm( OM orderedMonoid );
+ <WO extends OrderedMonoid<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=1292272&r1=1292271&r2=1292272&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 Feb 22 13:21:03 2012
@@ -67,9 +67,9 @@ public interface SpanningTreeSourceSelec
* return edges[] E
* </pre>
*
- * @param orderedMonoid the graph weights monoid
+ * @param weightOperations the weight operations
* @return the calculated spanning tree
*/
- <OM extends OrderedMonoid<W>> SpanningTree<V, WE, W> applyingReverseDeleteAlgorithm( OM orderedMonoid );
+ <WO extends OrderedMonoid<W>> SpanningTree<V, WE, W> applyingReverseDeleteAlgorithm( WO weightOperations );
}
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/SuperVertex.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/SuperVertex.java?rev=1292272&r1=1292271&r2=1292272&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/SuperVertex.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/SuperVertex.java Wed Feb 22 13:21:03 2012
@@ -19,6 +19,7 @@ package org.apache.commons.graph.spannin
* under the License.
*/
+import java.util.Comparator;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
@@ -28,7 +29,6 @@ import org.apache.commons.graph.Graph;
import org.apache.commons.graph.Vertex;
import org.apache.commons.graph.VertexPair;
import org.apache.commons.graph.WeightedEdge;
-import org.apache.commons.graph.weight.OrderedMonoid;
/**
* A {@link SuperVertex} is a collection of {@link Vertex} objects and is only
@@ -38,9 +38,9 @@ import org.apache.commons.graph.weight.O
* @param <W> the weight type
* @param <WE> the Graph weighted edges type
* @param <G> the input Graph type
- * @param <OM> the Comparator for weighted edges
+ * @param <WC> the weight operations
*/
-class SuperVertex<V extends Vertex, W, WE extends WeightedEdge<W>, G extends Graph<V, WE>, OM extends OrderedMonoid<W>>
+class SuperVertex<V extends Vertex, W, WE extends WeightedEdge<W>, G extends Graph<V, WE>, WC extends Comparator<W>>
implements Iterable<V> {
/** The reference to the graph. */
@@ -58,15 +58,15 @@ class SuperVertex<V extends Vertex, W, W
*
* @param source the start vertex
* @param graph the underlying graph
- * @param orderedMonoid the comparator used to sort the weighted edges
+ * @param weightComparator the comparator used to sort the weighted edges
*/
- public SuperVertex( final V source, final G graph, final OM orderedMonoid ) {
+ public SuperVertex( final V source, final G graph, final WC weightComparator ) {
this.graph = graph;
vertices = new HashSet<V>();
vertices.add( source );
- orderedEdges = new TreeSet<WE>( new WeightedEdgesComparator<W, WE>( orderedMonoid ) );
+ orderedEdges = new TreeSet<WE>( new WeightedEdgesComparator<W, WE>( weightComparator ) );
// add all edges for this vertex to the sorted set
for ( V w : graph.getConnectedVertices( source )) {
@@ -87,7 +87,7 @@ class SuperVertex<V extends Vertex, W, W
*
* @param other the {@link SuperVertex} to be merged into this
*/
- public void merge( final SuperVertex<V, W, WE, G, OM> other ) {
+ public void merge( final SuperVertex<V, W, WE, G, WC> other ) {
for ( V v : other.vertices ) {
vertices.add(v);
}
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/WeightedEdgesComparator.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/WeightedEdgesComparator.java?rev=1292272&r1=1292271&r2=1292272&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/WeightedEdgesComparator.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/WeightedEdgesComparator.java Wed Feb 22 13:21:03 2012
@@ -20,7 +20,6 @@ package org.apache.commons.graph.spannin
*/
import org.apache.commons.graph.WeightedEdge;
-import org.apache.commons.graph.weight.OrderedMonoid;
import java.util.Comparator;
@@ -33,16 +32,16 @@ public class WeightedEdgesComparator<W,
implements Comparator<WE>
{
- private final OrderedMonoid<W> orderedMonoid;
+ private final Comparator<W> weightComparator;
- public WeightedEdgesComparator( OrderedMonoid<W> orderedMonoid )
+ public WeightedEdgesComparator( Comparator<W> weightComparator )
{
- this.orderedMonoid = orderedMonoid;
+ this.weightComparator = weightComparator;
}
public int compare( WE o1, WE o2 )
{
- return orderedMonoid.compare( o1.getWeight(), o2.getWeight() );
+ return weightComparator.compare( o1.getWeight(), o2.getWeight() );
}
}
Copied: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/BigDecimalWeightBaseOperations.java (from r1290988, commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/BigDecimalWeight.java)
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/BigDecimalWeightBaseOperations.java?p2=commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/BigDecimalWeightBaseOperations.java&p1=commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/BigDecimalWeight.java&r1=1290988&r2=1292272&rev=1292272&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/BigDecimalWeight.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/BigDecimalWeightBaseOperations.java Wed Feb 22 13:21:03 2012
@@ -26,10 +26,10 @@ import java.math.BigDecimal;
import org.apache.commons.graph.weight.OrderedMonoid;
/**
- * An {@link BigBigDecimalWeight} provides operations and properties
+ * The class {@link BigDecimalWeightBaseOperations} provides operations and properties
* for weights of type {@link BigDecimal}.
*/
-public class BigDecimalWeight
+public class BigDecimalWeightBaseOperations
implements OrderedMonoid<BigDecimal>
{
Copied: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/BigIntegerWeightBaseOperations.java (from r1290988, commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/BigIntegerWeight.java)
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/BigIntegerWeightBaseOperations.java?p2=commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/BigIntegerWeightBaseOperations.java&p1=commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/BigIntegerWeight.java&r1=1290988&r2=1292272&rev=1292272&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/BigIntegerWeight.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/BigIntegerWeightBaseOperations.java Wed Feb 22 13:21:03 2012
@@ -26,10 +26,10 @@ import java.math.BigInteger;
import org.apache.commons.graph.weight.OrderedMonoid;
/**
- * An {@link BigIntegerWeight} provides operations and properties
+ * The class {@link BigIntegerWeightBaseOperations} provides operations and properties
* for weights of type {@link BigInteger}.
*/
-public class BigIntegerWeight
+public class BigIntegerWeightBaseOperations
implements OrderedMonoid<BigInteger>
{
Copied: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/DoubleWeightBaseOperations.java (from r1290988, commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/DoubleWeight.java)
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/DoubleWeightBaseOperations.java?p2=commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/DoubleWeightBaseOperations.java&p1=commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/DoubleWeight.java&r1=1290988&r2=1292272&rev=1292272&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/DoubleWeight.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/DoubleWeightBaseOperations.java Wed Feb 22 13:21:03 2012
@@ -22,10 +22,10 @@ package org.apache.commons.graph.weight.
import org.apache.commons.graph.weight.OrderedMonoid;
/**
- * A {@link DoubleWeight} provides operations and properties
+ * The class {@link DoubleWeightBaseOperations} provides operations and properties
* for weights of type {@link Double}.
*/
-public class DoubleWeight
+public class DoubleWeightBaseOperations
implements OrderedMonoid<Double>
{
Copied: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/FloatWeightBaseOperations.java (from r1290988, commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/FloatWeight.java)
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/FloatWeightBaseOperations.java?p2=commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/FloatWeightBaseOperations.java&p1=commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/FloatWeight.java&r1=1290988&r2=1292272&rev=1292272&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/FloatWeight.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/FloatWeightBaseOperations.java Wed Feb 22 13:21:03 2012
@@ -22,10 +22,10 @@ package org.apache.commons.graph.weight.
import org.apache.commons.graph.weight.OrderedMonoid;
/**
- * A {@link FloatWeight} provides operations and properties
+ * The class {@link FloatWeightBaseOperations} provides operations and properties
* for weights of type {@link Float}.
*/
-public class FloatWeight
+public class FloatWeightBaseOperations
implements OrderedMonoid<Float>
{
Copied: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/IntegerWeightBaseOperations.java (from r1290988, commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/IntegerWeight.java)
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/IntegerWeightBaseOperations.java?p2=commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/IntegerWeightBaseOperations.java&p1=commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/IntegerWeight.java&r1=1290988&r2=1292272&rev=1292272&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/IntegerWeight.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/IntegerWeightBaseOperations.java Wed Feb 22 13:21:03 2012
@@ -22,10 +22,10 @@ package org.apache.commons.graph.weight.
import org.apache.commons.graph.weight.OrderedMonoid;
/**
- * An {@link IntegerWeight} provides operations and properties
+ * The class {@link IntegerWeightBaseOperations} provides operations and properties
* for weights of type {@link Integer}.
*/
-public class IntegerWeight
+public class IntegerWeightBaseOperations
implements OrderedMonoid<Integer>
{
Copied: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/LongWeightBaseOperations.java (from r1290988, commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/LongWeight.java)
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/LongWeightBaseOperations.java?p2=commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/LongWeightBaseOperations.java&p1=commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/LongWeight.java&r1=1290988&r2=1292272&rev=1292272&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/LongWeight.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/LongWeightBaseOperations.java Wed Feb 22 13:21:03 2012
@@ -22,10 +22,10 @@ package org.apache.commons.graph.weight.
import org.apache.commons.graph.weight.OrderedMonoid;
/**
- * A {@link LongWeight} provides operations and properties
+ * The class {@link LongWeightBaseOperations} provides operations and properties
* for weights of type {@link Long}.
*/
-public class LongWeight
+public class LongWeightBaseOperations
implements OrderedMonoid<Long>
{
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/package-info.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/package-info.java?rev=1292272&r1=1292271&r2=1292272&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/package-info.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/package-info.java Wed Feb 22 13:21:03 2012
@@ -1,5 +1,5 @@
/**
- * Primitive weight implementations.
+ * Implementations of base operations on primitive types of weights.
*/
package org.apache.commons.graph.weight.primitive;
Modified: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/flow/EdmondsKarpTestCase.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/flow/EdmondsKarpTestCase.java?rev=1292272&r1=1292271&r2=1292272&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/flow/EdmondsKarpTestCase.java (original)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/flow/EdmondsKarpTestCase.java Wed Feb 22 13:21:03 2012
@@ -29,7 +29,7 @@ import org.apache.commons.graph.builder.
import org.apache.commons.graph.model.BaseLabeledVertex;
import org.apache.commons.graph.model.BaseLabeledWeightedEdge;
import org.apache.commons.graph.model.DirectedMutableWeightedGraph;
-import org.apache.commons.graph.weight.primitive.IntegerWeight;
+import org.apache.commons.graph.weight.primitive.IntegerWeightBaseOperations;
import org.junit.Test;
/**
@@ -47,7 +47,7 @@ public class EdmondsKarpTestCase
final BaseLabeledVertex g = new BaseLabeledVertex( "G" );
// actual max flow
- findMaxFlow( (DirectedMutableWeightedGraph<Vertex, WeightedEdge<Integer>, Integer>) null ).from( a ).to( g ).applyingEdmondsKarp( new IntegerWeight() );
+ findMaxFlow( (DirectedMutableWeightedGraph<Vertex, WeightedEdge<Integer>, Integer>) null ).from( a ).to( g ).applyingEdmondsKarp( new IntegerWeightBaseOperations() );
}
@Test( expected = NullPointerException.class )
@@ -68,7 +68,7 @@ public class EdmondsKarpTestCase
} );
// actual max flow
- findMaxFlow( graph ).from( a ).to( g ).applyingEdmondsKarp( new IntegerWeight() );
+ findMaxFlow( graph ).from( a ).to( g ).applyingEdmondsKarp( new IntegerWeightBaseOperations() );
}
@Test
@@ -101,7 +101,7 @@ public class EdmondsKarpTestCase
final Integer expected = 0;
// actual max flow
- Integer actual = findMaxFlow( graph ).from( a ).to( g ).applyingEdmondsKarp( new IntegerWeight() );
+ Integer actual = findMaxFlow( graph ).from( a ).to( g ).applyingEdmondsKarp( new IntegerWeightBaseOperations() );
assertEquals( actual, expected );
}
@@ -145,7 +145,7 @@ public class EdmondsKarpTestCase
final Integer expected = 5;
// actual max flow
- Integer actual = findMaxFlow( graph ).from( a ).to( g ).applyingEdmondsKarp( new IntegerWeight() );
+ Integer actual = findMaxFlow( graph ).from( a ).to( g ).applyingEdmondsKarp( new IntegerWeightBaseOperations() );
assertEquals( actual, expected );
}
Modified: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/flow/FordFulkersonTestCase.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/flow/FordFulkersonTestCase.java?rev=1292272&r1=1292271&r2=1292272&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/flow/FordFulkersonTestCase.java (original)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/flow/FordFulkersonTestCase.java Wed Feb 22 13:21:03 2012
@@ -31,7 +31,7 @@ import org.apache.commons.graph.builder.
import org.apache.commons.graph.model.BaseLabeledVertex;
import org.apache.commons.graph.model.BaseLabeledWeightedEdge;
import org.apache.commons.graph.model.DirectedMutableWeightedGraph;
-import org.apache.commons.graph.weight.primitive.IntegerWeight;
+import org.apache.commons.graph.weight.primitive.IntegerWeightBaseOperations;
import org.junit.Test;
/**
@@ -48,13 +48,13 @@ public final class FordFulkersonTestCase
final BaseLabeledVertex a = new BaseLabeledVertex( "A" );
final BaseLabeledVertex d = new BaseLabeledVertex( "D" );
- findMaxFlow( (DirectedMutableWeightedGraph<Vertex, WeightedEdge<Integer>, Integer>) null ).from( a ).to( d ).applyingFordFulkerson( new IntegerWeight() );
+ findMaxFlow( (DirectedMutableWeightedGraph<Vertex, WeightedEdge<Integer>, Integer>) null ).from( a ).to( d ).applyingFordFulkerson( new IntegerWeightBaseOperations() );
}
@Test(expected=NullPointerException.class)
public void testNullGraphAndVertices()
{
- findMaxFlow( (DirectedMutableWeightedGraph<Vertex, WeightedEdge<Integer>, Integer>) null ).from( null ).to( null ).applyingFordFulkerson( new IntegerWeight() );
+ findMaxFlow( (DirectedMutableWeightedGraph<Vertex, WeightedEdge<Integer>, Integer>) null ).from( null ).to( null ).applyingFordFulkerson( new IntegerWeightBaseOperations() );
}
@Test
@@ -83,7 +83,7 @@ public final class FordFulkersonTestCase
final Integer expected = 0;
// actual max flow
- Integer actual = findMaxFlow( graph ).from( a ).to( d ).applyingFordFulkerson( new IntegerWeight() );
+ Integer actual = findMaxFlow( graph ).from( a ).to( d ).applyingFordFulkerson( new IntegerWeightBaseOperations() );
assertEquals( actual, expected );
}
@@ -115,7 +115,7 @@ public final class FordFulkersonTestCase
final Integer expected = 0;
// actual max flow
- Integer actual = findMaxFlow( graph ).from( a ).to( d ).applyingFordFulkerson( new IntegerWeight() );
+ Integer actual = findMaxFlow( graph ).from( a ).to( d ).applyingFordFulkerson( new IntegerWeightBaseOperations() );
assertEquals( actual, expected );
}
@@ -143,7 +143,7 @@ public final class FordFulkersonTestCase
}
// actual max flow
- findMaxFlow( graph ).from( null ).to( null ).applyingFordFulkerson( new IntegerWeight() );
+ findMaxFlow( graph ).from( null ).to( null ).applyingFordFulkerson( new IntegerWeightBaseOperations() );
}
@Test
@@ -177,7 +177,7 @@ public final class FordFulkersonTestCase
final Integer expected = 2000;
// actual max flow
- Integer actual = findMaxFlow( graph ).from( a ).to( d ).applyingFordFulkerson( new IntegerWeight() );
+ Integer actual = findMaxFlow( graph ).from( a ).to( d ).applyingFordFulkerson( new IntegerWeightBaseOperations() );
assertEquals( actual, expected );
}
Modified: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/AStarTestCase.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/AStarTestCase.java?rev=1292272&r1=1292271&r2=1292272&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/AStarTestCase.java (original)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/AStarTestCase.java Wed Feb 22 13:21:03 2012
@@ -34,7 +34,7 @@ import org.apache.commons.graph.model.Ba
import org.apache.commons.graph.model.BaseLabeledWeightedEdge;
import org.apache.commons.graph.model.InMemoryWeightedPath;
import org.apache.commons.graph.model.UndirectedMutableWeightedGraph;
-import org.apache.commons.graph.weight.primitive.DoubleWeight;
+import org.apache.commons.graph.weight.primitive.DoubleWeightBaseOperations;
import org.junit.Test;
public final class AStarTestCase
@@ -43,7 +43,7 @@ public final class AStarTestCase
@Test( expected = NullPointerException.class )
public void testNullGraph()
{
- findShortestPath( (WeightedGraph<Vertex, WeightedEdge<Double>, Double>) null ).from( null ).to( null ).applyingAStar( new DoubleWeight() ).withHeuristic( null );
+ findShortestPath( (WeightedGraph<Vertex, WeightedEdge<Double>, Double>) null ).from( null ).to( null ).applyingAStar( new DoubleWeightBaseOperations() ).withHeuristic( null );
}
@Test( expected = NullPointerException.class )
@@ -52,7 +52,7 @@ public final class AStarTestCase
UndirectedMutableWeightedGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> graph =
new UndirectedMutableWeightedGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double>();
- findShortestPath( graph ).from( null ).to( null ).applyingAStar( new DoubleWeight() ).withHeuristic( null );
+ findShortestPath( graph ).from( null ).to( null ).applyingAStar( new DoubleWeightBaseOperations() ).withHeuristic( null );
}
@Test( expected = NullPointerException.class )
@@ -61,7 +61,7 @@ public final class AStarTestCase
UndirectedMutableWeightedGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> graph =
new UndirectedMutableWeightedGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double>();
- findShortestPath( graph ).from( new BaseLabeledVertex( "a" ) ).to( new BaseLabeledVertex( "b" ) ).applyingAStar( new DoubleWeight() ).withHeuristic( null );
+ findShortestPath( graph ).from( new BaseLabeledVertex( "a" ) ).to( new BaseLabeledVertex( "b" ) ).applyingAStar( new DoubleWeightBaseOperations() ).withHeuristic( null );
}
@Test( expected = NullPointerException.class )
@@ -121,7 +121,7 @@ public final class AStarTestCase
};
- findShortestPath( graph ).from( a ).to( b ).applyingAStar( new DoubleWeight() ).withHeuristic( heuristic );
+ findShortestPath( graph ).from( a ).to( b ).applyingAStar( new DoubleWeightBaseOperations() ).withHeuristic( heuristic );
}
/**
@@ -186,7 +186,7 @@ public final class AStarTestCase
InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> expected =
new InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double>( start, goal,
- new DoubleWeight() );
+ new DoubleWeightBaseOperations() );
expected.addConnectionInTail( start, new BaseLabeledWeightedEdge<Double>( "start <-> a", 1.5D ), a );
expected.addConnectionInTail( a, new BaseLabeledWeightedEdge<Double>( "a <-> b", 2D ), b );
@@ -196,7 +196,7 @@ public final class AStarTestCase
// actual path
Path<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>> actual =
- findShortestPath( graph ).from( start ).to( goal ).applyingAStar( new DoubleWeight() ).withHeuristic( heuristic );
+ findShortestPath( graph ).from( start ).to( goal ).applyingAStar( new DoubleWeightBaseOperations() ).withHeuristic( heuristic );
// assert!
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=1292272&r1=1292271&r2=1292272&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 Feb 22 13:21:03 2012
@@ -32,7 +32,7 @@ import org.apache.commons.graph.model.Ba
import org.apache.commons.graph.model.DirectedMutableWeightedGraph;
import org.apache.commons.graph.model.InMemoryWeightedPath;
import org.apache.commons.graph.model.UndirectedMutableWeightedGraph;
-import org.apache.commons.graph.weight.primitive.DoubleWeight;
+import org.apache.commons.graph.weight.primitive.DoubleWeightBaseOperations;
import org.junit.Test;
public final class BellmannFordTestCase
@@ -42,7 +42,7 @@ public final class BellmannFordTestCase
public void testNullGraph()
{
// the actual weighted path
- findShortestPath( (WeightedGraph<Vertex, WeightedEdge<Double>, Double>) null ).from( null ).applyingBelmannFord( new DoubleWeight() );
+ findShortestPath( (WeightedGraph<Vertex, WeightedEdge<Double>, Double>) null ).from( null ).applyingBelmannFord( new DoubleWeightBaseOperations() );
}
@Test( expected = NullPointerException.class )
@@ -51,7 +51,7 @@ public final class BellmannFordTestCase
UndirectedMutableWeightedGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> graph =
new UndirectedMutableWeightedGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double>();
- findShortestPath( graph ).from( null ).applyingBelmannFord( new DoubleWeight() );
+ findShortestPath( graph ).from( null ).applyingBelmannFord( new DoubleWeightBaseOperations() );
}
@Test( expected = NullPointerException.class )
@@ -95,7 +95,7 @@ public final class BellmannFordTestCase
graph.addVertex( a );
graph.addVertex( b );
- allVertexPairsShortestPath = findShortestPath( graph ).from( a ).applyingBelmannFord( new DoubleWeight() );
+ allVertexPairsShortestPath = findShortestPath( graph ).from( a ).applyingBelmannFord( new DoubleWeightBaseOperations() );
}
catch ( PathNotFoundException e )
{
@@ -144,13 +144,13 @@ public final class BellmannFordTestCase
// the expected weighted path
InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> expected =
- new InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double>( one, three, new DoubleWeight() );
+ new InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double>( one, three, new DoubleWeightBaseOperations() );
expected.addConnectionInTail( one, new BaseLabeledWeightedEdge<Double>( "1 -> 4", 7D ), four );
expected.addConnectionInTail( four, new BaseLabeledWeightedEdge<Double>( "4 -> 3", -3D ), three );
// the actual weighted path
AllVertexPairsShortestPath<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> allVertexPairsShortestPath =
- findShortestPath( graph ).from( one ).applyingBelmannFord( new DoubleWeight() );
+ findShortestPath( graph ).from( one ).applyingBelmannFord( new DoubleWeightBaseOperations() );
WeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> actual =
allVertexPairsShortestPath.findShortestPath( one, three );