You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by si...@apache.org on 2012/03/07 22:32:59 UTC
svn commit: r1298135 - in
/commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph:
./ shortestpath/
Author: simonetripodi
Date: Wed Mar 7 21:32:58 2012
New Revision: 1298135
URL: http://svn.apache.org/viewvc?rev=1298135&view=rev
Log:
renamed WeightedEdges to a general Mapper (same interface will be reused for algorithms where weights will be associated to vertices)
Added:
commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/Mapper.java
- copied, changed from r1298048, commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/WeightedEdges.java
commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/shortestpath/PathWeightedEdgesBuilder.java
- copied, changed from r1298048, commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/shortestpath/WeightedEdgesSelector.java
Removed:
commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/WeightedEdges.java
commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/shortestpath/WeightedEdgesSelector.java
Modified:
commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/CommonsGraph.java
commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/shortestpath/DefaultHeuristicBuilder.java
commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/shortestpath/DefaultPathSourceSelector.java
commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/shortestpath/DefaultShortestPathAlgorithmSelector.java
commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/shortestpath/DefaultTargetSourceSelector.java
commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/shortestpath/DefaultWeightedEdgesSelector.java
Modified: commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/CommonsGraph.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/CommonsGraph.java?rev=1298135&r1=1298134&r2=1298135&view=diff
==============================================================================
--- commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/CommonsGraph.java (original)
+++ commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/CommonsGraph.java Wed Mar 7 21:32:58 2012
@@ -44,7 +44,7 @@ import org.apache.commons.graph.model.Un
import org.apache.commons.graph.scc.DefaultSccAlgorithmSelector;
import org.apache.commons.graph.scc.SccAlgorithmSelector;
import org.apache.commons.graph.shortestpath.DefaultWeightedEdgesSelector;
-import org.apache.commons.graph.shortestpath.WeightedEdgesSelector;
+import org.apache.commons.graph.shortestpath.PathWeightedEdgesBuilder;
import org.apache.commons.graph.spanning.DefaultSpanningTreeSourceSelector;
import org.apache.commons.graph.visit.DefaultVisitSourceSelector;
import org.apache.commons.graph.visit.VisitSourceSelector;
@@ -88,7 +88,7 @@ public final class CommonsGraph<V, E, G
* @param graph
* @return
*/
- public static <V, WE, W, G extends Graph<V, WE> SpanningTreeSourceSelector<V, W, WE, G> minimumSpanningTree( G graph )
+ public static <V, WE, W, G extends Graph<V, WE>> SpanningTreeSourceSelector<V, W, WE, G> minimumSpanningTree( G graph )
{
graph = checkNotNull( graph, "Minimum spanning tree can not be calculated on null graph" );
return new DefaultSpanningTreeSourceSelector<V, W, WE, G>( graph );
@@ -103,7 +103,7 @@ public final class CommonsGraph<V, E, G
* @param <G>
* @param graph
*/
- public static <V, WE, G extends Graph<V, WE>> WeightedEdgesSelector<V, WE, G> findShortestPath( G graph )
+ public static <V, WE, G extends Graph<V, WE>> PathWeightedEdgesBuilder<V, WE, G> findShortestPath( G graph )
{
graph = checkNotNull( graph, "Shortest path can not be calculated on null graph" );
return new DefaultWeightedEdgesSelector<V, WE, G>( graph );
Copied: commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/Mapper.java (from r1298048, commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/WeightedEdges.java)
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/Mapper.java?p2=commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/Mapper.java&p1=commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/WeightedEdges.java&r1=1298048&r2=1298135&rev=1298135&view=diff
==============================================================================
--- commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/WeightedEdges.java (original)
+++ commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/Mapper.java Wed Mar 7 21:32:58 2012
@@ -19,10 +19,9 @@ package org.apache.commons.graph;
* under the License.
*/
-// TODO find a better name
-public interface WeightedEdges<E, W>
+public interface Mapper<I, O>
{
- W getWeightForEdge( E edge );
+ O map( I input );
}
Modified: commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/shortestpath/DefaultHeuristicBuilder.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/shortestpath/DefaultHeuristicBuilder.java?rev=1298135&r1=1298134&r2=1298135&view=diff
==============================================================================
--- commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/shortestpath/DefaultHeuristicBuilder.java (original)
+++ commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/shortestpath/DefaultHeuristicBuilder.java Wed Mar 7 21:32:58 2012
@@ -27,7 +27,7 @@ import java.util.Set;
import org.apache.commons.graph.DirectedGraph;
import org.apache.commons.graph.Graph;
-import org.apache.commons.graph.WeightedEdges;
+import org.apache.commons.graph.Mapper;
import org.apache.commons.graph.WeightedPath;
import org.apache.commons.graph.collections.FibonacciHeap;
import org.apache.commons.graph.weight.OrderedMonoid;
@@ -38,7 +38,7 @@ final class DefaultHeuristicBuilder<V, W
private final G graph;
- private final WeightedEdges<WE, W> weightedEdges;
+ private final Mapper<WE, W> weightedEdges;
private final V start;
@@ -46,7 +46,7 @@ final class DefaultHeuristicBuilder<V, W
private final WO weightOperations;
- public DefaultHeuristicBuilder( G graph, WeightedEdges<WE, W> weightedEdges, V source, V target, WO weightOperations )
+ public DefaultHeuristicBuilder( G graph, Mapper<WE, W> weightedEdges, V source, V target, WO weightOperations )
{
this.graph = graph;
this.weightedEdges = weightedEdges;
@@ -102,7 +102,7 @@ final class DefaultHeuristicBuilder<V, W
{
WE edge = graph.getEdge( current, v );
// note that the weight of current can never be undefined
- W tentativeGScore = weightOperations.append( gScores.getWeight( current ), weightedEdges.getWeightForEdge( edge ) );
+ W tentativeGScore = weightOperations.append( gScores.getWeight( current ), weightedEdges.map( edge ) );
// if the first condition fails, v has already been visited (its weight is defined)
if ( openSet.add( v ) || weightOperations.compare( tentativeGScore, gScores.getWeight( v ) ) < 0 )
Modified: commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/shortestpath/DefaultPathSourceSelector.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/shortestpath/DefaultPathSourceSelector.java?rev=1298135&r1=1298134&r2=1298135&view=diff
==============================================================================
--- commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/shortestpath/DefaultPathSourceSelector.java (original)
+++ commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/shortestpath/DefaultPathSourceSelector.java Wed Mar 7 21:32:58 2012
@@ -27,7 +27,7 @@ import java.util.Map;
import org.apache.commons.graph.Graph;
import org.apache.commons.graph.UndirectedGraph;
import org.apache.commons.graph.VertexPair;
-import org.apache.commons.graph.WeightedEdges;
+import org.apache.commons.graph.Mapper;
import org.apache.commons.graph.WeightedPath;
import org.apache.commons.graph.weight.OrderedMonoid;
@@ -37,9 +37,9 @@ final class DefaultPathSourceSelector<V,
private final G graph;
- private final WeightedEdges<WE, W> weightedEdges;
+ private final Mapper<WE, W> weightedEdges;
- public DefaultPathSourceSelector( G graph, WeightedEdges<WE, W> weightedEdges )
+ public DefaultPathSourceSelector( G graph, Mapper<WE, W> weightedEdges )
{
this.graph = graph;
this.weightedEdges = weightedEdges;
@@ -59,11 +59,11 @@ final class DefaultPathSourceSelector<V,
for ( WE we : graph.getEdges() )
{
VertexPair<V> vertexPair = graph.getVertices( we );
- shortestPaths.addShortestDistance( vertexPair.getHead(), vertexPair.getTail(), weightedEdges.getWeightForEdge( we ) );
+ shortestPaths.addShortestDistance( vertexPair.getHead(), vertexPair.getTail(), weightedEdges.map( we ) );
if ( graph instanceof UndirectedGraph )
{
- shortestPaths.addShortestDistance( vertexPair.getTail(), vertexPair.getHead(), weightedEdges.getWeightForEdge( we ) );
+ shortestPaths.addShortestDistance( vertexPair.getTail(), vertexPair.getHead(), weightedEdges.map( we ) );
}
}
Modified: commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/shortestpath/DefaultShortestPathAlgorithmSelector.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/shortestpath/DefaultShortestPathAlgorithmSelector.java?rev=1298135&r1=1298134&r2=1298135&view=diff
==============================================================================
--- commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/shortestpath/DefaultShortestPathAlgorithmSelector.java (original)
+++ commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/shortestpath/DefaultShortestPathAlgorithmSelector.java Wed Mar 7 21:32:58 2012
@@ -26,7 +26,7 @@ import java.util.Queue;
import java.util.Set;
import org.apache.commons.graph.Graph;
-import org.apache.commons.graph.WeightedEdges;
+import org.apache.commons.graph.Mapper;
import org.apache.commons.graph.WeightedPath;
import org.apache.commons.graph.collections.FibonacciHeap;
import org.apache.commons.graph.weight.OrderedMonoid;
@@ -37,13 +37,13 @@ final class DefaultShortestPathAlgorithm
private final G graph;
- private final WeightedEdges<WE, W> weightedEdges;
+ private final Mapper<WE, W> weightedEdges;
private final V source;
private final V target;
- public DefaultShortestPathAlgorithmSelector( G graph, WeightedEdges<WE, W> weightedEdges, V source, V target )
+ public DefaultShortestPathAlgorithmSelector( G graph, Mapper<WE, W> weightedEdges, V source, V target )
{
this.graph = graph;
this.weightedEdges = weightedEdges;
@@ -98,7 +98,7 @@ final class DefaultShortestPathAlgorithm
WE edge = graph.getEdge( vertex, v );
if ( shortestDistances.alreadyVisited( vertex ) )
{
- W shortDist = weightOperations.append( shortestDistances.getWeight( vertex ), weightedEdges.getWeightForEdge( edge ) );
+ W shortDist = weightOperations.append( shortestDistances.getWeight( vertex ), weightedEdges.map( edge ) );
if ( !shortestDistances.alreadyVisited( v )
|| weightOperations.compare( shortDist, shortestDistances.getWeight( v ) ) < 0 )
Modified: commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/shortestpath/DefaultTargetSourceSelector.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/shortestpath/DefaultTargetSourceSelector.java?rev=1298135&r1=1298134&r2=1298135&view=diff
==============================================================================
--- commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/shortestpath/DefaultTargetSourceSelector.java (original)
+++ commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/shortestpath/DefaultTargetSourceSelector.java Wed Mar 7 21:32:58 2012
@@ -23,7 +23,7 @@ import static org.apache.commons.graph.u
import org.apache.commons.graph.Graph;
import org.apache.commons.graph.VertexPair;
-import org.apache.commons.graph.WeightedEdges;
+import org.apache.commons.graph.Mapper;
import org.apache.commons.graph.WeightedPath;
import org.apache.commons.graph.weight.OrderedMonoid;
@@ -33,11 +33,11 @@ final class DefaultTargetSourceSelector<
private final G graph;
- private final WeightedEdges<WE, W> weightedEdges;
+ private final Mapper<WE, W> weightedEdges;
private final V source;
- public DefaultTargetSourceSelector( G graph, WeightedEdges<WE, W> weightedEdges, V source )
+ public DefaultTargetSourceSelector( G graph, Mapper<WE, W> weightedEdges, V source )
{
this.graph = graph;
this.weightedEdges = weightedEdges;
@@ -66,7 +66,7 @@ final class DefaultTargetSourceSelector<
if ( shortestDistances.alreadyVisited( u ) )
{
- W shortDist = weightOperations.append( shortestDistances.getWeight( u ), weightedEdges.getWeightForEdge( edge ) );
+ W shortDist = weightOperations.append( shortestDistances.getWeight( u ), weightedEdges.map( edge ) );
if ( !shortestDistances.alreadyVisited( v )
|| weightOperations.compare( shortDist, shortestDistances.getWeight( v ) ) < 0 )
@@ -89,7 +89,7 @@ final class DefaultTargetSourceSelector<
if ( shortestDistances.alreadyVisited( u ) )
{
- W shortDist = weightOperations.append( shortestDistances.getWeight( u ), weightedEdges.getWeightForEdge( edge ) );
+ W shortDist = weightOperations.append( shortestDistances.getWeight( u ), weightedEdges.map( edge ) );
if ( !shortestDistances.alreadyVisited( v )
|| weightOperations.compare( shortDist, shortestDistances.getWeight( v ) ) < 0 )
Modified: commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/shortestpath/DefaultWeightedEdgesSelector.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/shortestpath/DefaultWeightedEdgesSelector.java?rev=1298135&r1=1298134&r2=1298135&view=diff
==============================================================================
--- commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/shortestpath/DefaultWeightedEdgesSelector.java (original)
+++ commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/shortestpath/DefaultWeightedEdgesSelector.java Wed Mar 7 21:32:58 2012
@@ -22,10 +22,10 @@ package org.apache.commons.graph.shortes
import static org.apache.commons.graph.utils.Assertions.checkNotNull;
import org.apache.commons.graph.Graph;
-import org.apache.commons.graph.WeightedEdges;
+import org.apache.commons.graph.Mapper;
public final class DefaultWeightedEdgesSelector<V, WE, G extends Graph<V, WE>>
- implements WeightedEdgesSelector<V, WE, G>
+ implements PathWeightedEdgesBuilder<V, WE, G>
{
private final G graph;
@@ -35,7 +35,7 @@ public final class DefaultWeightedEdgesS
this.graph = graph;
}
- public <W> PathSourceSelector<V, WE, W, G> whereEdgesHaveWeights( WeightedEdges<WE, W> weightedEdges )
+ public <W> PathSourceSelector<V, WE, W, G> whereEdgesHaveWeights( Mapper<WE, W> weightedEdges )
{
weightedEdges = checkNotNull( weightedEdges, "Function to calculate edges weight can not be null." );
return new DefaultPathSourceSelector<V, WE, W, G>( graph, weightedEdges );
Copied: commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/shortestpath/PathWeightedEdgesBuilder.java (from r1298048, commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/shortestpath/WeightedEdgesSelector.java)
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/shortestpath/PathWeightedEdgesBuilder.java?p2=commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/shortestpath/PathWeightedEdgesBuilder.java&p1=commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/shortestpath/WeightedEdgesSelector.java&r1=1298048&r2=1298135&rev=1298135&view=diff
==============================================================================
--- commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/shortestpath/WeightedEdgesSelector.java (original)
+++ commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/shortestpath/PathWeightedEdgesBuilder.java Wed Mar 7 21:32:58 2012
@@ -20,13 +20,13 @@ package org.apache.commons.graph.shortes
*/
import org.apache.commons.graph.Graph;
-import org.apache.commons.graph.WeightedEdges;
+import org.apache.commons.graph.Mapper;
// TODO find a better name
-public interface WeightedEdgesSelector<V, WE, G extends Graph<V, WE>>
+public interface PathWeightedEdgesBuilder<V, WE, G extends Graph<V, WE>>
{
// TODO find a better sentence
- <W> PathSourceSelector<V, WE, W, G> whereEdgesHaveWeights( WeightedEdges<WE, W> weightedEdges );
+ <W> PathSourceSelector<V, WE, W, G> whereEdgesHaveWeights( Mapper<WE, W> weightedEdges );
}