commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From simonetrip...@apache.org
Subject svn commit: r1135807 - in /commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath: ./ Dijkstra.java PathNotFoundException.java ShortestDistanceComparator.java ShortestDistances.java
Date Tue, 14 Jun 2011 21:37:35 GMT
Author: simonetripodi
Date: Tue Jun 14 21:37:34 2011
New Revision: 1135807

URL: http://svn.apache.org/viewvc?rev=1135807&view=rev
Log:
first checkin of a prototypal version of Dijkstra's shortest path algorithm
TODO return a Path implementation

Added:
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/Dijkstra.java
  (with props)
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PathNotFoundException.java
  (with props)
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/ShortestDistanceComparator.java
  (with props)
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/ShortestDistances.java
  (with props)

Added: 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=1135807&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/Dijkstra.java
(added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/Dijkstra.java
Tue Jun 14 21:37:34 2011
@@ -0,0 +1,116 @@
+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 java.lang.String.format;
+
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Map;
+import java.util.PriorityQueue;
+import java.util.Set;
+
+import org.apache.commons.graph.Vertex;
+import org.apache.commons.graph.WeightedEdge;
+import org.apache.commons.graph.WeightedGraph;
+import org.apache.commons.graph.WeightedPath;
+
+/**
+ * 
+ */
+public final class Dijkstra
+{
+
+    /**
+     * This class can not be instantiated directly
+     */
+    private Dijkstra()
+    {
+        // do nothing
+    }
+
+    /**
+     * Applies the classical Dijkstra algorithm to find the shortest path from the source
to the target, if exists.
+     *
+     * @param <V>
+     * @param <WE>
+     * @param graph
+     * @param source
+     * @param target
+     * @return
+     */
+    public static <V extends Vertex, WE extends WeightedEdge<V>> WeightedPath<V,
WE> findShortestPath( WeightedGraph<V, WE> graph,
+                                                                                        
              V source,
+                                                                                        
              V target )
+    {
+        final ShortestDistances<V> shortestDistances = new ShortestDistances<V>();
+
+        final PriorityQueue<V> unsettledNodes =
+            new PriorityQueue<V>( graph.getVertices().size(), new ShortestDistanceComparator<V>(
shortestDistances ) );
+        unsettledNodes.add( source );
+
+        final Set<V> settledNodes = new HashSet<V>();
+
+        final Map<V, V> predecessors = new HashMap<V, V>();
+
+        // the current node
+        V vertex;
+
+        // extract the node with the shortest distance
+        while ( ( vertex = unsettledNodes.poll() ) != null )
+        {
+            assert !settledNodes.contains( vertex );
+
+            // destination reached, stop
+            if ( target == vertex )
+            {
+                // TODO return a WeightedPath instance
+                break;
+            }
+
+            settledNodes.add( vertex );
+
+            for ( WE edge : graph.getEdges( vertex ) )
+            {
+                V v = edge.getTail();
+
+                // skip node already settled
+                if ( !settledNodes.contains( v ) )
+                {
+                    Double shortDist = shortestDistances.get( vertex ) + edge.getWeight();
+
+                    if ( shortDist < shortestDistances.get( v ) )
+                    {
+                        // assign new shortest distance and mark unsettled
+                        shortestDistances.put( v, shortDist );
+                        unsettledNodes.add( v );
+
+                        // assign predecessor in shortest path
+                        predecessors.put( v, vertex );
+                    }
+                }
+            }
+        }
+
+        throw new PathNotFoundException( format( "Path from '%s' to '%s' doesn't exist in
Graph '%s'", source, target,
+                                                 graph ) );
+    }
+
+}

Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/Dijkstra.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/Dijkstra.java
------------------------------------------------------------------------------
    svn:keywords = Date Author Id Revision HeadURL

Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/Dijkstra.java
------------------------------------------------------------------------------
    svn:mime-type = text/plain

Added: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PathNotFoundException.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PathNotFoundException.java?rev=1135807&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PathNotFoundException.java
(added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PathNotFoundException.java
Tue Jun 14 21:37:34 2011
@@ -0,0 +1,35 @@
+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 org.apache.commons.graph.GraphException;
+
+public final class PathNotFoundException
+    extends GraphException
+{
+
+    private static final long serialVersionUID = 2919520319054603708L;
+
+    public PathNotFoundException( String msg )
+    {
+        super( msg );
+    }
+
+}

Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PathNotFoundException.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PathNotFoundException.java
------------------------------------------------------------------------------
    svn:keywords = Date Author Id Revision HeadURL

Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PathNotFoundException.java
------------------------------------------------------------------------------
    svn:mime-type = text/plain

Added: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/ShortestDistanceComparator.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/ShortestDistanceComparator.java?rev=1135807&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/ShortestDistanceComparator.java
(added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/ShortestDistanceComparator.java
Tue Jun 14 21:37:34 2011
@@ -0,0 +1,50 @@
+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 java.util.Comparator;
+
+import org.apache.commons.graph.Vertex;
+
+/**
+ * 
+ *
+ * @param <V>
+ */
+final class ShortestDistanceComparator<V extends Vertex>
+    implements Comparator<V>
+{
+
+    private final ShortestDistances<V> shortestDistances;
+
+    public ShortestDistanceComparator( ShortestDistances<V> shortestDistances )
+    {
+        this.shortestDistances = shortestDistances;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public int compare( V left, V right )
+    {
+        return shortestDistances.get( left ).compareTo( shortestDistances.get( right ) );
+    }
+
+}

Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/ShortestDistanceComparator.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/ShortestDistanceComparator.java
------------------------------------------------------------------------------
    svn:keywords = Date Author Id Revision HeadURL

Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/ShortestDistanceComparator.java
------------------------------------------------------------------------------
    svn:mime-type = text/plain

Added: 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=1135807&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/ShortestDistances.java
(added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/ShortestDistances.java
Tue Jun 14 21:37:34 2011
@@ -0,0 +1,42 @@
+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 java.util.HashMap;
+
+import org.apache.commons.graph.Vertex;
+
+final class ShortestDistances<V extends Vertex>
+    extends HashMap<V, Double>
+{
+
+    private static final long serialVersionUID = 568538689459177637L;
+
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public Double get( Object key )
+    {
+        Double distance = super.get( key );
+        return (distance == null) ? Double.POSITIVE_INFINITY : distance;
+    }
+
+}

Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/ShortestDistances.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/ShortestDistances.java
------------------------------------------------------------------------------
    svn:keywords = Date Author Id Revision HeadURL

Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/ShortestDistances.java
------------------------------------------------------------------------------
    svn:mime-type = text/plain



Mime
View raw message