svn commit: r1146053 - in /commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath: AStar.java Dijkstra.java

[simonetripodi]

Author: simonetripodi
Date: Wed Jul 13 14:25:24 2011
New Revision: 1146053

URL: http://svn.apache.org/viewvc?rev=1146053&view=rev
Log:
A+ and Dijkstra algorithms now use the Fibonacci Heap instead of the Binary Heap

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/Dijkstra.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=1146053&r1=1146052&r2=1146053&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
 Wed Jul 13 14:25:24 2011
@@ -20,7 +20,7 @@ package org.apache.commons.graph.shortes
  */
 
 import java.util.HashSet;
-import java.util.PriorityQueue;
+import java.util.Queue;
 import java.util.Set;
 
 import org.apache.commons.graph.DirectedGraph;
@@ -28,6 +28,7 @@ import org.apache.commons.graph.Vertex;
 import org.apache.commons.graph.WeightedEdge;
 import org.apache.commons.graph.WeightedGraph;
 import org.apache.commons.graph.WeightedPath;
+import org.apache.commons.graph.collections.FibonacciHeap;
 
 /**
  * Contains the A* shortest path algorithm implementation.
@@ -72,7 +73,7 @@ public final class AStar
         final Set<V> closedSet = new HashSet<V>();
 
         // The set of tentative nodes to be evaluated.
-        final PriorityQueue<V> openSet = new PriorityQueue<V>( 
graph.getOrder(), fScores );
+        final Queue<V> openSet = new FibonacciHeap<V>( fScores );
         openSet.add( start );
 
         // The of navigated nodes

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=1146053&r1=1146052&r2=1146053&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
 Wed Jul 13 14:25:24 2011
@@ -20,7 +20,7 @@ package org.apache.commons.graph.shortes
  */
 
 import java.util.HashSet;
-import java.util.PriorityQueue;
+import java.util.Queue;
 import java.util.Set;
 
 import org.apache.commons.graph.DirectedGraph;
@@ -28,6 +28,7 @@ import org.apache.commons.graph.Vertex;
 import org.apache.commons.graph.WeightedEdge;
 import org.apache.commons.graph.WeightedGraph;
 import org.apache.commons.graph.WeightedPath;
+import org.apache.commons.graph.collections.FibonacciHeap;
 
 /**
  * Contains the Dijkstra's shortest path algorithm implementation.
@@ -61,7 +62,7 @@ public final class Dijkstra
         final ShortestDistances<V> shortestDistances = new 
ShortestDistances<V>();
         shortestDistances.setWeight( source, 0D );
 
-        final PriorityQueue<V> unsettledNodes = new PriorityQueue<V>( 
graph.getOrder(), shortestDistances );
+        final Queue<V> unsettledNodes = new FibonacciHeap<V>( 
shortestDistances );
         unsettledNodes.add( source );
 
         final Set<V> settledNodes = new HashSet<V>();