Return-Path: 
 <commits-return-24727-apmail-commons-commits-archive=commons.apache.org@commons.apache.org>
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 A38BEBEBD
	for <apmail-commons-commits-archive@minotaur.apache.org>;
 Tue, 10 Jan 2012 21:30:59 +0000 (UTC)
Received: (qmail 50880 invoked by uid 500); 10 Jan 2012 21:30:58 -0000
Delivered-To: apmail-commons-commits-archive@commons.apache.org
Received: (qmail 50769 invoked by uid 500); 10 Jan 2012 21:30:57 -0000
Mailing-List: contact commits-help@commons.apache.org; run by ezmlm
Precedence: bulk
List-Help: <mailto:commits-help@commons.apache.org>
List-Unsubscribe: <mailto:commits-unsubscribe@commons.apache.org>
List-Post: <mailto:commits@commons.apache.org>
List-Id: <commits.commons.apache.org>
Reply-To: dev@commons.apache.org
Delivered-To: mailing list commits@commons.apache.org
Received: (qmail 50762 invoked by uid 99); 10 Jan 2012 21:30:57 -0000
Received: from athena.apache.org (HELO athena.apache.org) (140.211.11.136)
    by apache.org (qpsmtpd/0.29) with ESMTP; Tue, 10 Jan 2012 21:30:57 +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; Tue, 10 Jan 2012 21:30:56 +0000
Received: from eris.apache.org (localhost [127.0.0.1])
	by eris.apache.org (Postfix) with ESMTP id AB8182388ACC
	for <commits@commons.apache.org>; Tue, 10 Jan 2012 21:30:35 +0000 (UTC)
Content-Type: text/plain; charset="utf-8"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Subject: svn commit: r1229746 - in /commons/sandbox/graph/trunk/src:
 main/java/org/apache/commons/graph/shortestpath/AStar.java
 main/java/org/apache/commons/graph/shortestpath/Heuristic.java
 test/java/org/apache/commons/graph/shortestpath/AStarTestCase.java
Date: Tue, 10 Jan 2012 21:30:35 -0000
To: commits@commons.apache.org
From: simonetripodi@apache.org
X-Mailer: svnmailer-1.0.8-patched
Message-Id: <20120110213035.AB8182388ACC@eris.apache.org>

Author: simonetripodi
Date: Tue Jan 10 21:30:35 2012
New Revision: 1229746

URL: http://svn.apache.org/viewvc?rev=1229746&view=rev
Log:
applied GenericWeightTypeAlsoForAStar.patch submitted by Claudio Squarcella

Modified:
    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/Heuristic.java
    commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/AStarTestCase.java

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=1229746&r1=1229745&r2=1229746&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 Tue Jan 10 21:30:35 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.OrderedMonoid;
 import org.apache.commons.graph.weight.primitive.DoubleWeight;
 
 /**
@@ -37,8 +38,6 @@ import org.apache.commons.graph.weight.p
 public final class AStar
 {
 
-    private static final DoubleWeight DOUBLE_WEIGHT = new DoubleWeight();
-
     /**
      * This class can not be instantiated directly
      */
