commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From simonetrip...@apache.org
Subject 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/
Date Wed, 08 Feb 2012 22:22:20 GMT
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 )
         {



Mime
View raw message