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/14 23:37:35 UTC
svn commit: r1135807 - in
/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath:
./ Dijkstra.java PathNotFoundException.java ShortestDistanceComparator.java
ShortestDistances.java
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