commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From simonetrip...@apache.org
Subject svn commit: r1138014 - in /commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath: Dijkstra.java PredecessorsList.java
Date Tue, 21 Jun 2011 14:16:39 GMT
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



Mime
View raw message