Author: simonetripodi
Date: Tue Jun 21 14:24:34 2011
New Revision: 1138016
URL: http://svn.apache.org/viewvc?rev=1138016&view=rev
Log:
used the object adapter pattern to implement the ShortestDistance in order to
expose more intuitive APIs
Modified:
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/ShortestDistances.java
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=1138016&r1=1138015&r2=1138016&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
Tue Jun 21 14:24:34 2011
@@ -62,7 +62,7 @@ public final class Dijkstra
V target )
{
final ShortestDistances<V> shortestDistances = new
ShortestDistances<V>();
- shortestDistances.put( source, 0D );
+ shortestDistances.setWeight( source, 0D );
final PriorityQueue<V> unsettledNodes =
new PriorityQueue<V>( graph.getVertices().size(),
shortestDistances );
@@ -81,7 +81,7 @@ public final class Dijkstra
// destination reached, stop and build the path
if ( target.equals( vertex ) )
{
- return predecessors.buildPath( source, target,
shortestDistances.get( target ) );
+ return predecessors.buildPath( source, target,
shortestDistances.getWeight( target ) );
}
settledNodes.add( vertex );
@@ -96,12 +96,12 @@ public final class Dijkstra
// skip node already settled
if ( !settledNodes.contains( v ) )
{
- Double shortDist = shortestDistances.get( vertex ) +
edge.getWeight();
+ Double shortDist = shortestDistances.getWeight( vertex ) +
edge.getWeight();
- if ( shortDist.compareTo( shortestDistances.get( v ) ) < 0
)
+ if ( shortDist.compareTo( shortestDistances.getWeight( v )
) < 0 )
{
// assign new shortest distance and mark unsettled
- shortestDistances.put( v, shortDist );
+ shortestDistances.setWeight( v, shortDist );
unsettledNodes.add( v );
// assign predecessor in shortest path
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=1138016&r1=1138015&r2=1138016&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
Tue Jun 21 14:24:34 2011
@@ -21,24 +21,45 @@ package org.apache.commons.graph.shortes
import java.util.Comparator;
import java.util.HashMap;
+import java.util.Map;
import org.apache.commons.graph.Vertex;
final class ShortestDistances<V extends Vertex>
- extends HashMap<V, Double>
implements Comparator<V>
{
private static final long serialVersionUID = 568538689459177637L;
+ private final Map<V, Double> distances = new HashMap<V, Double>();
+
/**
- * {@inheritDoc}
+ * Returns the distance related to input vertex, or {@code INFINITY} if it
wasn't previously visited.
+ *
+ * @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.
+ */
+ public Double getWeight( V vertex )
+ {
+ Double distance = distances.get( vertex );
+
+ if ( distance == null )
+ {
+ return Double.POSITIVE_INFINITY;
+ }
+
+ return distance;
+ }
+
+ /**
+ * Update the input vertex distance.
+ *
+ * @param vertex the vertex for which the distance has to be updated
+ * @param distance the new input vertex distance
*/
- @Override
- public Double get( Object key )
+ public void setWeight( V vertex, Double distance )
{
- Double distance = super.get( key );
- return (distance == null) ? Double.POSITIVE_INFINITY : distance;
+ distances.put( vertex, distance );
}
/**
@@ -46,7 +67,7 @@ final class ShortestDistances<V extends
*/
public int compare( V left, V right )
{
- return get( left ).compareTo( get( right ) );
+ return getWeight( left ).compareTo( getWeight( right ) );
}
}
