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 2011/06/21 16:16:39 UTC
svn commit: r1138014 - in
/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath:
Dijkstra.java PredecessorsList.java
Author: simonetripodi
Date: Tue Jun 21 14:16:38 2011
New Revision: 1138014
URL: http://svn.apache.org/viewvc?rev=1138014&view=rev
Log:
first checkin of PredecessorsList class, it will be reused by other shortest path algorithms
Added:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PredecessorsList.java (with props)
Modified:
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/Dijkstra.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/Dijkstra.java?rev=1138014&r1=1138013&r2=1138014&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:16:38 2011
@@ -22,9 +22,7 @@ package org.apache.commons.graph.shortes
import static java.lang.String.format;
import static org.apache.commons.graph.utils.Edges.getConnectedVertex;
-import java.util.HashMap;
import java.util.HashSet;
-import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;
@@ -33,7 +31,6 @@ 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.model.InMemoryWeightedPath;
/**
* Contains the Dijkstra's shortest path algorithm implementation.
@@ -73,7 +70,7 @@ public final class Dijkstra
final Set<V> settledNodes = new HashSet<V>();
- final Map<V, WE> predecessors = new HashMap<V, WE>();
+ final PredecessorsList<V, WE> predecessors = new PredecessorsList<V, WE>();
// the current node
V vertex;
@@ -84,20 +81,7 @@ public final class Dijkstra
// destination reached, stop and build the path
if ( target.equals( vertex ) )
{
- InMemoryWeightedPath<V, WE> path =
- new InMemoryWeightedPath<V, WE>( source, target, shortestDistances.get( target ) );
-
- while ( !source.equals( vertex ) )
- {
- WE edge = predecessors.get( vertex );
-
- path.addEdgeInHead( edge );
- path.addVertexInHead( vertex );
-
- vertex = edge.getHead();
- }
-
- return path;
+ return predecessors.buildPath( source, target, shortestDistances.get( target ) );
}
settledNodes.add( vertex );
@@ -121,7 +105,7 @@ public final class Dijkstra
unsettledNodes.add( v );
// assign predecessor in shortest path
- predecessors.put( v, edge );
+ predecessors.addPredecessor( v, edge );
}
}
}
Added: 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=1138014&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PredecessorsList.java (added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PredecessorsList.java Tue Jun 21 14:16:38 2011
@@ -0,0 +1,83 @@
+package org.apache.commons.graph.shortestpath;
+
+/*
+ * 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 static org.apache.commons.graph.utils.Edges.getConnectedVertex;
+
+import java.util.HashMap;
+import java.util.Map;
+
+import org.apache.commons.graph.Edge;
+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;
+
+/**
+ * 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
+ */
+final class PredecessorsList<V extends Vertex, WE extends WeightedEdge<V>>
+{
+
+ final Map<V, WE> predecessors = new HashMap<V, WE>();
+
+ /**
+ * Add an {@link Edge} in the predecessor list associated to the input {@link Vertex}.
+ *
+ * @param vertex the predecessor vertex
+ * @param edge the edge that succeeds to the input vertex
+ */
+ public void addPredecessor( V vertex, WE edge )
+ {
+ predecessors.put( vertex, edge );
+ }
+
+ /**
+ * Build a {@link WeightedPath} instance related to source-target path.
+ *
+ * @param source the path source vertex
+ * @param target the path target vertex
+ * @param cost the path cost
+ * @return the weighted path related to source to target
+ */
+ public WeightedPath<V, WE> buildPath( V source, V target, Double cost )
+ {
+ InMemoryWeightedPath<V, WE> path =
+ new InMemoryWeightedPath<V, WE>( source, target, cost );
+
+ V vertex = target;
+ while ( !source.equals( vertex ) )
+ {
+ WE edge = predecessors.get( vertex );
+
+ path.addEdgeInHead( edge );
+ path.addVertexInHead( vertex );
+
+ vertex = getConnectedVertex( vertex, edge );
+ }
+
+ return path;
+ }
+
+}
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PredecessorsList.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PredecessorsList.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PredecessorsList.java
------------------------------------------------------------------------------
svn:mime-type = text/plain