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/01/08 20:42:52 UTC
svn commit: r1228934 - in /commons/sandbox/graph/trunk/src: changes/
main/java/org/apache/commons/graph/ main/java/org/apache/commons/graph/model/
main/java/org/apache/commons/graph/shortestpath/
main/java/org/apache/commons/graph/weight/ main/java/org...
Author: simonetripodi
Date: Sun Jan 8 19:42:51 2012
New Revision: 1228934
URL: http://svn.apache.org/viewvc?rev=1228934&view=rev
Log:
[SANDBOX-356] Generic weight types and updated shortest path implementations - patch provided by Claudio Squarcella
Added:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Monoid.java (with props)
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/OrderedMonoid.java (with props)
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Semigroup.java (with props)
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Zero.java (with props)
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/package-info.java (with props)
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/DoubleWeight.java (with props)
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/IntegerWeight.java (with props)
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/package-info.java (with props)
Modified:
commons/sandbox/graph/trunk/src/changes/changes.xml
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/Weighted.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/WeightedEdge.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/InMemoryWeightedPath.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/AStar.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/AllVertexPairsShortestPath.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/BellmannFord.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/Dijkstra.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/FloydWarshall.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PredecessorsList.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/ShortestDistances.java
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/AStarTestCase.java
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/BellmannFordTestCase.java
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/DijkstraTestCase.java
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/FloydWarshallTestCase.java
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/KruskalTestCase.java
Modified: commons/sandbox/graph/trunk/src/changes/changes.xml
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/changes/changes.xml?rev=1228934&r1=1228933&r2=1228934&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/changes/changes.xml (original)
+++ commons/sandbox/graph/trunk/src/changes/changes.xml Sun Jan 8 19:42:51 2012
@@ -23,6 +23,9 @@
</properties>
<body>
<release version="0.1" date="201?-??-??" description="First release.">
+ <action dev="simonetripodi" type="update" issue="SANDBOX-356">
+ Generic weight types and updated shortest path implementations - patch provided by Claudio Squarcella
+ </action>
<action dev="simonetripodi" type="update" issue="SANDBOX-346">
DotExporter only exports weights that extend Number - patch provided by Claudio Squarcella
</action>
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/Weighted.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/Weighted.java?rev=1228934&r1=1228933&r2=1228934&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/Weighted.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/Weighted.java Sun Jan 8 19:42:51 2012
@@ -33,6 +33,6 @@ public interface Weighted<W>
*
* @return the weight of the {@code Weighted} object.
*/
- public W getWeight();
+ W getWeight();
}
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/WeightedEdge.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/WeightedEdge.java?rev=1228934&r1=1228933&r2=1228934&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/WeightedEdge.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/WeightedEdge.java Sun Jan 8 19:42:51 2012
@@ -22,6 +22,8 @@ package org.apache.commons.graph;
/**
* A WeightedEdge is an {@link Edge} that is assigned a weight to represent, for example,
* costs, lengths or capacities, etc. depending on the problem.
+ *
+ * @param <W> the weight type
*/
public interface WeightedEdge<W>
extends Edge, Weighted<W>, Comparable<WeightedEdge<W>>
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/InMemoryWeightedPath.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/InMemoryWeightedPath.java?rev=1228934&r1=1228933&r2=1228934&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/InMemoryWeightedPath.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/InMemoryWeightedPath.java Sun Jan 8 19:42:51 2012
@@ -24,6 +24,7 @@ import static java.lang.String.format;
import org.apache.commons.graph.Vertex;
import org.apache.commons.graph.WeightedEdge;
import org.apache.commons.graph.WeightedPath;
+import org.apache.commons.graph.weight.Monoid;
/**
* Support {@link WeightedPath} implementation, optimized for algorithms (such Dijkstra's) that need to rebuild the path
@@ -31,17 +32,21 @@ import org.apache.commons.graph.Weighted
*
* @param <V> the Graph vertices type
* @param <WE> the Graph weighted edges type
+ * @param <W> the weight type
*/
-public final class InMemoryWeightedPath<V extends Vertex, WE extends WeightedEdge<Double>>
+public final class InMemoryWeightedPath<V extends Vertex, WE extends WeightedEdge<W>, W>
extends InMemoryPath<V, WE>
- implements WeightedPath<V, WE, Double>
+ implements WeightedPath<V, WE, W>
{
- private Double weigth = 0D;
+ private W weight;
+ private Monoid<W> monoid;
- public InMemoryWeightedPath( V start, V target )
+ public InMemoryWeightedPath( V start, V target, Monoid<W> monoid )
{
super( start, target );
+ this.monoid = monoid;
+ this.weight = monoid.zero();
}
/**
@@ -65,21 +70,21 @@ public final class InMemoryWeightedPath<
}
/**
- * Increase the path weight
+ * Increase the path weight with the weight of the input weighted edge.
*
- * @param edge the edge which weigth increase the path weigth
+ * @param edge the edge whose weight is used to increase the path weight
*/
private void increaseWeight( WE edge )
{
- weigth = edge.getWeight().doubleValue() + weigth.doubleValue();
+ weight = monoid.append( edge.getWeight(), weight );
}
/**
* {@inheritDoc}
*/
- public Double getWeight()
+ public W getWeight()
{
- return weigth;
+ return weight;
}
/**
@@ -90,7 +95,7 @@ public final class InMemoryWeightedPath<
{
final int prime = 31;
int result = super.hashCode();
- result = prime * result + ( ( weigth == null ) ? 0 : weigth.hashCode() );
+ result = prime * result + ( ( weight == null ) ? 0 : weight.hashCode() );
return result;
}
@@ -116,8 +121,8 @@ public final class InMemoryWeightedPath<
}
@SuppressWarnings( "unchecked" ) // test against any WeightedPath typed instance
- InMemoryWeightedPath<Vertex, WeightedEdge<Double>> other = (InMemoryWeightedPath<Vertex, WeightedEdge<Double>>) obj;
- if ( !weigth.equals( other.getWeight() ) )
+ InMemoryWeightedPath<Vertex, WeightedEdge<W>, W> other = (InMemoryWeightedPath<Vertex, WeightedEdge<W>, W>) obj;
+ if ( !weight.equals( other.getWeight() ) )
{
return false;
}
@@ -130,7 +135,7 @@ public final class InMemoryWeightedPath<
@Override
public String toString()
{
- return format( "InMemoryPath [weigth=%s, vertices=%s, edges=%s]", weigth, getVertices(), getEdges() );
+ return format( "InMemoryPath [weigth=%s, vertices=%s, edges=%s]", weight, getVertices(), getEdges() );
}
}
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/AStar.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/AStar.java?rev=1228934&r1=1228933&r2=1228934&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/AStar.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/AStar.java Sun Jan 8 19:42:51 2012
@@ -29,6 +29,7 @@ import org.apache.commons.graph.Vertex;
import org.apache.commons.graph.WeightedEdge;
import org.apache.commons.graph.WeightedPath;
import org.apache.commons.graph.collections.FibonacciHeap;
+import org.apache.commons.graph.weight.primitive.DoubleWeight;
/**
* Contains the A* shortest path algorithm implementation.
@@ -36,6 +37,8 @@ import org.apache.commons.graph.collecti
public final class AStar
{
+ private static final DoubleWeight DOUBLE_WEIGHT = new DoubleWeight();
+
/**
* This class can not be instantiated directly
*/
@@ -61,11 +64,11 @@ public final class AStar
Heuristic<V> heuristic )
{
// Cost from start along best known path.
- final ShortestDistances<V> gScores = new ShortestDistances<V>();
+ final ShortestDistances<V, Double> gScores = new ShortestDistances<V, Double>( DOUBLE_WEIGHT );
gScores.setWeight( start, 0D );
// Estimated total cost from start to goal through y.
- final ShortestDistances<V> fScores = new ShortestDistances<V>();
+ final ShortestDistances<V, Double> fScores = new ShortestDistances<V, Double>( DOUBLE_WEIGHT );
Double hScore = heuristic.applyHeuristic( start, goal );
fScores.setWeight( start, hScore );
@@ -77,7 +80,7 @@ public final class AStar
openSet.add( start );
// The of navigated nodes
- final PredecessorsList<V, WE> predecessors = new PredecessorsList<V, WE>( graph );
+ final PredecessorsList<V, WE, Double> predecessors = new PredecessorsList<V, WE, Double>( graph, DOUBLE_WEIGHT );
// extract the node in openset having the lowest f_score[] value
while ( !openSet.isEmpty() )
@@ -99,8 +102,10 @@ public final class AStar
if ( !closedSet.contains( v ) )
{
WE edge = graph.getEdge( current, v );
+ // note that the weight of current can never be undefined
Double tentativeGScore = gScores.getWeight( current ) + edge.getWeight();
+ // if the first condition fails, v has already been visited (its weight is defined)
if ( openSet.add( v ) || tentativeGScore.compareTo( gScores.getWeight( v ) ) < 0 )
{
predecessors.addPredecessor( v, current );
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/AllVertexPairsShortestPath.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/AllVertexPairsShortestPath.java?rev=1228934&r1=1228933&r2=1228934&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/AllVertexPairsShortestPath.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/AllVertexPairsShortestPath.java Sun Jan 8 19:42:51 2012
@@ -26,26 +26,30 @@ import org.apache.commons.graph.Vertex;
import org.apache.commons.graph.VertexPair;
import org.apache.commons.graph.WeightedEdge;
import org.apache.commons.graph.WeightedPath;
+import org.apache.commons.graph.weight.OrderedMonoid;
/**
* Represents all shortest paths between all vertex pairs calculated by {@link FloydWarshall} algorithm.
- *
+ *
* @param <V> the Graph vertices type
- * @param <E> the Graph edges type
+ * @param <WE> the Graph weighted edges type
+ * @param <W> the weight type
*/
-public final class AllVertexPairsShortestPath<V extends Vertex, WE extends WeightedEdge<Double>>
+public final class AllVertexPairsShortestPath<V extends Vertex, WE extends WeightedEdge<W>, W>
{
- private final Map<VertexPair<V>, WeightedPath<V, WE, Double>> paths = new HashMap<VertexPair<V>, WeightedPath<V, WE, Double>>();
+ private final Map<VertexPair<V>, WeightedPath<V, WE, W>> paths = new HashMap<VertexPair<V>, WeightedPath<V, WE, W>>();
- private final Map<VertexPair<V>, Double> shortestDistances = new HashMap<VertexPair<V>, Double>();
+ private final Map<VertexPair<V>, W> shortestDistances = new HashMap<VertexPair<V>, W>();
+
+ private final OrderedMonoid<W> orderedMonoid;
/**
* Constructor visible only inside the package
*/
- AllVertexPairsShortestPath()
+ AllVertexPairsShortestPath( OrderedMonoid<W> orderedMonoid )
{
- // do nothing
+ this.orderedMonoid = orderedMonoid;
}
/**
@@ -53,7 +57,7 @@ public final class AllVertexPairsShortes
* @param target
* @param weightedPath
*/
- void addShortestPath( V source, V target, WeightedPath<V, WE, Double> weightedPath )
+ void addShortestPath( V source, V target, WeightedPath<V, WE, W> weightedPath )
{
if ( source == null )
{
@@ -73,12 +77,12 @@ public final class AllVertexPairsShortes
/**
* Returns the shortest path between source and target
- *
+ *
* @param source The source Vertex
* @param target The target Vertex
* @return Returns the shortest path between source and target
*/
- public WeightedPath<V, WE, Double> findShortestPath( V source, V target )
+ public WeightedPath<V, WE, W> findShortestPath( V source, V target )
{
if ( source == null )
{
@@ -89,7 +93,7 @@ public final class AllVertexPairsShortes
throw new IllegalArgumentException( "Impossible to find the shortest path to a null target" );
}
- WeightedPath<V, WE, Double> path = paths.get( new VertexPair<V>( source, target ) );
+ WeightedPath<V, WE, W> path = paths.get( new VertexPair<V>( source, target ) );
if ( path == null )
{
@@ -104,7 +108,7 @@ public final class AllVertexPairsShortes
* @param target
* @param distance
*/
- void addShortestDistance( V source, V target, Double distance )
+ void addShortestDistance( V source, V target, W distance )
{
if ( source == null )
{
@@ -124,12 +128,12 @@ public final class AllVertexPairsShortes
/**
* Returns the shortest distance between source and target.
- *
+ *
* @param source The source Vertex
* @param target The target Vertex
* @return Returns the shortest distance between source and target.
*/
- Double getShortestDistance( V source, V target )
+ W getShortestDistance( V source, V target )
{
if ( source == null )
{
@@ -142,17 +146,36 @@ public final class AllVertexPairsShortes
if ( source.equals( target ) )
{
- return 0D;
+ return orderedMonoid.zero();
}
- Double distance = shortestDistances.get( new VertexPair<V>( source, target ) );
+ return shortestDistances.get( new VertexPair<V>( source, target ) );
+ }
- if ( distance == null )
+ /**
+ * Checks if there is a shortest distance between source and target.
+ *
+ * @param source The source Vertex
+ * @param target The target Vertex
+ * @return Returns true if there is a shortest distance between source and target, false otherwise.
+ */
+ boolean hasShortestDistance( V source, V target )
+ {
+ if ( source == null )
+ {
+ throw new IllegalArgumentException( "Impossible to get the shortest distance from a null source" );
+ }
+ if ( target == null )
+ {
+ throw new IllegalArgumentException( "Impossible to get the shortest distance to a null target" );
+ }
+
+ if ( source.equals( target ) )
{
- return Double.POSITIVE_INFINITY;
+ return true;
}
- return distance;
+ return shortestDistances.containsKey( new VertexPair<V>( source, target ) );
}
@Override
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/BellmannFord.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/BellmannFord.java?rev=1228934&r1=1228933&r2=1228934&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/BellmannFord.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/BellmannFord.java Sun Jan 8 19:42:51 2012
@@ -1,11 +1,5 @@
package org.apache.commons.graph.shortestpath;
-import org.apache.commons.graph.DirectedGraph;
-import org.apache.commons.graph.Vertex;
-import org.apache.commons.graph.VertexPair;
-import org.apache.commons.graph.WeightedEdge;
-import org.apache.commons.graph.WeightedPath;
-
/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements. See the NOTICE file
@@ -25,6 +19,14 @@ import org.apache.commons.graph.Weighted
* under the License.
*/
+import org.apache.commons.graph.DirectedGraph;
+import org.apache.commons.graph.Vertex;
+import org.apache.commons.graph.VertexPair;
+import org.apache.commons.graph.WeightedEdge;
+import org.apache.commons.graph.WeightedPath;
+import org.apache.commons.graph.weight.OrderedMonoid;
+import org.apache.commons.graph.weight.primitive.DoubleWeight;
+
/**
* Contains the BellmanÐFord's shortest path algorithm implementation.
*/
@@ -42,20 +44,23 @@ public final class BellmannFord
/**
* Applies the classical BellmanÐFord's algorithm to find the shortest path from the source to the target, if exists.
*
- * @param <V> the Graph vertices type.
+ * @param <V> the Graph vertices type
* @param <WE> the Graph weighted edges type
- * @param graph the Graph which shortest path from {@code source} to {@code target} has to be found
+ * @param <W> the weight type
+ * @param <G> the Graph type
+ * @param graph the Graph whose shortest path from {@code source} to {@code target} has to be found
* @param source the shortest path source Vertex
- * @param target the shortest path target Vertex
+ * @param orderedMonoid the {@code OrderedMonoid} needed to handle weights
* @return a path which describes the shortest path, if any, otherwise a {@link PathNotFoundException} will be thrown
*/
- public static <V extends Vertex, WE extends WeightedEdge<Double>, G extends DirectedGraph<V, WE>> AllVertexPairsShortestPath<V, WE> findShortestPath( G graph,
- V source)
+ public static <V extends Vertex, W, WE extends WeightedEdge<W>, G extends DirectedGraph<V, WE>> AllVertexPairsShortestPath<V, WE, W> findShortestPath( G graph,
+ V source,
+ OrderedMonoid<W> orderedMonoid )
{
- final ShortestDistances<V> shortestDistances = new ShortestDistances<V>();
- shortestDistances.setWeight( source, 0D );
+ final ShortestDistances<V, W> shortestDistances = new ShortestDistances<V, W>( orderedMonoid );
+ shortestDistances.setWeight( source, orderedMonoid.zero() );
- final PredecessorsList<V, WE> predecessors = new PredecessorsList<V, WE>( graph );
+ final PredecessorsList<V, WE, W> predecessors = new PredecessorsList<V, WE, W>( graph, orderedMonoid );
for ( int i = 0; i < graph.getOrder(); i++ )
{
@@ -65,15 +70,19 @@ public final class BellmannFord
V u = vertexPair.getHead();
V v = vertexPair.getTail();
- Double shortDist = shortestDistances.getWeight( u ) + edge.getWeight();
-
- if ( shortDist.compareTo( shortestDistances.getWeight( v ) ) < 0 )
+ if ( shortestDistances.alreadyVisited( u ) )
{
- // assign new shortest distance and mark unsettled
- shortestDistances.setWeight( v, shortDist );
+ W shortDist = orderedMonoid.append( shortestDistances.getWeight( u ), edge.getWeight() );
- // assign predecessor in shortest path
- predecessors.addPredecessor( v, u );
+ if ( !shortestDistances.alreadyVisited( v )
+ || orderedMonoid.compare( shortDist, shortestDistances.getWeight( v ) ) < 0 )
+ {
+ // assign new shortest distance and mark unsettled
+ shortestDistances.setWeight( v, shortDist );
+
+ // assign predecessor in shortest path
+ predecessors.addPredecessor( v, u );
+ }
}
}
}
@@ -84,23 +93,27 @@ public final class BellmannFord
V u = vertexPair.getHead();
V v = vertexPair.getTail();
- Double shortDist = shortestDistances.getWeight( u ) + edge.getWeight();
-
- if ( shortDist.compareTo( shortestDistances.getWeight( v ) ) < 0 )
+ if ( shortestDistances.alreadyVisited( u ) )
{
- // TODO it would be nice printing the cycle
- throw new NegativeWeightedCycleException( "Graph contains a negative-weight cycle in vertex %s",
- v, graph );
+ W shortDist = orderedMonoid.append( shortestDistances.getWeight( u ), edge.getWeight() );
+
+ if ( !shortestDistances.alreadyVisited( v )
+ || orderedMonoid.compare( shortDist, shortestDistances.getWeight( v ) ) < 0 )
+ {
+ // TODO it would be nice printing the cycle
+ throw new NegativeWeightedCycleException( "Graph contains a negative-weight cycle in vertex %s",
+ v, graph );
+ }
}
}
- AllVertexPairsShortestPath<V, WE> allVertexPairsShortestPath = new AllVertexPairsShortestPath<V, WE>();
+ AllVertexPairsShortestPath<V, WE, W> allVertexPairsShortestPath = new AllVertexPairsShortestPath<V, WE, W>( orderedMonoid );
for ( V target : graph.getVertices() )
{
if ( !source.equals( target ) )
{
- WeightedPath<V, WE, Double> weightedPath = predecessors.buildPath( source, target );
+ WeightedPath<V, WE, W> weightedPath = predecessors.buildPath( source, target );
allVertexPairsShortestPath.addShortestPath( source, target, weightedPath );
}
}
@@ -108,4 +121,21 @@ public final class BellmannFord
return allVertexPairsShortestPath;
}
+ /**
+ * Applies the classical BellmanÐFord's algorithm to an edge weighted graph with weights of type Double
+ * to find the shortest path from the source to the target, if exists.
+ *
+ * @param <V> the Graph vertices type
+ * @param <WE> the Graph weighted edges type
+ * @param <G> the Graph type
+ * @param graph the Graph whose shortest path from {@code source} to {@code target} has to be found
+ * @param source the shortest path source Vertex
+ * @return a path which describes the shortest path, if any, otherwise a {@link PathNotFoundException} will be thrown
+ */
+ public static <V extends Vertex, WE extends WeightedEdge<Double>, G extends DirectedGraph<V, WE>> AllVertexPairsShortestPath<V, WE, Double> findShortestPath( G graph,
+ V source )
+ {
+ return findShortestPath( graph, source, new DoubleWeight() );
+ }
+
}
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/Dijkstra.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/Dijkstra.java?rev=1228934&r1=1228933&r2=1228934&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/Dijkstra.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/Dijkstra.java Sun Jan 8 19:42:51 2012
@@ -28,6 +28,8 @@ import org.apache.commons.graph.Vertex;
import org.apache.commons.graph.WeightedEdge;
import org.apache.commons.graph.WeightedPath;
import org.apache.commons.graph.collections.FibonacciHeap;
+import org.apache.commons.graph.weight.OrderedMonoid;
+import org.apache.commons.graph.weight.primitive.DoubleWeight;
/**
* Contains the Dijkstra's shortest path algorithm implementation.
@@ -46,27 +48,31 @@ public final class Dijkstra
/**
* Applies the classical Dijkstra's algorithm to find the shortest path from the source to the target, if exists.
*
- * @param <V> the Graph vertices type.
+ * @param <V> the Graph vertices type
+ * @param <W> the weight type
* @param <WE> the Graph weighted edges type
- * @param graph the Graph which shortest path from {@code source} to {@code target} has to be found
+ * @param <G> the Graph type
+ * @param graph the Graph whose shortest path from {@code source} to {@code target} has to be found
* @param source the shortest path source Vertex
* @param target the shortest path target Vertex
+ * @param orderedMonoid the {@link OrderedMonoid} needed to handle operations on weights
* @return a path which describes the shortest path, if any,
* otherwise a {@link PathNotFoundException} will be thrown
*/
- public static <V extends Vertex, WE extends WeightedEdge<Double>, G extends DirectedGraph<V, WE>> WeightedPath<V, WE, Double> findShortestPath( G graph,
- V source,
- V target )
+ public static <V extends Vertex, W, WE extends WeightedEdge<W>, G extends DirectedGraph<V, WE>> WeightedPath<V, WE, W> findShortestPath( G graph,
+ V source,
+ V target,
+ OrderedMonoid<W> orderedMonoid )
{
- final ShortestDistances<V> shortestDistances = new ShortestDistances<V>();
- shortestDistances.setWeight( source, 0D );
+ final ShortestDistances<V, W> shortestDistances = new ShortestDistances<V, W>( orderedMonoid );
+ shortestDistances.setWeight( source, orderedMonoid.zero() );
final Queue<V> unsettledNodes = new FibonacciHeap<V>( shortestDistances );
unsettledNodes.add( source );
final Set<V> settledNodes = new HashSet<V>();
- final PredecessorsList<V, WE> predecessors = new PredecessorsList<V, WE>( graph );
+ final PredecessorsList<V, WE, W> predecessors = new PredecessorsList<V, WE, W>( graph, orderedMonoid );
// extract the node with the shortest distance
while ( !unsettledNodes.isEmpty() )
@@ -87,17 +93,22 @@ public final class Dijkstra
if ( !settledNodes.contains( v ) )
{
WE edge = graph.getEdge( vertex, v );
- Double shortDist = shortestDistances.getWeight( vertex ) + edge.getWeight();
-
- if ( shortDist.compareTo( shortestDistances.getWeight( v ) ) < 0 )
+ if ( shortestDistances.alreadyVisited( vertex ) )
{
- // assign new shortest distance and mark unsettled
- shortestDistances.setWeight( v, shortDist );
- unsettledNodes.add( v );
+ W shortDist = orderedMonoid.append( shortestDistances.getWeight( vertex ), edge.getWeight() );
- // assign predecessor in shortest path
- predecessors.addPredecessor( v, vertex );
+ if ( !shortestDistances.alreadyVisited( v )
+ || orderedMonoid.compare( shortDist, shortestDistances.getWeight( v ) ) < 0 )
+ {
+ // assign new shortest distance and mark unsettled
+ shortestDistances.setWeight( v, shortDist );
+ unsettledNodes.add( v );
+
+ // assign predecessor in shortest path
+ predecessors.addPredecessor( v, vertex );
+ }
}
+
}
}
}
@@ -105,4 +116,24 @@ public final class Dijkstra
throw new PathNotFoundException( "Path from '%s' to '%s' doesn't exist in Graph '%s'", source, target, graph );
}
+ /**
+ * Applies the classical Dijkstra's algorithm to an edge weighted graph with weights of type Double
+ * to find the shortest path from the source to the target, if exists.
+ *
+ * @param <V> the Graph vertices type
+ * @param <WE> the Graph weighted edges type
+ * @param <G> the Graph type
+ * @param graph the Graph whose shortest path from {@code source} to {@code target} has to be found
+ * @param source the shortest path source Vertex
+ * @param target the shortest path target Vertex
+ * @return a path which describes the shortest path, if any,
+ * otherwise a {@link PathNotFoundException} will be thrown
+ */
+ public static <V extends Vertex, WE extends WeightedEdge<Double>, G extends DirectedGraph<V, WE>> WeightedPath<V, WE, Double> findShortestPath( G graph,
+ V source,
+ V target )
+ {
+ return findShortestPath( graph, source, target, new DoubleWeight() );
+ }
+
}
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/FloydWarshall.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/FloydWarshall.java?rev=1228934&r1=1228933&r2=1228934&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/FloydWarshall.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/FloydWarshall.java Sun Jan 8 19:42:51 2012
@@ -28,6 +28,8 @@ import org.apache.commons.graph.Vertex;
import org.apache.commons.graph.VertexPair;
import org.apache.commons.graph.WeightedEdge;
import org.apache.commons.graph.WeightedPath;
+import org.apache.commons.graph.weight.OrderedMonoid;
+import org.apache.commons.graph.weight.primitive.DoubleWeight;
/**
* Contains the Floyd-Warshall's shortest paths algorithm implementation.
@@ -45,25 +47,28 @@ public final class FloydWarshall
/**
* Applies the classical Floyd-Warshall's algorithm to find all vertex shortest path
- *
+ *
* @param <V> the Graph vertices type.
* @param <WE> the Graph weighted edges type
+ * @param <W> the weight type
+ * @param graph the input graph
+ * @param orderedMonoid the {@link OrderedMonoid} needed to handle operations on weights
* @return a data structure which contains all vertex pairs shortest path.
*/
- public static <V extends Vertex, WE extends WeightedEdge<Double>> AllVertexPairsShortestPath<V, WE> findAllVertexPairsShortestPath( Graph<V, WE> graph )
+ public static <V extends Vertex, W, WE extends WeightedEdge<W>> AllVertexPairsShortestPath<V, WE, W> findAllVertexPairsShortestPath( Graph<V, WE> graph, OrderedMonoid<W> orderedMonoid )
{
- AllVertexPairsShortestPath<V, WE> shortesPaths = new AllVertexPairsShortestPath<V, WE>();
+ AllVertexPairsShortestPath<V, WE, W> shortestPaths = new AllVertexPairsShortestPath<V, WE, W>( orderedMonoid );
Map<VertexPair<V>, V> next = new HashMap<VertexPair<V>, V>();
// init
for ( WE we : graph.getEdges() )
{
VertexPair<V> vertexPair = graph.getVertices( we );
- shortesPaths.addShortestDistance( vertexPair.getHead(), vertexPair.getTail(), we.getWeight() );
+ shortestPaths.addShortestDistance( vertexPair.getHead(), vertexPair.getTail(), we.getWeight() );
if ( graph instanceof UndirectedGraph )
{
- shortesPaths.addShortestDistance( vertexPair.getTail(), vertexPair.getHead(), we.getWeight() );
+ shortestPaths.addShortestDistance( vertexPair.getTail(), vertexPair.getHead(), we.getWeight() );
}
}
@@ -74,15 +79,19 @@ public final class FloydWarshall
{
for ( V j : graph.getVertices() )
{
- Double newDistance =
- shortesPaths.getShortestDistance( i, k ) + shortesPaths.getShortestDistance( k, j );
- if ( newDistance.compareTo( shortesPaths.getShortestDistance( i, j ) ) < 0 )
+ if ( shortestPaths.hasShortestDistance( i, k ) && shortestPaths.hasShortestDistance( k, j ) )
{
- shortesPaths.addShortestDistance( i, j, newDistance );
+ W newDistance = orderedMonoid.append( shortestPaths.getShortestDistance( i, k ), shortestPaths.getShortestDistance( k, j ) );
+ if ( !shortestPaths.hasShortestDistance( i, j )
+ || orderedMonoid.compare( newDistance, shortestPaths.getShortestDistance( i, j ) ) < 0 )
+ {
+ shortestPaths.addShortestDistance( i, j, newDistance );
- // store the intermediate vertex
- next.put( new VertexPair<V>( i, j ), k );
+ // store the intermediate vertex
+ next.put( new VertexPair<V>( i, j ), k );
+ }
}
+
}
}
}
@@ -94,25 +103,39 @@ public final class FloydWarshall
{
if ( !source.equals( target ) )
{
- PredecessorsList<V, WE> predecessorsList = new PredecessorsList<V, WE>( graph );
+ PredecessorsList<V, WE, W> predecessorsList = new PredecessorsList<V, WE, W>( graph, orderedMonoid );
pathReconstruction( predecessorsList, source, target, next, graph );
if ( !predecessorsList.isEmpty() )
{
- WeightedPath<V, WE, Double> weightedPath = predecessorsList.buildPath( source, target );
+ WeightedPath<V, WE, W> weightedPath = predecessorsList.buildPath( source, target );
if ( weightedPath.getOrder() > 0 )
{
- shortesPaths.addShortestPath( source, target, weightedPath );
+ shortestPaths.addShortestPath( source, target, weightedPath );
}
}
}
}
}
- return shortesPaths;
+ return shortestPaths;
+ }
+
+ /**
+ * Applies the classical Floyd-Warshall's algorithm to an edge weighted graph with weights of type Double
+ * to find all vertex shortest path.
+ *
+ * @param <V> the Graph vertices type.
+ * @param <WE> the Graph weighted edges type
+ * @param graph the input graph
+ * @return a data structure which contains all vertex pairs shortest path.
+ */
+ public static <V extends Vertex, WE extends WeightedEdge<Double>> AllVertexPairsShortestPath<V, WE, Double> findAllVertexPairsShortestPath( Graph<V, WE> graph )
+ {
+ return findAllVertexPairsShortestPath( graph, new DoubleWeight() );
}
- private static <V extends Vertex, WE extends WeightedEdge<Double>> void pathReconstruction( PredecessorsList<V, WE> path,
+ private static <V extends Vertex, WE extends WeightedEdge<W>, W> void pathReconstruction( PredecessorsList<V, WE, W> path,
V source, V target,
Map<VertexPair<V>, V> next,
Graph<V, WE> graph )
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PredecessorsList.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PredecessorsList.java?rev=1228934&r1=1228933&r2=1228934&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PredecessorsList.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PredecessorsList.java Sun Jan 8 19:42:51 2012
@@ -22,30 +22,34 @@ package org.apache.commons.graph.shortes
import java.util.HashMap;
import java.util.Map;
-import org.apache.commons.graph.Edge;
import org.apache.commons.graph.Graph;
import org.apache.commons.graph.Vertex;
import org.apache.commons.graph.WeightedEdge;
import org.apache.commons.graph.WeightedPath;
import org.apache.commons.graph.model.InMemoryWeightedPath;
+import org.apache.commons.graph.weight.Monoid;
/**
* The predecessor list is a list of {@link Vertex} of a {@link org.apache.commons.graph.Graph}.
* Each {@link Vertex}' entry contains the index of its predecessor in a path through the graph.
*
* @param <V> the Graph vertices type
- * @param <E> the Graph edges type
+ * @param <WE> the Graph weighted edges type
+ * @param <W> the weight type
*/
-final class PredecessorsList<V extends Vertex, WE extends WeightedEdge<Double>>
+final class PredecessorsList<V extends Vertex, WE extends WeightedEdge<W>, W>
{
private final Graph<V, WE> graph;
+
+ private final Monoid<W> monoid;
private final Map<V, V> predecessors = new HashMap<V, V>();
- public PredecessorsList(Graph<V, WE> graph )
+ public PredecessorsList( Graph<V, WE> graph, Monoid<W> monoid )
{
this.graph = graph;
+ this.monoid = monoid;
}
/**
@@ -67,9 +71,9 @@ final class PredecessorsList<V extends V
* @param cost the path cost
* @return the weighted path related to source to target
*/
- public WeightedPath<V, WE, Double> buildPath( V source, V target )
+ public WeightedPath<V, WE, W> buildPath( V source, V target )
{
- InMemoryWeightedPath<V, WE> path = new InMemoryWeightedPath<V, WE>( source, target );
+ InMemoryWeightedPath<V, WE, W> path = new InMemoryWeightedPath<V, WE, W>( source, target, monoid );
V vertex = target;
while ( !source.equals( vertex ) )
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/ShortestDistances.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/ShortestDistances.java?rev=1228934&r1=1228933&r2=1228934&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/ShortestDistances.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/ShortestDistances.java Sun Jan 8 19:42:51 2012
@@ -24,36 +24,52 @@ import java.util.HashMap;
import java.util.Map;
import org.apache.commons.graph.Vertex;
+import org.apache.commons.graph.weight.OrderedMonoid;
/**
* Stores and compares Graph Vertices weights.
*
* @param <V> the Graph vertices type
+ * @param <W> the weight type
*/
-final class ShortestDistances<V extends Vertex>
+final class ShortestDistances<V extends Vertex, W>
implements Comparator<V>
{
private static final long serialVersionUID = 568538689459177637L;
- private final Map<V, Double> distances = new HashMap<V, Double>();
+ private final Map<V, W> distances = new HashMap<V, W>();
+
+ private final OrderedMonoid<W> orderedMonoid;
+
+ public ShortestDistances( OrderedMonoid<W> orderedMonoid )
+ {
+ this.orderedMonoid = orderedMonoid;
+ }
/**
- * Returns the distance related to input vertex, or {@code INFINITY} if it wasn't previously visited.
+ * Returns the distance related to input vertex, or null if it wasn't previously visited.
+ *
+ * <b>NOTE</b>: the method {@link alreadyVisited} should be used first to check if
+ * the input vertex was already visited and a distance value is available for it.
*
- * @param vertex the vertex for which the distance has to be retrieved
- * @return the distance related to input vertex, or {@code INFINITY} if it wasn't previously visited.
+ * @param vertex the vertex whose distance has to be retrieved
+ * @return the distance related to input vertex, or null if it wasn't previously visited.
*/
- public Double getWeight( V vertex )
+ public W getWeight( V vertex )
{
- Double distance = distances.get( vertex );
-
- if ( distance == null )
- {
- return Double.POSITIVE_INFINITY;
- }
+ return distances.get( vertex );
+ }
- return distance;
+ /**
+ * Checks if the input {@code Vertex} was already visited.
+ *
+ * @param vertex the input {@code Vertex}
+ * @return true if the input {@code Vertex} was already visited, false otherwise.
+ */
+ public boolean alreadyVisited( V vertex )
+ {
+ return distances.containsKey( vertex );
}
/**
@@ -62,7 +78,7 @@ final class ShortestDistances<V extends
* @param vertex the vertex for which the distance has to be updated
* @param distance the new input vertex distance
*/
- public void setWeight( V vertex, Double distance )
+ public void setWeight( V vertex, W distance )
{
distances.put( vertex, distance );
}
@@ -72,7 +88,19 @@ final class ShortestDistances<V extends
*/
public int compare( V left, V right )
{
- return getWeight( left ).compareTo( getWeight( right ) );
+ if ( !alreadyVisited( left ) && !alreadyVisited( right ) )
+ {
+ return 0;
+ }
+ else if ( !alreadyVisited( left ) )
+ {
+ return 1;
+ }
+ else if ( !alreadyVisited( right ) )
+ {
+ return -1;
+ }
+ return orderedMonoid.compare( getWeight( left ), getWeight( right ) );
}
}
Added: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Monoid.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Monoid.java?rev=1228934&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Monoid.java (added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Monoid.java Sun Jan 8 19:42:51 2012
@@ -0,0 +1,31 @@
+package org.apache.commons.graph.weight;
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+/**
+ * A {@link Monoid} is a {@link Semigroup} with an identity value.
+ *
+ * @param <M> the type of the elements in the {@link Monoid}
+ */
+public interface Monoid<M>
+ extends Zero<M>, Semigroup<M>
+{
+
+}
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Monoid.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Monoid.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Monoid.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Added: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/OrderedMonoid.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/OrderedMonoid.java?rev=1228934&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/OrderedMonoid.java (added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/OrderedMonoid.java Sun Jan 8 19:42:51 2012
@@ -0,0 +1,33 @@
+package org.apache.commons.graph.weight;
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+import java.util.Comparator;
+
+/**
+ * An {@link OrderedMonoid} is a {@link Monoid} with a total order defined on it.
+ *
+ * @param <M> the type of the elements in the {@link OrderedMonoid}
+ */
+public interface OrderedMonoid<M>
+ extends Monoid<M>, Comparator<M>
+{
+
+}
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/OrderedMonoid.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/OrderedMonoid.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/OrderedMonoid.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Added: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Semigroup.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Semigroup.java?rev=1228934&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Semigroup.java (added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Semigroup.java Sun Jan 8 19:42:51 2012
@@ -0,0 +1,41 @@
+package org.apache.commons.graph.weight;
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+/**
+ * A {@link Semigroup} defines an associative binary operation
+ * on a set of elements of the same type.
+ *
+ * @param <S> the type of the elements in the {@link Semigroup}
+ */
+public interface Semigroup<S>
+{
+
+ /**
+ * Returns the result of the associative binary operation defined by this
+ * {@link Semigroup} between two elements of appropriate type.
+ *
+ * @param s1 the first element
+ * @param s2 the second element
+ * @return the result of the associative binary operation
+ */
+ S append( S s1, S s2 );
+
+}
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Semigroup.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Semigroup.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Semigroup.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Added: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Zero.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Zero.java?rev=1228934&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Zero.java (added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Zero.java Sun Jan 8 19:42:51 2012
@@ -0,0 +1,38 @@
+package org.apache.commons.graph.weight;
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+/**
+ * An object implementing {@link Zero} provides access to an identity value,
+ * also called zero, for the specified type.
+ *
+ * @param <Z> the type of the identity value
+ */
+public interface Zero<Z>
+{
+
+ /**
+ * Returns the identity value.
+ *
+ * @return the identity value
+ */
+ Z zero();
+
+}
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Zero.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Zero.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/Zero.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Added: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/package-info.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/package-info.java?rev=1228934&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/package-info.java (added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/package-info.java Sun Jan 8 19:42:51 2012
@@ -0,0 +1,23 @@
+/**
+ * Interfaces that define properties and operations on weights.
+ */
+package org.apache.commons.graph.weight;
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
\ No newline at end of file
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/package-info.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/package-info.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/package-info.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Added: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/DoubleWeight.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/DoubleWeight.java?rev=1228934&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/DoubleWeight.java (added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/DoubleWeight.java Sun Jan 8 19:42:51 2012
@@ -0,0 +1,60 @@
+package org.apache.commons.graph.weight.primitive;
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+import org.apache.commons.graph.weight.OrderedMonoid;
+
+/**
+ * A {@link DoubleWeight} provides operations and properties
+ * for weights of type {@link Double}.
+ */
+public class DoubleWeight
+ implements OrderedMonoid<Double>
+{
+
+ /**
+ * {@inheritDoc}
+ */
+ public Double zero()
+ {
+ return 0.0;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public Double append( Double s1, Double s2 )
+ {
+ if ( s1 == null || s2 == null )
+ {
+ return null;
+ }
+ return s1 + s2;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public int compare( Double s1, Double s2 )
+ {
+ return s1.compareTo( s2 );
+ }
+
+}
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/DoubleWeight.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/DoubleWeight.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/DoubleWeight.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Added: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/IntegerWeight.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/IntegerWeight.java?rev=1228934&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/IntegerWeight.java (added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/IntegerWeight.java Sun Jan 8 19:42:51 2012
@@ -0,0 +1,60 @@
+package org.apache.commons.graph.weight.primitive;
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+import org.apache.commons.graph.weight.OrderedMonoid;
+
+/**
+ * A {@link IntegerWeight} provides operations and properties
+ * for weights of type {@link Integer}.
+ */
+public class IntegerWeight
+ implements OrderedMonoid<Integer>
+{
+
+ /**
+ * {@inheritDoc}
+ */
+ public Integer zero()
+ {
+ return 0;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public Integer append( Integer s1, Integer s2 )
+ {
+ if ( s1 == null || s2 == null )
+ {
+ return null;
+ }
+ return s1 + s2;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public int compare( Integer o1, Integer o2 )
+ {
+ return o1.compareTo( o2 );
+ }
+
+}
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/IntegerWeight.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/IntegerWeight.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/IntegerWeight.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Added: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/package-info.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/package-info.java?rev=1228934&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/package-info.java (added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/package-info.java Sun Jan 8 19:42:51 2012
@@ -0,0 +1,23 @@
+/**
+ * Primitive weight implementations.
+ */
+package org.apache.commons.graph.weight.primitive;
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
\ No newline at end of file
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/package-info.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/package-info.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/weight/primitive/package-info.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Modified: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/AStarTestCase.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/AStarTestCase.java?rev=1228934&r1=1228933&r2=1228934&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/AStarTestCase.java (original)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/AStarTestCase.java Sun Jan 8 19:42:51 2012
@@ -30,6 +30,7 @@ import org.apache.commons.graph.model.Ba
import org.apache.commons.graph.model.BaseLabeledWeightedEdge;
import org.apache.commons.graph.model.InMemoryWeightedPath;
import org.apache.commons.graph.model.UndirectedMutableWeightedGraph;
+import org.apache.commons.graph.weight.primitive.DoubleWeight;
import org.junit.Test;
public final class AStarTestCase
@@ -95,8 +96,8 @@ public final class AStarTestCase
// expected path
- InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge> expected =
- new InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge>( start, goal );
+ InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge, Double> expected =
+ new InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge, Double>( start, goal, new DoubleWeight() );
expected.addConnectionInTail( start, new BaseLabeledWeightedEdge( "start <-> a", 1.5D ), a );
expected.addConnectionInTail( a, new BaseLabeledWeightedEdge( "a <-> b", 2D ), b );
Modified: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/BellmannFordTestCase.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/BellmannFordTestCase.java?rev=1228934&r1=1228933&r2=1228934&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/BellmannFordTestCase.java (original)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/BellmannFordTestCase.java Sun Jan 8 19:42:51 2012
@@ -27,6 +27,7 @@ import org.apache.commons.graph.model.Ba
import org.apache.commons.graph.model.BaseLabeledWeightedEdge;
import org.apache.commons.graph.model.DirectedMutableWeightedGraph;
import org.apache.commons.graph.model.InMemoryWeightedPath;
+import org.apache.commons.graph.weight.primitive.DoubleWeight;
import org.junit.Test;
public final class BellmannFordTestCase
@@ -71,13 +72,13 @@ public final class BellmannFordTestCase
graph.addEdge( five, new BaseLabeledWeightedEdge( "5 -> 1", 2D ), one );
// the expected weighted path
- InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge> expected =
- new InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge>( one, three );
+ InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge, Double> expected =
+ new InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge, Double>( one, three, new DoubleWeight() );
expected.addConnectionInTail( one, new BaseLabeledWeightedEdge( "1 -> 4", 7D ), four );
expected.addConnectionInTail( four, new BaseLabeledWeightedEdge( "4 -> 3", -3D ), three );
// the actual weighted path
- AllVertexPairsShortestPath<BaseLabeledVertex, BaseLabeledWeightedEdge> allVertexPairsShortestPath =
+ AllVertexPairsShortestPath<BaseLabeledVertex, BaseLabeledWeightedEdge, Double> allVertexPairsShortestPath =
findShortestPath( graph, one );
WeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge, Double> actual =
Modified: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/DijkstraTestCase.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/DijkstraTestCase.java?rev=1228934&r1=1228933&r2=1228934&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/DijkstraTestCase.java (original)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/DijkstraTestCase.java Sun Jan 8 19:42:51 2012
@@ -27,6 +27,7 @@ import org.apache.commons.graph.model.Ba
import org.apache.commons.graph.model.BaseLabeledWeightedEdge;
import org.apache.commons.graph.model.DirectedMutableWeightedGraph;
import org.apache.commons.graph.model.InMemoryWeightedPath;
+import org.apache.commons.graph.weight.primitive.DoubleWeight;
import org.junit.Test;
public final class DijkstraTestCase
@@ -73,8 +74,8 @@ public final class DijkstraTestCase
// expected path
- InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge> expected =
- new InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge>( one, five );
+ InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge, Double> expected =
+ new InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge, Double>( one, five, new DoubleWeight() );
expected.addConnectionInTail( one, new BaseLabeledWeightedEdge( "1 -> 3", 9D ), three );
expected.addConnectionInTail( three, new BaseLabeledWeightedEdge( "3 -> 6", 2D ), six );
Modified: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/FloydWarshallTestCase.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/FloydWarshallTestCase.java?rev=1228934&r1=1228933&r2=1228934&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/FloydWarshallTestCase.java (original)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/FloydWarshallTestCase.java Sun Jan 8 19:42:51 2012
@@ -20,6 +20,7 @@ package org.apache.commons.graph.shortes
*/
import static junit.framework.Assert.assertEquals;
+import static junit.framework.Assert.assertFalse;
import static junit.framework.Assert.fail;
import static org.apache.commons.graph.shortestpath.FloydWarshall.findAllVertexPairsShortestPath;
@@ -32,6 +33,7 @@ import org.apache.commons.graph.model.Ba
import org.apache.commons.graph.model.DirectedMutableWeightedGraph;
import org.apache.commons.graph.model.InMemoryWeightedPath;
import org.apache.commons.graph.model.UndirectedMutableWeightedGraph;
+import org.apache.commons.graph.weight.primitive.DoubleWeight;
import org.junit.Test;
/**
@@ -86,7 +88,7 @@ public class FloydWarshallTestCase
mutable.addEdge( four, new BaseLabeledWeightedEdge( "4 -> 5", 6D ), five );
mutable.addEdge( six, new BaseLabeledWeightedEdge( "6 -> 5", 9D ), five );
- AllVertexPairsShortestPath<BaseLabeledVertex, BaseLabeledWeightedEdge> p =
+ AllVertexPairsShortestPath<BaseLabeledVertex, BaseLabeledWeightedEdge, Double> p =
findAllVertexPairsShortestPath( weighted );
if ( weighted instanceof UndirectedGraph )
@@ -107,8 +109,8 @@ public class FloydWarshallTestCase
WeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge, Double> wp = p.findShortestPath( one, six );
// Expected
- InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge> expected =
- new InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge>( one, six );
+ InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge, Double> expected =
+ new InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge, Double>( one, six, new DoubleWeight() );
expected.addConnectionInTail( one, new BaseLabeledWeightedEdge( "1 -> 3", 9D ), three );
expected.addConnectionInTail( three, new BaseLabeledWeightedEdge( "3 -> 6", 2D ), six );
@@ -122,7 +124,7 @@ public class FloydWarshallTestCase
assertEquals( 6D, p.getShortestDistance( four, five ) );
assertEquals( 20D, p.getShortestDistance( one, five ) );
- assertEquals( Double.POSITIVE_INFINITY, p.getShortestDistance( five, one ) );
+ assertFalse( p.hasShortestDistance( five, one ) );
WeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge, Double> wp;
// Verify shortest paths
@@ -135,8 +137,8 @@ public class FloydWarshallTestCase
// wallow it
}
- InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge> expected =
- new InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge>( one, six );
+ InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge, Double> expected =
+ new InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge, Double>( one, six, new DoubleWeight() );
expected.addConnectionInTail( one, new BaseLabeledWeightedEdge( "1 -> 3", 9D ), three );
expected.addConnectionInTail( three, new BaseLabeledWeightedEdge( "3 -> 6", 2D ), six );
Modified: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/KruskalTestCase.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/KruskalTestCase.java?rev=1228934&r1=1228933&r2=1228934&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/KruskalTestCase.java (original)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/spanning/KruskalTestCase.java Sun Jan 8 19:42:51 2012
@@ -95,7 +95,7 @@ public final class KruskalTestCase
// Actual
SpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge> actual = minimumSpanningTree( input );
-
+
// assert!
assertEquals( expected, actual );