Return-Path: X-Original-To: apmail-commons-commits-archive@minotaur.apache.org Delivered-To: apmail-commons-commits-archive@minotaur.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id DDEF9BA29 for ; Sun, 8 Jan 2012 19:43:27 +0000 (UTC) Received: (qmail 3632 invoked by uid 500); 8 Jan 2012 19:43:27 -0000 Delivered-To: apmail-commons-commits-archive@commons.apache.org Received: (qmail 3542 invoked by uid 500); 8 Jan 2012 19:43:26 -0000 Mailing-List: contact commits-help@commons.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@commons.apache.org Delivered-To: mailing list commits@commons.apache.org Received: (qmail 3535 invoked by uid 99); 8 Jan 2012 19:43:25 -0000 Received: from nike.apache.org (HELO nike.apache.org) (192.87.106.230) by apache.org (qpsmtpd/0.29) with ESMTP; Sun, 08 Jan 2012 19:43:25 +0000 X-ASF-Spam-Status: No, hits=-2000.0 required=5.0 tests=ALL_TRUSTED X-Spam-Check-By: apache.org Received: from [140.211.11.4] (HELO eris.apache.org) (140.211.11.4) by apache.org (qpsmtpd/0.29) with ESMTP; Sun, 08 Jan 2012 19:43:16 +0000 Received: from eris.apache.org (localhost [127.0.0.1]) by eris.apache.org (Postfix) with ESMTP id 647A82388900 for ; Sun, 8 Jan 2012 19:42:53 +0000 (UTC) Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Subject: 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... Date: Sun, 08 Jan 2012 19:42:52 -0000 To: commits@commons.apache.org From: simonetripodi@apache.org X-Mailer: svnmailer-1.0.8-patched Message-Id: <20120108194253.647A82388900@eris.apache.org> X-Virus-Checked: Checked by ClamAV on apache.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 @@ + + Generic weight types and updated shortest path implementations - patch provided by Claudio Squarcella + DotExporter only exports weights that extend Number - patch provided by Claudio Squarcella 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 * * @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 the weight type */ public interface WeightedEdge extends Edge, Weighted, Comparable> 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 the Graph vertices type * @param the Graph weighted edges type + * @param the weight type */ -public final class InMemoryWeightedPath> +public final class InMemoryWeightedPath, W> extends InMemoryPath - implements WeightedPath + implements WeightedPath { - private Double weigth = 0D; + private W weight; + private Monoid monoid; - public InMemoryWeightedPath( V start, V target ) + public InMemoryWeightedPath( V start, V target, Monoid 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> other = (InMemoryWeightedPath>) obj; - if ( !weigth.equals( other.getWeight() ) ) + InMemoryWeightedPath, W> other = (InMemoryWeightedPath, 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 heuristic ) { // Cost from start along best known path. - final ShortestDistances gScores = new ShortestDistances(); + final ShortestDistances gScores = new ShortestDistances( DOUBLE_WEIGHT ); gScores.setWeight( start, 0D ); // Estimated total cost from start to goal through y. - final ShortestDistances fScores = new ShortestDistances(); + final ShortestDistances fScores = new ShortestDistances( 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 predecessors = new PredecessorsList( graph ); + final PredecessorsList predecessors = new PredecessorsList( 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 the Graph vertices type - * @param the Graph edges type + * @param the Graph weighted edges type + * @param the weight type */ -public final class AllVertexPairsShortestPath> +public final class AllVertexPairsShortestPath, W> { - private final Map, WeightedPath> paths = new HashMap, WeightedPath>(); + private final Map, WeightedPath> paths = new HashMap, WeightedPath>(); - private final Map, Double> shortestDistances = new HashMap, Double>(); + private final Map, W> shortestDistances = new HashMap, W>(); + + private final OrderedMonoid orderedMonoid; /** * Constructor visible only inside the package */ - AllVertexPairsShortestPath() + AllVertexPairsShortestPath( OrderedMonoid 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 weightedPath ) + void addShortestPath( V source, V target, WeightedPath 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 findShortestPath( V source, V target ) + public WeightedPath 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 path = paths.get( new VertexPair( source, target ) ); + WeightedPath path = paths.get( new VertexPair( 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( source, target ) ); + return shortestDistances.get( new VertexPair( 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( 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 the Graph vertices type. + * @param the Graph vertices type * @param the Graph weighted edges type - * @param graph the Graph which shortest path from {@code source} to {@code target} has to be found + * @param the weight type + * @param 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 , G extends DirectedGraph> AllVertexPairsShortestPath findShortestPath( G graph, - V source) + public static , G extends DirectedGraph> AllVertexPairsShortestPath findShortestPath( G graph, + V source, + OrderedMonoid orderedMonoid ) { - final ShortestDistances shortestDistances = new ShortestDistances(); - shortestDistances.setWeight( source, 0D ); + final ShortestDistances shortestDistances = new ShortestDistances( orderedMonoid ); + shortestDistances.setWeight( source, orderedMonoid.zero() ); - final PredecessorsList predecessors = new PredecessorsList( graph ); + final PredecessorsList predecessors = new PredecessorsList( 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 allVertexPairsShortestPath = new AllVertexPairsShortestPath(); + AllVertexPairsShortestPath allVertexPairsShortestPath = new AllVertexPairsShortestPath( orderedMonoid ); for ( V target : graph.getVertices() ) { if ( !source.equals( target ) ) { - WeightedPath weightedPath = predecessors.buildPath( source, target ); + WeightedPath 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 the Graph vertices type + * @param the Graph weighted edges type + * @param 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 , G extends DirectedGraph> AllVertexPairsShortestPath 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 the Graph vertices type. + * @param the Graph vertices type + * @param the weight type * @param the Graph weighted edges type - * @param graph the Graph which shortest path from {@code source} to {@code target} has to be found + * @param 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 , G extends DirectedGraph> WeightedPath findShortestPath( G graph, - V source, - V target ) + public static , G extends DirectedGraph> WeightedPath findShortestPath( G graph, + V source, + V target, + OrderedMonoid orderedMonoid ) { - final ShortestDistances shortestDistances = new ShortestDistances(); - shortestDistances.setWeight( source, 0D ); + final ShortestDistances shortestDistances = new ShortestDistances( orderedMonoid ); + shortestDistances.setWeight( source, orderedMonoid.zero() ); final Queue unsettledNodes = new FibonacciHeap( shortestDistances ); unsettledNodes.add( source ); final Set settledNodes = new HashSet(); - final PredecessorsList predecessors = new PredecessorsList( graph ); + final PredecessorsList predecessors = new PredecessorsList( 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 the Graph vertices type + * @param the Graph weighted edges type + * @param 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 , G extends DirectedGraph> WeightedPath 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 the Graph vertices type. * @param the Graph weighted edges type + * @param 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 > AllVertexPairsShortestPath findAllVertexPairsShortestPath( Graph graph ) + public static > AllVertexPairsShortestPath findAllVertexPairsShortestPath( Graph graph, OrderedMonoid orderedMonoid ) { - AllVertexPairsShortestPath shortesPaths = new AllVertexPairsShortestPath(); + AllVertexPairsShortestPath shortestPaths = new AllVertexPairsShortestPath( orderedMonoid ); Map, V> next = new HashMap, V>(); // init for ( WE we : graph.getEdges() ) { VertexPair 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( i, j ), k ); + // store the intermediate vertex + next.put( new VertexPair( i, j ), k ); + } } + } } } @@ -94,25 +103,39 @@ public final class FloydWarshall { if ( !source.equals( target ) ) { - PredecessorsList predecessorsList = new PredecessorsList( graph ); + PredecessorsList predecessorsList = new PredecessorsList( graph, orderedMonoid ); pathReconstruction( predecessorsList, source, target, next, graph ); if ( !predecessorsList.isEmpty() ) { - WeightedPath weightedPath = predecessorsList.buildPath( source, target ); + WeightedPath 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 the Graph vertices type. + * @param the Graph weighted edges type + * @param graph the input graph + * @return a data structure which contains all vertex pairs shortest path. + */ + public static > AllVertexPairsShortestPath findAllVertexPairsShortestPath( Graph graph ) + { + return findAllVertexPairsShortestPath( graph, new DoubleWeight() ); } - private static > void pathReconstruction( PredecessorsList path, + private static , W> void pathReconstruction( PredecessorsList path, V source, V target, Map, V> next, Graph 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 the Graph vertices type - * @param the Graph edges type + * @param the Graph weighted edges type + * @param the weight type */ -final class PredecessorsList> +final class PredecessorsList, W> { private final Graph graph; + + private final Monoid monoid; private final Map predecessors = new HashMap(); - public PredecessorsList(Graph graph ) + public PredecessorsList( Graph graph, Monoid monoid ) { this.graph = graph; + this.monoid = monoid; } /** @@ -67,9 +71,9 @@ final class PredecessorsList buildPath( V source, V target ) + public WeightedPath buildPath( V source, V target ) { - InMemoryWeightedPath path = new InMemoryWeightedPath( source, target ); + InMemoryWeightedPath path = new InMemoryWeightedPath( 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 the Graph vertices type + * @param the weight type */ -final class ShortestDistances +final class ShortestDistances implements Comparator { private static final long serialVersionUID = 568538689459177637L; - private final Map distances = new HashMap(); + private final Map distances = new HashMap(); + + private final OrderedMonoid orderedMonoid; + + public ShortestDistances( OrderedMonoid 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. + * + * NOTE: 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 the type of the elements in the {@link Monoid} + */ +public interface Monoid + extends Zero, Semigroup +{ + +} 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 the type of the elements in the {@link OrderedMonoid} + */ +public interface OrderedMonoid + extends Monoid, Comparator +{ + +} 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 the type of the elements in the {@link Semigroup} + */ +public interface Semigroup +{ + + /** + * 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 the type of the identity value + */ +public interface Zero +{ + + /** + * 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 +{ + + /** + * {@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 +{ + + /** + * {@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 expected = - new InMemoryWeightedPath( start, goal ); + InMemoryWeightedPath expected = + new InMemoryWeightedPath( 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 expected = - new InMemoryWeightedPath( one, three ); + InMemoryWeightedPath expected = + new InMemoryWeightedPath( 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 allVertexPairsShortestPath = + AllVertexPairsShortestPath allVertexPairsShortestPath = findShortestPath( graph, one ); WeightedPath 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 expected = - new InMemoryWeightedPath( one, five ); + InMemoryWeightedPath expected = + new InMemoryWeightedPath( 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 p = + AllVertexPairsShortestPath p = findAllVertexPairsShortestPath( weighted ); if ( weighted instanceof UndirectedGraph ) @@ -107,8 +109,8 @@ public class FloydWarshallTestCase WeightedPath wp = p.findShortestPath( one, six ); // Expected - InMemoryWeightedPath expected = - new InMemoryWeightedPath( one, six ); + InMemoryWeightedPath expected = + new InMemoryWeightedPath( 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 wp; // Verify shortest paths @@ -135,8 +137,8 @@ public class FloydWarshallTestCase // wallow it } - InMemoryWeightedPath expected = - new InMemoryWeightedPath( one, six ); + InMemoryWeightedPath expected = + new InMemoryWeightedPath( 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 actual = minimumSpanningTree( input ); - + // assert! assertEquals( expected, actual );