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 2012/02/08 23:22:20 UTC
svn commit: r1242143 - in /commons/sandbox/graph/trunk/src:
main/java/org/apache/commons/graph/
main/java/org/apache/commons/graph/shortestpath/
main/java/org/apache/commons/graph/spanning/
test/java/org/apache/commons/graph/shortestpath/
Author: simonetripodi
Date: Wed Feb 8 22:22:19 2012
New Revision: 1242143
URL: http://svn.apache.org/viewvc?rev=1242143&view=rev
Log:
migrated shortest path algorithms to fluent EDSL
Added:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultHeuristicBuilder.java (with props)
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultPathSourceSelector.java (with props)
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultShortestPathAlgorithmSelector.java (with props)
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultTargetSourceSelector.java (with props)
Removed:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/AStar.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/BellmannFord.java
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/FloydWarshall.java
Modified:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/CommonsGraph.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/HeuristicBuilder.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PathSourceSelector.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/ShortestPathAlgorithmSelector.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/TargetSourceSelector.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeSourceSelector.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/ReverseDeleteGraph.java
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/AStarTestCase.java
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/BellmannFordTestCase.java
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/DijkstraTestCase.java
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/FloydWarshallTestCase.java
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/CommonsGraph.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/CommonsGraph.java?rev=1242143&r1=1242142&r2=1242143&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/CommonsGraph.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/CommonsGraph.java Wed Feb 8 22:22:19 2012
@@ -38,6 +38,7 @@ import org.apache.commons.graph.model.Un
import org.apache.commons.graph.model.UndirectedMutableWeightedGraph;
import org.apache.commons.graph.scc.DefaultSccAlgorithmSelector;
import org.apache.commons.graph.scc.SccAlgorithmSelector;
+import org.apache.commons.graph.shortestpath.DefaultPathSourceSelector;
import org.apache.commons.graph.shortestpath.PathSourceSelector;
import org.apache.commons.graph.spanning.DefaultSpanningTreeSourceSelector;
import org.apache.commons.graph.spanning.SpanningTreeSourceSelector;
@@ -98,10 +99,10 @@ public final class CommonsGraph<V extend
* @param <G>
* @param graph
*/
- public static <V extends Vertex, WE extends WeightedEdge<W>, W, G extends WeightedGraph<V, WE, W>> PathSourceSelector<V, W, WE, G> findShortestPath( G graph )
+ public static <V extends Vertex, WE extends WeightedEdge<W>, W, G extends WeightedGraph<V, WE, W>> PathSourceSelector<V, WE, W, G> findShortestPath( G graph )
{
graph = checkNotNull( graph, "Minimum spanning tree can not be calculated on null graph" );
- return null;
+ return new DefaultPathSourceSelector<V, WE, W, G>( graph );
}
/**
Added: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultHeuristicBuilder.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultHeuristicBuilder.java?rev=1242143&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultHeuristicBuilder.java (added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultHeuristicBuilder.java Wed Feb 8 22:22:19 2012
@@ -0,0 +1,120 @@
+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.Assertions.checkNotNull;
+
+import java.util.HashSet;
+import java.util.Queue;
+import java.util.Set;
+
+import org.apache.commons.graph.DirectedGraph;
+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.collections.FibonacciHeap;
+import org.apache.commons.graph.weight.OrderedMonoid;
+
+final class DefaultHeuristicBuilder<V extends Vertex, WE extends WeightedEdge<W>, W, G extends WeightedGraph<V, WE, W>, OM extends OrderedMonoid<W>>
+ implements HeuristicBuilder<V, WE, W, G, OM>
+{
+
+ private final G graph;
+
+ private final V start;
+
+ private final V goal;
+
+ private final OM orderedMonoid;
+
+ public DefaultHeuristicBuilder( G graph, V source, V target, OM orderedMonoid )
+ {
+ this.graph = graph;
+ this.start = source;
+ this.goal = target;
+ this.orderedMonoid = orderedMonoid;
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public <H extends Heuristic<V, W>> WeightedPath<V, WE, W> withEuristic( H heuristic )
+ {
+ heuristic = checkNotNull( heuristic, "A* algorithm can not be applied using a null heuristic" );
+ // Cost from start along best known path.
+ final ShortestDistances<V, W> gScores = new ShortestDistances<V, W>( orderedMonoid );
+ gScores.setWeight( start, orderedMonoid.zero() );
+
+ // Estimated total cost from start to goal through y.
+ final ShortestDistances<V, W> fScores = new ShortestDistances<V, W>( orderedMonoid );
+ W hScore = heuristic.applyHeuristic( start, goal );
+ fScores.setWeight( start, hScore );
+
+ // The set of nodes already evaluated.
+ final Set<V> closedSet = new HashSet<V>();
+
+ // The set of tentative nodes to be evaluated.
+ final Queue<V> openSet = new FibonacciHeap<V>( fScores );
+ openSet.add( start );
+
+ // The of navigated nodes
+ final PredecessorsList<V, WE, W> predecessors = new PredecessorsList<V, WE, W>( graph, orderedMonoid );
+
+ // extract the node in openset having the lowest f_score[] value
+ while ( !openSet.isEmpty() )
+ {
+ V current = openSet.remove();
+
+ // destination reached, stop and build the path
+ if ( goal.equals( current ) )
+ {
+ return predecessors.buildPath( start, goal );
+ }
+
+ closedSet.add( current );
+
+ Iterable<V> connected = ( graph instanceof DirectedGraph ) ? ( (DirectedGraph<V, WE>) graph ).getOutbound( current )
+ : graph.getConnectedVertices( current );
+ for ( V v : connected )
+ {
+ if ( !closedSet.contains( v ) )
+ {
+ WE edge = graph.getEdge( current, v );
+ // note that the weight of current can never be undefined
+ W tentativeGScore = orderedMonoid.append( gScores.getWeight( current ), edge.getWeight() );
+
+ // if the first condition fails, v has already been visited (its weight is defined)
+ if ( openSet.add( v ) || orderedMonoid.compare( tentativeGScore, gScores.getWeight( v ) ) < 0 )
+ {
+ predecessors.addPredecessor( v, current );
+ gScores.setWeight( v, tentativeGScore );
+ hScore = heuristic.applyHeuristic( v, goal );
+ fScores.setWeight( v, orderedMonoid.append( gScores.getWeight( v ), hScore ) );
+ }
+ }
+ }
+ }
+
+ throw new PathNotFoundException( "Path from '%s' to '%s' doesn't exist in Graph '%s'", start, goal, graph );
+ }
+
+}
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultHeuristicBuilder.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultHeuristicBuilder.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultHeuristicBuilder.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Added: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultPathSourceSelector.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultPathSourceSelector.java?rev=1242143&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultPathSourceSelector.java (added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultPathSourceSelector.java Wed Feb 8 22:22:19 2012
@@ -0,0 +1,147 @@
+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.Assertions.checkNotNull;
+
+import java.util.HashMap;
+import java.util.Map;
+
+import org.apache.commons.graph.UndirectedGraph;
+import org.apache.commons.graph.Vertex;
+import org.apache.commons.graph.VertexPair;
+import org.apache.commons.graph.WeightedEdge;
+import org.apache.commons.graph.WeightedGraph;
+import org.apache.commons.graph.WeightedPath;
+import org.apache.commons.graph.weight.OrderedMonoid;
+
+public final class DefaultPathSourceSelector<V extends Vertex, WE extends WeightedEdge<W>, W, G extends WeightedGraph<V, WE, W>>
+ implements PathSourceSelector<V, WE, W, G>
+{
+
+ private final G graph;
+
+ public DefaultPathSourceSelector( G graph )
+ {
+ this.graph = graph;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public <OM extends OrderedMonoid<W>> AllVertexPairsShortestPath<V, WE, W> applyingFloydWarshall( OM orderedMonoid )
+ {
+ orderedMonoid = checkNotNull( orderedMonoid, "Floyd-Warshall algorithm can not be applied using a null weight monoid" );
+
+ AllVertexPairsShortestPath<V, WE, W> shortestPaths = new AllVertexPairsShortestPath<V, WE, W>( orderedMonoid );
+ Map<VertexPair<V>, V> next = new HashMap<VertexPair<V>, V>();
+
+ // init
+ for ( WE we : graph.getEdges() )
+ {
+ VertexPair<V> vertexPair = graph.getVertices( we );
+ shortestPaths.addShortestDistance( vertexPair.getHead(), vertexPair.getTail(), we.getWeight() );
+
+ if ( graph instanceof UndirectedGraph )
+ {
+ shortestPaths.addShortestDistance( vertexPair.getTail(), vertexPair.getHead(), we.getWeight() );
+ }
+ }
+
+ // run the Floyd-Warshall algorithm.
+ for ( V k : graph.getVertices() )
+ {
+ for ( V i : graph.getVertices() )
+ {
+ for ( V j : graph.getVertices() )
+ {
+ if ( shortestPaths.hasShortestDistance( i, k ) && shortestPaths.hasShortestDistance( k, j ) )
+ {
+ W newDistance = orderedMonoid.append( shortestPaths.getShortestDistance( i, k ), shortestPaths.getShortestDistance( k, j ) );
+ if ( !shortestPaths.hasShortestDistance( i, j )
+ || orderedMonoid.compare( newDistance, shortestPaths.getShortestDistance( i, j ) ) < 0 )
+ {
+ shortestPaths.addShortestDistance( i, j, newDistance );
+
+ // store the intermediate vertex
+ next.put( new VertexPair<V>( i, j ), k );
+ }
+ }
+
+ }
+ }
+ }
+
+ // fills all WeightedPaths
+ for ( V source : graph.getVertices() )
+ {
+ for ( V target : graph.getVertices() )
+ {
+ if ( !source.equals( target ) )
+ {
+ PredecessorsList<V, WE, W> predecessorsList = new PredecessorsList<V, WE, W>( graph, orderedMonoid );
+
+ pathReconstruction( predecessorsList, source, target, next );
+ if ( !predecessorsList.isEmpty() )
+ {
+ WeightedPath<V, WE, W> weightedPath = predecessorsList.buildPath( source, target );
+ if ( weightedPath.getOrder() > 0 )
+ {
+ shortestPaths.addShortestPath( source, target, weightedPath );
+ }
+ }
+ }
+ }
+ }
+
+ return shortestPaths;
+ }
+
+ private void pathReconstruction( PredecessorsList<V, WE, W> path,
+ V source, V target,
+ Map<VertexPair<V>, V> next )
+ {
+ V k = next.get( new VertexPair<Vertex>( source, target ) );
+ if ( k == null )
+ {
+ // there is a direct path between a and b
+ WE edge = graph.getEdge( source, target );
+ if ( edge != null )
+ {
+ path.addPredecessor( target, source );
+ }
+ }
+ else
+ {
+ pathReconstruction( path, source, k, next );
+ pathReconstruction( path, k, target, next );
+ }
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public TargetSourceSelector<V, WE, W, G> from( V source )
+ {
+ source = checkNotNull( source, "Shortest path can not be calculated from a null source" );
+ return new DefaultTargetSourceSelector<V, WE, W, G>( graph, source );
+ }
+
+}
\ No newline at end of file
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultPathSourceSelector.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultPathSourceSelector.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultPathSourceSelector.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Added: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultShortestPathAlgorithmSelector.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultShortestPathAlgorithmSelector.java?rev=1242143&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultShortestPathAlgorithmSelector.java (added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultShortestPathAlgorithmSelector.java Wed Feb 8 22:22:19 2012
@@ -0,0 +1,120 @@
+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.Assertions.checkNotNull;
+
+import java.util.HashSet;
+import java.util.Queue;
+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;
+import org.apache.commons.graph.collections.FibonacciHeap;
+import org.apache.commons.graph.weight.OrderedMonoid;
+
+final class DefaultShortestPathAlgorithmSelector<V extends Vertex, WE extends WeightedEdge<W>, W, G extends WeightedGraph<V, WE, W>>
+ implements ShortestPathAlgorithmSelector<V, WE, W, G>
+{
+
+ private final G graph;
+
+ private final V source;
+
+ private final V target;
+
+ public DefaultShortestPathAlgorithmSelector( G graph, V source, V target )
+ {
+ this.graph = graph;
+ this.source = source;
+ this.target = target;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public <OM extends OrderedMonoid<W>> HeuristicBuilder<V, WE, W, G, OM> applyingAStar( OM orderedMonoid )
+ {
+ orderedMonoid = checkNotNull( orderedMonoid, "A* algorithm can not be applied using a null weight monoid" );
+ return new DefaultHeuristicBuilder<V, WE, W, G, OM>( graph, source, target, orderedMonoid );
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public <OM extends OrderedMonoid<W>> WeightedPath<V, WE, W> applyingDijkstra( OM orderedMonoid )
+ {
+ orderedMonoid = checkNotNull( orderedMonoid, "Dijkstra algorithm can not be applied using a null weight monoid" );
+
+ final ShortestDistances<V, W> shortestDistances = new ShortestDistances<V, W>( orderedMonoid );
+ shortestDistances.setWeight( source, orderedMonoid.zero() );
+
+ final Queue<V> unsettledNodes = new FibonacciHeap<V>( shortestDistances );
+ unsettledNodes.add( source );
+
+ final Set<V> settledNodes = new HashSet<V>();
+
+ final PredecessorsList<V, WE, W> predecessors = new PredecessorsList<V, WE, W>( graph, orderedMonoid );
+
+ // extract the node with the shortest distance
+ while ( !unsettledNodes.isEmpty() )
+ {
+ V vertex = unsettledNodes.remove();
+
+ // destination reached, stop and build the path
+ if ( target.equals( vertex ) )
+ {
+ return predecessors.buildPath( source, target );
+ }
+
+ settledNodes.add( vertex );
+
+ for ( V v : graph.getConnectedVertices( vertex ) )
+ {
+ // skip node already settled
+ if ( !settledNodes.contains( v ) )
+ {
+ WE edge = graph.getEdge( vertex, v );
+ if ( shortestDistances.alreadyVisited( vertex ) )
+ {
+ W shortDist = orderedMonoid.append( shortestDistances.getWeight( vertex ), edge.getWeight() );
+
+ if ( !shortestDistances.alreadyVisited( v )
+ || orderedMonoid.compare( shortDist, shortestDistances.getWeight( v ) ) < 0 )
+ {
+ // assign new shortest distance and mark unsettled
+ shortestDistances.setWeight( v, shortDist );
+ unsettledNodes.add( v );
+
+ // assign predecessor in shortest path
+ predecessors.addPredecessor( v, vertex );
+ }
+ }
+
+ }
+ }
+ }
+
+ throw new PathNotFoundException( "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/DefaultShortestPathAlgorithmSelector.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultShortestPathAlgorithmSelector.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultShortestPathAlgorithmSelector.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Added: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultTargetSourceSelector.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultTargetSourceSelector.java?rev=1242143&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultTargetSourceSelector.java (added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultTargetSourceSelector.java Wed Feb 8 22:22:19 2012
@@ -0,0 +1,125 @@
+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.Assertions.checkNotNull;
+
+import org.apache.commons.graph.Vertex;
+import org.apache.commons.graph.VertexPair;
+import org.apache.commons.graph.WeightedEdge;
+import org.apache.commons.graph.WeightedGraph;
+import org.apache.commons.graph.WeightedPath;
+import org.apache.commons.graph.weight.OrderedMonoid;
+
+final class DefaultTargetSourceSelector<V extends Vertex, WE extends WeightedEdge<W>, W, G extends WeightedGraph<V, WE, W>>
+ implements TargetSourceSelector<V, WE, W, G>
+{
+
+ private final G graph;
+
+ private final V source;
+
+ public DefaultTargetSourceSelector( G graph, V source )
+ {
+ this.graph = graph;
+ this.source = source;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public <OM extends OrderedMonoid<W>> AllVertexPairsShortestPath<V, WE, W> applyingBelmannFord( OM orderedMonoid )
+ {
+ orderedMonoid = checkNotNull( orderedMonoid, "Belmann-Ford algorithm can not be applied using a null weight monoid" );
+
+ final ShortestDistances<V, W> shortestDistances = new ShortestDistances<V, W>( orderedMonoid );
+ shortestDistances.setWeight( source, orderedMonoid.zero() );
+
+ final PredecessorsList<V, WE, W> predecessors = new PredecessorsList<V, WE, W>( graph, orderedMonoid );
+
+ for ( int i = 0; i < graph.getOrder(); i++ )
+ {
+ for ( WE edge : graph.getEdges() )
+ {
+ VertexPair<V> vertexPair = graph.getVertices( edge );
+ V u = vertexPair.getHead();
+ V v = vertexPair.getTail();
+
+ if ( shortestDistances.alreadyVisited( u ) )
+ {
+ W shortDist = orderedMonoid.append( shortestDistances.getWeight( u ), edge.getWeight() );
+
+ if ( !shortestDistances.alreadyVisited( v )
+ || orderedMonoid.compare( shortDist, shortestDistances.getWeight( v ) ) < 0 )
+ {
+ // assign new shortest distance and mark unsettled
+ shortestDistances.setWeight( v, shortDist );
+
+ // assign predecessor in shortest path
+ predecessors.addPredecessor( v, u );
+ }
+ }
+ }
+ }
+
+ for ( WE edge : graph.getEdges() )
+ {
+ VertexPair<V> vertexPair = graph.getVertices( edge );
+ V u = vertexPair.getHead();
+ V v = vertexPair.getTail();
+
+ if ( shortestDistances.alreadyVisited( u ) )
+ {
+ W shortDist = orderedMonoid.append( shortestDistances.getWeight( u ), edge.getWeight() );
+
+ if ( !shortestDistances.alreadyVisited( v )
+ || orderedMonoid.compare( shortDist, shortestDistances.getWeight( v ) ) < 0 )
+ {
+ // TODO it would be nice printing the cycle
+ throw new NegativeWeightedCycleException( "Graph contains a negative-weight cycle in vertex %s",
+ v, graph );
+ }
+ }
+ }
+
+ AllVertexPairsShortestPath<V, WE, W> allVertexPairsShortestPath = new AllVertexPairsShortestPath<V, WE, W>( orderedMonoid );
+
+ for ( V target : graph.getVertices() )
+ {
+ if ( !source.equals( target ) )
+ {
+ WeightedPath<V, WE, W> weightedPath = predecessors.buildPath( source, target );
+ allVertexPairsShortestPath.addShortestPath( source, target, weightedPath );
+ }
+ }
+
+ return allVertexPairsShortestPath;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public ShortestPathAlgorithmSelector<V, WE, W, G> to( V target )
+ {
+ target = checkNotNull( target, "Shortest path can not be calculated to a null target" );
+ return new DefaultShortestPathAlgorithmSelector<V, WE, W, G>( graph, source, target );
+ }
+
+}
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultTargetSourceSelector.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultTargetSourceSelector.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultTargetSourceSelector.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/HeuristicBuilder.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/HeuristicBuilder.java?rev=1242143&r1=1242142&r2=1242143&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/HeuristicBuilder.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/HeuristicBuilder.java Wed Feb 8 22:22:19 2012
@@ -19,19 +19,20 @@ package org.apache.commons.graph.shortes
* under the License.
*/
-import org.apache.commons.graph.Graph;
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.weight.OrderedMonoid;
/**
*
* @param <V>
- * @param <W>
* @param <WE>
+ * @param <W>
* @param <G>
*/
-public interface HeuristicBuilder<V extends Vertex, W, WE extends WeightedEdge<W>, G extends Graph<V, WE>>
+public interface HeuristicBuilder<V extends Vertex, WE extends WeightedEdge<W>, W, G extends WeightedGraph<V, WE, W>, OM extends OrderedMonoid<W>>
{
/**
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PathSourceSelector.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PathSourceSelector.java?rev=1242143&r1=1242142&r2=1242143&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PathSourceSelector.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PathSourceSelector.java Wed Feb 8 22:22:19 2012
@@ -19,9 +19,9 @@ package org.apache.commons.graph.shortes
* under the License.
*/
-import org.apache.commons.graph.Graph;
import org.apache.commons.graph.Vertex;
import org.apache.commons.graph.WeightedEdge;
+import org.apache.commons.graph.WeightedGraph;
import org.apache.commons.graph.weight.OrderedMonoid;
/**
@@ -32,7 +32,7 @@ import org.apache.commons.graph.weight.O
* @param <WE>
* @param <G>
*/
-public interface PathSourceSelector<V extends Vertex, W, WE extends WeightedEdge<W>, G extends Graph<V, WE>>
+public interface PathSourceSelector<V extends Vertex, WE extends WeightedEdge<W>, W, G extends WeightedGraph<V, WE, W>>
{
/**
@@ -49,6 +49,6 @@ public interface PathSourceSelector<V ex
*
* @param source
*/
- TargetSourceSelector<V, W, WE, G> from( V source );
-
+ TargetSourceSelector<V, WE, W, G> from( V source );
+
}
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/ShortestPathAlgorithmSelector.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/ShortestPathAlgorithmSelector.java?rev=1242143&r1=1242142&r2=1242143&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/ShortestPathAlgorithmSelector.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/ShortestPathAlgorithmSelector.java Wed Feb 8 22:22:19 2012
@@ -19,9 +19,9 @@ package org.apache.commons.graph.shortes
* under the License.
*/
-import org.apache.commons.graph.Graph;
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.weight.OrderedMonoid;
@@ -33,7 +33,7 @@ import org.apache.commons.graph.weight.O
* @param <WE>
* @param <G>
*/
-public interface ShortestPathAlgorithmSelector<V extends Vertex, W, WE extends WeightedEdge<W>, G extends Graph<V, WE>>
+public interface ShortestPathAlgorithmSelector<V extends Vertex, WE extends WeightedEdge<W>, W, G extends WeightedGraph<V, WE, W>>
{
/**
@@ -43,7 +43,7 @@ public interface ShortestPathAlgorithmSe
* @param orderedMonoid the ordered monoid needed to handle operations on weights
* @return
*/
- <OM extends OrderedMonoid<W>> HeuristicBuilder<V, W, WE, G> applyingAStar( OM orderedMonoid );
+ <OM extends OrderedMonoid<W>> HeuristicBuilder<V, WE, W, G, OM> applyingAStar( OM orderedMonoid );
/**
* Calculates the shortest path using the Dijkstra's algorithm.
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/TargetSourceSelector.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/TargetSourceSelector.java?rev=1242143&r1=1242142&r2=1242143&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/TargetSourceSelector.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/TargetSourceSelector.java Wed Feb 8 22:22:19 2012
@@ -19,9 +19,9 @@ package org.apache.commons.graph.shortes
* under the License.
*/
-import org.apache.commons.graph.Graph;
import org.apache.commons.graph.Vertex;
import org.apache.commons.graph.WeightedEdge;
+import org.apache.commons.graph.WeightedGraph;
import org.apache.commons.graph.weight.OrderedMonoid;
/**
@@ -32,7 +32,7 @@ import org.apache.commons.graph.weight.O
* @param <WE>
* @param <G>
*/
-public interface TargetSourceSelector<V extends Vertex, W, WE extends WeightedEdge<W>, G extends Graph<V, WE>>
+public interface TargetSourceSelector<V extends Vertex, WE extends WeightedEdge<W>, W, G extends WeightedGraph<V, WE, W>>
{
/**
@@ -49,6 +49,6 @@ public interface TargetSourceSelector<V
*
* @param target
*/
- void to( V target );
-
+ ShortestPathAlgorithmSelector<V, WE, W, G> to( V target );
+
}
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeSourceSelector.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeSourceSelector.java?rev=1242143&r1=1242142&r2=1242143&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeSourceSelector.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeSourceSelector.java Wed Feb 8 22:22:19 2012
@@ -21,7 +21,7 @@ package org.apache.commons.graph.spannin
import static java.util.Collections.reverseOrder;
import static java.util.Collections.sort;
-import static org.apache.commons.graph.shortestpath.Dijkstra.findShortestPath;
+import static org.apache.commons.graph.CommonsGraph.findShortestPath;
import static org.apache.commons.graph.utils.Assertions.checkNotNull;
import java.util.ArrayList;
@@ -33,6 +33,7 @@ import org.apache.commons.graph.Spanning
import org.apache.commons.graph.Vertex;
import org.apache.commons.graph.VertexPair;
import org.apache.commons.graph.WeightedEdge;
+import org.apache.commons.graph.WeightedGraph;
import org.apache.commons.graph.model.MutableSpanningTree;
import org.apache.commons.graph.shortestpath.PathNotFoundException;
import org.apache.commons.graph.weight.OrderedMonoid;
@@ -89,7 +90,7 @@ public final class DefaultSpanningTreeSo
sort( sortedEdge, reverseOrder( new WeightedEdgesComparator<W, WE>( orderedMonoid ) ) );
- Graph<V, WE> tmpGraph = new ReverseDeleteGraph<V, WE, W>( graph, sortedEdge, visitedEdge );
+ WeightedGraph<V, WE, W> tmpGraph = new ReverseDeleteGraph<V, WE, W>( graph, sortedEdge, visitedEdge );
for ( Iterator<WE> iterator = sortedEdge.iterator(); iterator.hasNext(); )
{
@@ -100,7 +101,7 @@ public final class DefaultSpanningTreeSo
try
{
- findShortestPath( tmpGraph, vertices.getHead(), vertices.getTail(), orderedMonoid );
+ findShortestPath( tmpGraph ).from( vertices.getHead() ).to( vertices.getTail() ).applyingDijkstra( orderedMonoid );
}
catch ( PathNotFoundException ex )
{
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/ReverseDeleteGraph.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/ReverseDeleteGraph.java?rev=1242143&r1=1242142&r2=1242143&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/ReverseDeleteGraph.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/ReverseDeleteGraph.java Wed Feb 8 22:22:19 2012
@@ -19,14 +19,15 @@ package org.apache.commons.graph.spannin
* under the License.
*/
+import java.util.ArrayList;
+import java.util.List;
+
import org.apache.commons.graph.Graph;
import org.apache.commons.graph.GraphException;
import org.apache.commons.graph.Vertex;
import org.apache.commons.graph.VertexPair;
import org.apache.commons.graph.WeightedEdge;
-
-import java.util.ArrayList;
-import java.util.List;
+import org.apache.commons.graph.WeightedGraph;
/**
*
@@ -35,7 +36,7 @@ import java.util.List;
* @param <W>
*/
final class ReverseDeleteGraph<V extends Vertex, WE extends WeightedEdge<W>, W>
- implements Graph<V, WE>
+ implements WeightedGraph<V, WE, W>
{
private static final long serialVersionUID = -543197749473412325L;
Modified: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/AStarTestCase.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/AStarTestCase.java?rev=1242143&r1=1242142&r2=1242143&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/AStarTestCase.java (original)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/AStarTestCase.java Wed Feb 8 22:22:19 2012
@@ -20,7 +20,7 @@ package org.apache.commons.graph.shortes
*/
import static junit.framework.Assert.assertEquals;
-import static org.apache.commons.graph.shortestpath.AStar.findShortestPath;
+import static org.apache.commons.graph.CommonsGraph.findShortestPath;
import java.util.HashMap;
import java.util.Map;
@@ -106,7 +106,8 @@ public final class AStarTestCase
// actual path
- Path<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>> actual = findShortestPath( graph, start, goal, heuristic );
+ Path<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>> actual =
+ findShortestPath( graph ).from( start ).to( goal ).applyingAStar( new DoubleWeight() ).withEuristic( heuristic );
// assert!
Modified: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/BellmannFordTestCase.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/BellmannFordTestCase.java?rev=1242143&r1=1242142&r2=1242143&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/BellmannFordTestCase.java (original)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/BellmannFordTestCase.java Wed Feb 8 22:22:19 2012
@@ -19,8 +19,8 @@ package org.apache.commons.graph.shortes
* under the License.
*/
+import static org.apache.commons.graph.CommonsGraph.findShortestPath;
import static junit.framework.Assert.assertEquals;
-import static org.apache.commons.graph.shortestpath.BellmannFord.findShortestPath;
import org.apache.commons.graph.WeightedPath;
import org.apache.commons.graph.model.BaseLabeledVertex;
@@ -79,7 +79,7 @@ public final class BellmannFordTestCase
// the actual weighted path
AllVertexPairsShortestPath<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> allVertexPairsShortestPath =
- findShortestPath( graph, one );
+ findShortestPath( graph ).from( one ).applyingBelmannFord( new DoubleWeight() );
WeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> actual =
allVertexPairsShortestPath.findShortestPath( one, three );
Modified: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/DijkstraTestCase.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/DijkstraTestCase.java?rev=1242143&r1=1242142&r2=1242143&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/DijkstraTestCase.java (original)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/DijkstraTestCase.java Wed Feb 8 22:22:19 2012
@@ -20,7 +20,7 @@ package org.apache.commons.graph.shortes
*/
import static junit.framework.Assert.assertEquals;
-import static org.apache.commons.graph.shortestpath.Dijkstra.findShortestPath;
+import static org.apache.commons.graph.CommonsGraph.findShortestPath;
import org.apache.commons.graph.Path;
import org.apache.commons.graph.model.BaseLabeledVertex;
@@ -83,7 +83,7 @@ public final class DijkstraTestCase
// actual path
- Path<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>> actual = findShortestPath( graph, one, five );
+ Path<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>> actual = findShortestPath( graph ).from( one ).to( five ).applyingDijkstra( new DoubleWeight() );
// assert!
Modified: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/FloydWarshallTestCase.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/FloydWarshallTestCase.java?rev=1242143&r1=1242142&r2=1242143&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/FloydWarshallTestCase.java (original)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/FloydWarshallTestCase.java Wed Feb 8 22:22:19 2012
@@ -22,11 +22,11 @@ package org.apache.commons.graph.shortes
import static junit.framework.Assert.assertEquals;
import static junit.framework.Assert.assertFalse;
import static junit.framework.Assert.fail;
-import static org.apache.commons.graph.shortestpath.FloydWarshall.findAllVertexPairsShortestPath;
+import static org.apache.commons.graph.CommonsGraph.findShortestPath;
-import org.apache.commons.graph.Graph;
import org.apache.commons.graph.MutableGraph;
import org.apache.commons.graph.UndirectedGraph;
+import org.apache.commons.graph.WeightedGraph;
import org.apache.commons.graph.WeightedPath;
import org.apache.commons.graph.model.BaseLabeledVertex;
import org.apache.commons.graph.model.BaseLabeledWeightedEdge;
@@ -53,9 +53,9 @@ public class FloydWarshallTestCase
findShortestPathAndVerify( new DirectedMutableWeightedGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double>() );
}
- private void findShortestPathAndVerify( Graph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>> weighted )
+ private void findShortestPathAndVerify( WeightedGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> weighted )
{
- // mutable by definition, generic types driven by input graph
+ @SuppressWarnings( "unchecked" ) // mutable by definition, generic types driven by input graph
MutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>> mutable =
(MutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>) weighted;
@@ -89,7 +89,7 @@ public class FloydWarshallTestCase
mutable.addEdge( six, new BaseLabeledWeightedEdge<Double>( "6 -> 5", 9D ), five );
AllVertexPairsShortestPath<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> p =
- findAllVertexPairsShortestPath( weighted );
+ findShortestPath( weighted ).applyingFloydWarshall( new DoubleWeight() );
if ( weighted instanceof UndirectedGraph )
{