@@ -50,26 +49,29 @@ public final class AStar
     /**
      * Applies the classical A* 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 <W> the weight type
      * @param graph the Graph which shortest path from {@code source} to {@code target} has to be found
      * @param start the shortest path source Vertex
      * @param goal the shortest path target Vertex
      * @param heuristic the <i>h(x)</i> function
+     * @param orderedMonoid the ordered monoid 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>> WeightedPath<V, WE, Double> findShortestPath( Graph<V, WE> graph,
-                                                                                                                    V start,
-                                                                                                                    V goal,
-                                                                                                                    Heuristic<V> heuristic )
+    public static <V extends Vertex, W, WE extends WeightedEdge<W>> WeightedPath<V, WE, W> findShortestPath( Graph<V, WE> graph,
+                                                                                                             V start,
+                                                                                                             V goal,
+                                                                                                             Heuristic<V, W> heuristic,
+                                                                                                             OrderedMonoid<W> orderedMonoid )
     {
         // Cost from start along best known path.
-        final ShortestDistances<V, Double> gScores = new ShortestDistances<V, Double>( DOUBLE_WEIGHT );
-        gScores.setWeight( start, 0D );
+        final ShortestDistances<V, W> gScores = new ShortestDistances<V, W>( orderedMonoid );
+        gScores.setWeight( start, orderedMonoid.zero() );
 
         // Estimated total cost from start to goal through y.
-        final ShortestDistances<V, Double> fScores = new ShortestDistances<V, Double>( DOUBLE_WEIGHT );
-        Double hScore = heuristic.applyHeuristic( start, goal );
+        final ShortestDistances<V, W> fScores = new ShortestDistances<V, W>( orderedMonoid );
+        W hScore = heuristic.applyHeuristic( start, goal );
         fScores.setWeight( start, hScore );
 
         // The set of nodes already evaluated.
@@ -80,7 +82,7 @@ public final class AStar
         openSet.add( start );
 
         // The of navigated nodes
-        final PredecessorsList<V, WE, Double> predecessors = new PredecessorsList<V, WE, Double>( graph, DOUBLE_WEIGHT );
+        final PredecessorsList<V, WE, W> predecessors = new PredecessorsList<V, WE, W>( graph, orderedMonoid );
 
         // extract the node in openset having the lowest f_score[] value
         while ( !openSet.isEmpty() )
@@ -103,15 +105,15 @@ public final class AStar
                 {
                     WE edge = graph.getEdge( current, v );
                     // note that the weight of current can never be undefined
-                    Double tentativeGScore = gScores.getWeight( current ) + edge.getWeight();
+                    W tentativeGScore = orderedMonoid.append( 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 )
+                    if ( openSet.add( v ) || orderedMonoid.compare( tentativeGScore, gScores.getWeight( v ) ) < 0 )
                     {
                         predecessors.addPredecessor( v, current );
                         gScores.setWeight( v, tentativeGScore );
                         hScore = heuristic.applyHeuristic( v, goal );
-                        fScores.setWeight( v, gScores.getWeight( v ) + hScore );
+                        fScores.setWeight( v, orderedMonoid.append( gScores.getWeight( v ), hScore ) );
                     }
                 }
             }
@@ -119,5 +121,25 @@ public final class AStar
 
         throw new PathNotFoundException( "Path from '%s' to '%s' doesn't exist in Graph '%s'", start, goal, graph );
     }
+    
+    /**
+     * Applies the classical A* 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 graph the Graph which shortest path from {@code source} to {@code target} has to be found
+     * @param start the shortest path source Vertex
+     * @param goal the shortest path target Vertex
+     * @param heuristic the <i>h(x)</i> function
+     * @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>> WeightedPath<V, WE, Double> findShortestPath( Graph<V, WE> graph,
+                                                                                                                    V start,
+                                                                                                                    V goal,
+                                                                                                                    Heuristic<V, Double> heuristic )
+    {
+        return findShortestPath( graph, start, goal, heuristic, new DoubleWeight() );
+    }
 
 }

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/Heuristic.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/Heuristic.java?rev=1229746&r1=1229745&r2=1229746&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/Heuristic.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/Heuristic.java Tue Jan 10 21:30:35 2012
@@ -25,9 +25,10 @@ import org.apache.commons.graph.Vertex;
  * An {@link Heuristic} instance is an admissible "heuristic estimate" of the distance to the goal
  * (usually denoted <i>h(x)</i>).
  *
- * @param <V> the Graph vertices type.
+ * @param <V> the Graph vertices type
+ * @param <W> the weight type
  */
-public interface Heuristic<V extends Vertex>
+public interface Heuristic<V extends Vertex, W>
 {
 
     /**
@@ -37,6 +38,6 @@ public interface Heuristic<V extends Ver
      * @param goal the goal of the Graph visit.
      * @return the "heuristic estimate" of the distance from the start to the goal.
      */
-    Double applyHeuristic( V current, V goal );
+    W applyHeuristic( V current, V goal );
 
 }

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=1229746&r1=1229745&r2=1229746&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 Tue Jan 10 21:30:35 2012
@@ -84,7 +84,7 @@ public final class AStarTestCase
         heuristics.put( e, 2D );
         heuristics.put( goal, 6D );
 
-        Heuristic<BaseLabeledVertex> heuristic = new Heuristic<BaseLabeledVertex>()
+        Heuristic<BaseLabeledVertex, Double> heuristic = new Heuristic<BaseLabeledVertex, Double>()
         {
 
             public Double applyHeuristic( BaseLabeledVertex current, BaseLabeledVertex goal )