commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From simonetrip...@apache.org
Subject svn commit: r1484153 - in /commons/sandbox/graph/trunk: ./ src/benchmarks/java/org/apache/commons/graph/shortestpath/ src/main/java/org/apache/commons/graph/shortestpath/ src/test/java/org/apache/commons/graph/shortestpath/
Date Sat, 18 May 2013 17:50:01 GMT
Author: simonetripodi
Date: Sat May 18 17:50:00 2013
New Revision: 1484153

URL: http://svn.apache.org/r1484153
Log:
SANDBOX-457 - Adding an implementation of a bidirectional Dijkstra's algorithm

applied patch provided by Rodion Efremov [rodion.efremov@cs.helsinki.fi]

Added:
    commons/sandbox/graph/trunk/src/benchmarks/java/org/apache/commons/graph/shortestpath/
    commons/sandbox/graph/trunk/src/benchmarks/java/org/apache/commons/graph/shortestpath/UniVsBiDijkstraBenchmarkTestCase.java
  (with props)
    commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/BidirDijkstraTestCase.java
  (with props)
Modified:
    commons/sandbox/graph/trunk/pom.xml
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultShortestPathAlgorithmSelector.java
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PredecessorsList.java
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/ShortestPathAlgorithmSelector.java

Modified: commons/sandbox/graph/trunk/pom.xml
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/pom.xml?rev=1484153&r1=1484152&r2=1484153&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/pom.xml (original)
+++ commons/sandbox/graph/trunk/pom.xml Sat May 18 17:50:00 2013
@@ -92,6 +92,10 @@
       <name>Matthew Pocock</name>
       <email>turingatemyhamster AT gmail DOT com</email>
     </contributor>
+    <contributor>
+      <name>Rodion Efremov</name>
+      <email>rodion dot efremov at cs dot helsinki dot fi</email>
+    </contributor>
   </contributors>
 
   <scm>

Added: commons/sandbox/graph/trunk/src/benchmarks/java/org/apache/commons/graph/shortestpath/UniVsBiDijkstraBenchmarkTestCase.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/benchmarks/java/org/apache/commons/graph/shortestpath/UniVsBiDijkstraBenchmarkTestCase.java?rev=1484153&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/benchmarks/java/org/apache/commons/graph/shortestpath/UniVsBiDijkstraBenchmarkTestCase.java
(added)
+++ commons/sandbox/graph/trunk/src/benchmarks/java/org/apache/commons/graph/shortestpath/UniVsBiDijkstraBenchmarkTestCase.java
Sat May 18 17:50:00 2013
@@ -0,0 +1,204 @@
+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 static java.lang.String.valueOf;
+import static org.apache.commons.graph.CommonsGraph.findShortestPath;
+import static org.apache.commons.graph.CommonsGraph.newDirectedMutableGraph;
+import static org.junit.Assert.assertTrue;
+
+import java.util.ArrayList;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Random;
+
+import org.apache.commons.graph.builder.AbstractGraphConnection;
+import org.apache.commons.graph.GraphException;
+import org.apache.commons.graph.Mapper;
+import org.apache.commons.graph.model.BaseLabeledVertex;
+import org.apache.commons.graph.model.BaseLabeledWeightedEdge;
+import org.apache.commons.graph.model.BaseWeightedEdge;
+import org.apache.commons.graph.model.DirectedMutableGraph;
+import org.apache.commons.graph.WeightedPath;
+import org.apache.commons.graph.weight.OrderedMonoid;
+import org.apache.commons.graph.weight.primitive.DoubleWeightBaseOperations;
+
+import org.junit.BeforeClass;
+import org.junit.Rule;
+import org.junit.Test;
+
+import com.carrotsearch.junitbenchmarks.BenchmarkOptions;
+import com.carrotsearch.junitbenchmarks.BenchmarkRule;
+import com.carrotsearch.junitbenchmarks.annotation.AxisRange;
+import com.carrotsearch.junitbenchmarks.annotation.BenchmarkMethodChart;
+
+@AxisRange( min = 0, max = 2 )
+@BenchmarkMethodChart( filePrefix = "dijkstras" )
+@BenchmarkOptions( benchmarkRounds = 10, warmupRounds = 5 )
+public final class UniVsBiDijkstraBenchmarkTestCase
+{
+    private static final int NODES = 5000;
+    private static final int EDGES = 100000;
+
+    @Rule
+    public BenchmarkRule benchmarkRun = new BenchmarkRule();
+
+    private static DirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>
graph;
+
+    private static Mapper<BaseLabeledWeightedEdge<Double>, Double> weightedEdges;
+
+    private static LinkedList<BaseLabeledVertex> sourceListUni;
+
+    private static LinkedList<BaseLabeledVertex> sourceListBi;
+
+    private static LinkedList<BaseLabeledVertex> targetListUni;
+
+    private static LinkedList<BaseLabeledVertex> targetListBi;
+
+    private static List<BaseLabeledVertex> vertices;
+
+    private static OrderedMonoid<Double> weightOperations;
+
+    @BeforeClass
+    public static void setUp()
+    {
+        weightOperations = new DoubleWeightBaseOperations();
+
+        weightedEdges = new Mapper<BaseLabeledWeightedEdge<Double>, Double>()
+        {
+
+            public Double map( BaseLabeledWeightedEdge<Double> input )
+            {
+                return input.getWeight();
+            }
+
+        };
+
+        graph = newDirectedMutableGraph( new AbstractGraphConnection<BaseLabeledVertex,
BaseLabeledWeightedEdge<Double>>()
+        {
+            Random r = new Random();
+
+            public void connect()
+            {
+                vertices = new ArrayList<BaseLabeledVertex>();
+                for ( int i = 0; i < NODES; i++ )
+                {
+                    BaseLabeledVertex v = new BaseLabeledVertex( valueOf( i ) );
+                    addVertex( v );
+                    vertices.add( v );
+                }
+
+                // form a connected graph
+                for ( int i = 0; i < NODES - 1; i++ )
+                {
+                    addEdge( vertices.get( i ), vertices.get( i + 1 ) );
+                }
+
+                addEdge( vertices.get( NODES - 1 ) , vertices.get( 0 ) );
+
+                // we have already created #NODES edges
+                int maxEdges = Math.max(0, EDGES - NODES);
+                for ( int i = 0; i < maxEdges; i++)
+                {
+                    while ( ! addEdge( vertices.get( r.nextInt(NODES) ), vertices.get( r.nextInt(NODES)
) ) ) {
+                        // do nothing
+                    }
+                }
+            }
+
+            private boolean addEdge( BaseLabeledVertex src, BaseLabeledVertex dst )
+            {
+                try {
+                  addEdge( new BaseLabeledWeightedEdge<Double>( format( "%s -> %s",
src, dst ),
+                                                                10.0 * r.nextDouble() + 1.0
) ).from( src ).to( dst );
+                  return true;
+              } catch (GraphException e) {
+                  // ignore duplicate edge exceptions
+                  return false;
+              }
+            }
+        } );
+
+        sourceListUni = new LinkedList<BaseLabeledVertex>();
+        targetListUni = new LinkedList<BaseLabeledVertex>();
+
+        sourceListBi = new LinkedList<BaseLabeledVertex>();
+        targetListBi = new LinkedList<BaseLabeledVertex>();
+
+        Random r = new Random();
+
+        for ( int i = 0; i < 15; i++ )
+        {
+            BaseLabeledVertex s = vertices.get( r.nextInt( vertices.size() ) );
+            sourceListUni.add( s );
+            sourceListBi.add( s );
+
+            BaseLabeledVertex t = vertices.get( r.nextInt( vertices.size() ) );
+            targetListUni.add( t );
+            targetListBi.add( t );
+        }
+    }
+
+    @Test
+    public void performUnidirectionalDijkstra() {
+        BaseLabeledVertex source = sourceListUni.removeFirst();
+        BaseLabeledVertex target = targetListUni.removeFirst();
+
+        try {
+            WeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double>
path =
+                    findShortestPath( graph )
+                                .whereEdgesHaveWeights( new BaseWeightedEdge<Double>()
)
+                                .from( source )
+                                .to( target )
+                                .applyingDijkstra( weightOperations );
+
+            assertTrue( path.getSize() > 0 );
+            assertTrue( path.getWeight() > 0D );
+        }
+        catch ( Exception e )
+        {
+            e.printStackTrace();
+        }
+    }
+
+    @Test
+    public void performBidirectionalDijkstra() {
+        BaseLabeledVertex source = sourceListBi.removeFirst();
+        BaseLabeledVertex target = targetListBi.removeFirst();
+
+        try {
+            WeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double>
path =
+                    findShortestPath( graph )
+                                .whereEdgesHaveWeights( new BaseWeightedEdge<Double>()
)
+                                .from( source )
+                                .to( target )
+                                .applyingBidirectionalDijkstra( weightOperations );
+
+            assertTrue( path.getSize() > 0 );
+            assertTrue( path.getWeight() > 0D );
+        }
+        catch ( Exception e )
+        {
+            e.printStackTrace();
+        }
+    }
+
+}

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

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

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

Modified: 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=1484153&r1=1484152&r2=1484153&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultShortestPathAlgorithmSelector.java
(original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/DefaultShortestPathAlgorithmSelector.java
Sat May 18 17:50:00 2013
@@ -24,6 +24,7 @@ import static org.apache.commons.graph.u
 import java.util.HashSet;
 import java.util.Queue;
 import java.util.Set;
+import org.apache.commons.graph.DirectedGraph;
 
 import org.apache.commons.graph.Graph;
 import org.apache.commons.graph.Mapper;
@@ -119,4 +120,127 @@ final class DefaultShortestPathAlgorithm
         throw new PathNotFoundException( "Path from '%s' to '%s' doesn't exist in Graph '%s'",
source, target, graph );
     }
 
+    /**
+     * {@inheritDoc}
+     */
+    public <WO extends OrderedMonoid<W>> WeightedPath<V, WE, W> applyingBidirectionalDijkstra(
WO weightOperations )
+    {
+        weightOperations = checkNotNull( weightOperations, "Bidirectional Dijkstra algorithm
can not be applied using null weight operations" );
+
+        final ShortestDistances<V, W> shortestDistancesForward = new ShortestDistances<V,
W>( weightOperations );
+        shortestDistancesForward.setWeight( source, weightOperations.identity() );
+
+        final ShortestDistances<V, W> shortestDistancesBackwards = new ShortestDistances<V,
W>( weightOperations );
+        shortestDistancesBackwards.setWeight( target, weightOperations.identity() );
+
+        final Queue<V> openForward = new FibonacciHeap<V>( shortestDistancesForward
);
+        openForward.add( source );
+
+        final Queue<V> openBackwards = new FibonacciHeap<V>( shortestDistancesBackwards
);
+        openBackwards.add( target );
+
+        final Set<V> closedForward = new HashSet<V>();
+
+        final Set<V> closedBackwards = new HashSet<V>();
+
+        final PredecessorsList<V, WE, W> predecessorsForward = new PredecessorsList<V,
WE, W>( graph, weightOperations, weightedEdges );
+
+        final PredecessorsList<V, WE, W> predecessorsBackwards = new PredecessorsList<V,
WE, W>( graph, weightOperations, weightedEdges );
+
+        W best = null;
+        V touch = null;
+
+        while (!openForward.isEmpty() && !openBackwards.isEmpty())
+        {
+            if ( best != null )
+            {
+                final W tmp = weightOperations.append( shortestDistancesForward.getWeight(
openForward.peek() ),
+                                                       shortestDistancesBackwards.getWeight(
openBackwards.peek() ) );
+
+                if ( weightOperations.compare( tmp, best ) >= 0 )
+                {
+                    return predecessorsForward.buildPath( source, touch, target, predecessorsBackwards
);
+                }
+            }
+
+            V vertex = openForward.remove();
+
+            closedForward.add( vertex );
+
+            for ( V v : graph.getConnectedVertices( vertex ) )
+            {
+                if ( !closedForward.contains( v ) )
+                {
+                    WE edge = graph.getEdge( vertex, v );
+                    if ( shortestDistancesForward.alreadyVisited( vertex ) )
+                    {
+                        W shortDist = weightOperations.append( shortestDistancesForward.getWeight(
vertex ), weightedEdges.map( edge ) );
+
+                        if ( !shortestDistancesForward.alreadyVisited( v )
+                                || weightOperations.compare( shortDist, shortestDistancesForward.getWeight(
v ) ) < 0 )
+                        {
+                            shortestDistancesForward.setWeight( v, shortDist );
+                            openForward.add( v );
+                            predecessorsForward.addPredecessor( v, vertex );
+
+                            if ( closedBackwards.contains( v ) )
+                            {
+                                W tmpBest = weightOperations.append( shortDist, shortestDistancesBackwards.getWeight(
v ) );
+
+                                if ( best == null || weightOperations.compare( tmpBest, best
) < 0 )
+                                {
+                                    best = tmpBest;
+                                    touch = v;
+                                }
+                            }
+                        }
+                    }
+                }
+            }
+
+            vertex = openBackwards.remove();
+
+            closedBackwards.add( vertex );
+
+            Iterable<V> parentsIterable = ( graph instanceof DirectedGraph ? ((DirectedGraph<V,
WE>) graph).getInbound( vertex ) : graph.getConnectedVertices( vertex ) );
+
+            for ( V v : parentsIterable )
+            {
+                if ( !closedBackwards.contains( v ) )
+                {
+                    WE edge = graph.getEdge( v, vertex );
+                    if ( shortestDistancesBackwards.alreadyVisited( vertex ) )
+                    {
+                        W shortDist = weightOperations.append( shortestDistancesBackwards.getWeight(
vertex ), weightedEdges.map( edge ) );
+
+                        if ( !shortestDistancesBackwards.alreadyVisited( v )
+                                || weightOperations.compare( shortDist, shortestDistancesBackwards.getWeight(
v ) ) < 0 )
+                        {
+                            shortestDistancesBackwards.setWeight( v, shortDist );
+                            openBackwards.add( v );
+                            predecessorsBackwards.addPredecessor( v, vertex );
+
+                            if ( closedForward.contains( v ) )
+                            {
+                                W tmpBest = weightOperations.append( shortDist, shortestDistancesForward.getWeight(
v ) );
+
+                                if ( best == null || weightOperations.compare( tmpBest, best
) < 0 )
+                                {
+                                    best = tmpBest;
+                                    touch = v;
+                                }
+                            }
+                        }
+                    }
+                }
+            }
+        }
+
+        if ( touch == null )
+        {
+            throw new PathNotFoundException( "Path from '%s' to '%s' doesn't exist in Graph
'%s'", source, target, graph);
+        }
+
+        return predecessorsForward.buildPath( source, touch, target, predecessorsBackwards
);
+    }
 }

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PredecessorsList.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PredecessorsList.java?rev=1484153&r1=1484152&r2=1484153&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PredecessorsList.java
(original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PredecessorsList.java
Sat May 18 17:50:00 2013
@@ -95,6 +95,53 @@ public final class PredecessorsList<V, W
     }
 
     /**
+     * Build a {@link WeightedPath} instance related to source-target path.
+     *
+     * @param source the path source vertex
+     * @param touch the node where search frontiers meet, producing the shortest path
+     * @param target the path target vertex
+     * @param backwardsList the predecessor list in backwards search space along reversed
edges
+     * @return the weighted path related to source to target
+     */
+    public WeightedPath<V, WE, W> buildPath( V source, V touch, V target, PredecessorsList<V,
WE, W> backwardsList ) {
+        InMemoryWeightedPath<V, WE, W> path = new InMemoryWeightedPath<V, WE, W>(
source, target, weightOperations, weightedEdges );
+
+        V vertex = touch;
+        while ( !source.equals( vertex ) )
+        {
+            V predecessor = predecessors.get( vertex );
+            if ( predecessor == null )
+            {
+                throw new PathNotFoundException( "Path from '%s' to '%s' doesn't exist",
source, target );
+            }
+            WE edge = graph.getEdge( predecessor, vertex );
+
+            path.addConnectionInHead(predecessor, edge, vertex);
+
+            vertex = predecessor;
+        }
+
+        vertex = touch;
+
+        while ( !target.equals( vertex ) )
+        {
+            // 'predecessor' is actually a successor.
+            V predecessor = backwardsList.predecessors.get( vertex );
+            if ( predecessor == null )
+            {
+                throw new PathNotFoundException( "Path from '%s' to '%s' doesn't exist",
source, target );
+            }
+            WE edge = graph.getEdge( vertex, predecessor );
+
+            path.addConnectionInTail( vertex, edge, predecessor );
+
+            vertex = predecessor;
+        }
+
+        return path;
+    }
+
+    /**
      * Checks the predecessor list has no elements.
      *
      * @return true, if the predecessor list has no elements, false otherwise.

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=1484153&r1=1484152&r2=1484153&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
Sat May 18 17:50:00 2013
@@ -50,4 +50,13 @@ public interface ShortestPathAlgorithmSe
      */
     <WO extends OrderedMonoid<W>> WeightedPath<V, WE, W> applyingDijkstra(
WO weightOperations );
 
+    /**
+     *  Calculates the shortest path using bidirectional Dijkstra's algorithm.
+     *
+     * @param <WO> the type of weight operations
+     * @param weightOperations the class responsible for operations on weights
+     * @return a path which describes the shortest path, if any, otherwise a {@link PathNotFoundException}
will be thrown
+     */
+    <WO extends OrderedMonoid<W>> WeightedPath<V, WE, W> applyingBidirectionalDijkstra(
WO weightOperations );
+
 }

Added: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/BidirDijkstraTestCase.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/BidirDijkstraTestCase.java?rev=1484153&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/BidirDijkstraTestCase.java
(added)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/BidirDijkstraTestCase.java
Sat May 18 17:50:00 2013
@@ -0,0 +1,345 @@
+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.junit.Assert.assertEquals;
+
+import org.apache.commons.graph.Graph;
+import org.apache.commons.graph.Path;
+import org.apache.commons.graph.model.InMemoryWeightedPath;
+
+import static java.lang.String.format;
+import static java.lang.String.valueOf;
+import static org.apache.commons.graph.CommonsGraph.findShortestPath;
+import static org.apache.commons.graph.CommonsGraph.newDirectedMutableGraph;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Random;
+
+import org.apache.commons.graph.GraphException;
+import org.apache.commons.graph.builder.AbstractGraphConnection;
+import org.apache.commons.graph.model.BaseLabeledVertex;
+import org.apache.commons.graph.model.BaseLabeledWeightedEdge;
+import org.apache.commons.graph.model.UndirectedMutableGraph;
+import org.apache.commons.graph.weight.primitive.DoubleWeightBaseOperations;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import org.apache.commons.graph.WeightedPath;
+import org.apache.commons.graph.model.BaseWeightedEdge;
+import org.apache.commons.graph.model.DirectedMutableGraph;
+import org.apache.commons.graph.weight.OrderedMonoid;
+
+public final class BidirDijkstraTestCase
+{
+    private static final int TIMES = 10;
+    private static final int NODES = 5000;
+    private static final int EDGES = 100000;
+    private static final double EPSILON = 1.0e-6;
+
+    private static DirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>
graph;
+
+    private static List<BaseLabeledVertex> vertices;
+
+    private static OrderedMonoid<Double> weightOperations;
+
+    @BeforeClass
+    public static void setUp()
+    {
+        weightOperations = new DoubleWeightBaseOperations();
+
+        graph = newDirectedMutableGraph( new AbstractGraphConnection<BaseLabeledVertex,
BaseLabeledWeightedEdge<Double>>()
+        {
+            Random r = new Random();
+
+            public void connect()
+            {
+                vertices = new ArrayList<BaseLabeledVertex>();
+                for ( int i = 0; i < NODES; i++ )
+                {
+                    BaseLabeledVertex v = new BaseLabeledVertex( valueOf( i ) );
+                    addVertex( v );
+                    vertices.add( v );
+                }
+
+                // form a connected graph
+                for ( int i = 0; i < NODES - 1; i++ )
+                {
+                    addEdge( vertices.get( i ), vertices.get( i + 1 ) );
+                }
+
+                addEdge( vertices.get( NODES - 1 ) , vertices.get( 0 ) );
+
+                // we have already created #NODES edges
+                int maxEdges = Math.max(0, EDGES - NODES);
+                for ( int i = 0; i < maxEdges; i++)
+                {
+                    while ( ! addEdge( vertices.get( r.nextInt(NODES) ), vertices.get( r.nextInt(NODES)
) ) ) {
+                        // do nothing
+                    }
+                }
+            }
+
+            private boolean addEdge( BaseLabeledVertex src, BaseLabeledVertex dst )
+            {
+                try {
+                  addEdge( new BaseLabeledWeightedEdge<Double>( format( "%s -> %s",
src, dst ),
+                                                                10.0 * r.nextDouble() + 1.0
) ).from( src ).to( dst );
+                  return true;
+              } catch (GraphException e) {
+                  // ignore duplicate edge exceptions
+                  return false;
+              }
+            }
+        } );
+    }
+
+    @Test( expected = NullPointerException.class )
+    public void testNullGraph()
+    {
+        // the actual weighted path
+        findShortestPath( (Graph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>)
null )
+            .whereEdgesHaveWeights( new BaseWeightedEdge<Double>() )
+            .from( null )
+            .to( null )
+            .applyingBidirectionalDijkstra( new DoubleWeightBaseOperations() );
+    }
+
+    @Test( expected = NullPointerException.class )
+    public void testNullVertices()
+    {
+        UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>
graph =
+            new UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>();
+
+        // the actual weighted path
+        findShortestPath( graph )
+            .whereEdgesHaveWeights( new BaseWeightedEdge<Double>() )
+            .from( null )
+            .to( null )
+            .applyingBidirectionalDijkstra( new DoubleWeightBaseOperations() );
+    }
+
+    @Test( expected = NullPointerException.class )
+    public void testNullMonoid()
+    {
+        UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>
graph =
+            new UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>();
+
+        final BaseLabeledVertex a = new BaseLabeledVertex( "a" );
+        final BaseLabeledVertex b = new BaseLabeledVertex( "b" );
+        graph.addVertex( a );
+        graph.addVertex( b );
+
+        // the actual weighted path
+        findShortestPath( graph )
+            .whereEdgesHaveWeights( new BaseWeightedEdge<Double>() )
+            .from( a )
+            .to( b )
+            .applyingBidirectionalDijkstra( null );
+    }
+
+    @Test( expected = PathNotFoundException.class )
+    public void testNotConnectGraph()
+    {
+        UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>
graph =
+            new UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>();
+
+        final BaseLabeledVertex a = new BaseLabeledVertex( "a" );
+        final BaseLabeledVertex b = new BaseLabeledVertex( "b" );
+        graph.addVertex( a );
+        graph.addVertex( b );
+
+        // the actual weighted path
+        findShortestPath( graph )
+            .whereEdgesHaveWeights( new BaseWeightedEdge<Double>() )
+            .from( a )
+            .to( b )
+            .applyingBidirectionalDijkstra( new DoubleWeightBaseOperations() );
+    }
+
+    /**
+     * Test Graph and Dijkstra's solution can be seen on
+     * <a href="http://en.wikipedia.org/wiki/Dijkstra's_algorithm>Wikipedia</a>
+     */
+    @Test
+    public void findShortestPathAndVerify()
+    {
+        DirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>
graph =
+            new DirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>();
+
+        // building Graph
+
+        BaseLabeledVertex one = new BaseLabeledVertex( "1" );
+        BaseLabeledVertex two = new BaseLabeledVertex( "2" );
+        BaseLabeledVertex three = new BaseLabeledVertex( "3" );
+        BaseLabeledVertex four = new BaseLabeledVertex( "4" );
+        BaseLabeledVertex five = new BaseLabeledVertex( "5" );
+        BaseLabeledVertex six = new BaseLabeledVertex( "6" );
+
+        graph.addVertex( one );
+        graph.addVertex( two );
+        graph.addVertex( three );
+        graph.addVertex( four );
+        graph.addVertex( five );
+        graph.addVertex( six );
+
+        graph.addEdge( one, new BaseLabeledWeightedEdge<Double>( "1 -> 6", 14D ),
six );
+        graph.addEdge( one, new BaseLabeledWeightedEdge<Double>( "1 -> 3", 9D ),
three );
+        graph.addEdge( one, new BaseLabeledWeightedEdge<Double>( "1 -> 2", 7D ),
two );
+
+        graph.addEdge( two, new BaseLabeledWeightedEdge<Double>( "2 -> 3", 10D ),
three );
+        graph.addEdge( two, new BaseLabeledWeightedEdge<Double>( "2 -> 4", 15D ),
four );
+
+        graph.addEdge( three, new BaseLabeledWeightedEdge<Double>( "3 -> 6", 2D
), six );
+        graph.addEdge( three, new BaseLabeledWeightedEdge<Double>( "3 -> 4", 11D
), four );
+
+        graph.addEdge( four, new BaseLabeledWeightedEdge<Double>( "4 -> 5", 6D ),
five );
+        graph.addEdge( six, new BaseLabeledWeightedEdge<Double>( "6 -> 5", 9D ),
five );
+
+        // expected path
+
+        InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>,
Double> expected =
+            new InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>,
Double>( one, five, new DoubleWeightBaseOperations(), new BaseWeightedEdge<Double>()
);
+
+        expected.addConnectionInTail( one, new BaseLabeledWeightedEdge<Double>( "1
-> 3", 9D ), three );
+        expected.addConnectionInTail( three, new BaseLabeledWeightedEdge<Double>( "3
-> 6", 2D ), six );
+        expected.addConnectionInTail( six, new BaseLabeledWeightedEdge<Double>( "6
-> 5", 9D ), five );
+
+        // actual path
+
+        Path<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>> actual =
+                        findShortestPath( graph )
+                            .whereEdgesHaveWeights( new BaseWeightedEdge<Double>()
)
+                            .from( one )
+                            .to( five )
+                            .applyingBidirectionalDijkstra( new DoubleWeightBaseOperations()
);
+
+        // assert!
+
+        assertEquals( expected, actual );
+    }
+
+    @Test
+    public void verifyTwoNodePath() {
+        DirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>
graph =
+            new DirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>();
+
+        // building Graph
+
+        BaseLabeledVertex one = new BaseLabeledVertex( "1" );
+        BaseLabeledVertex two = new BaseLabeledVertex( "2" );
+
+        graph.addVertex( one );
+        graph.addVertex( two );
+
+        graph.addEdge( one, new BaseLabeledWeightedEdge<Double>( "1 -> 2", 14D ),
two );
+
+        // expected path
+        InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>,
Double> expected =
+            new InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>,
Double>( one, two, new DoubleWeightBaseOperations(), new BaseWeightedEdge<Double>()
);
+
+        expected.addConnectionInTail( one, new BaseLabeledWeightedEdge<Double>( "1
-> 2", 14D ), two );
+
+        // actual path
+        Path<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>> actual =
+                        findShortestPath( graph )
+                            .whereEdgesHaveWeights( new BaseWeightedEdge<Double>()
)
+                            .from( one )
+                            .to( two )
+                            .applyingBidirectionalDijkstra( new DoubleWeightBaseOperations()
);
+
+        // assert!
+        assertEquals( expected, actual );
+    }
+
+    @Test
+    public void verifyThreeNodePath() {
+        DirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>
graph =
+            new DirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>();
+
+        // building Graph
+
+        BaseLabeledVertex a = new BaseLabeledVertex( "a" );
+        BaseLabeledVertex b = new BaseLabeledVertex( "b" );
+        BaseLabeledVertex c = new BaseLabeledVertex( "c" );
+
+        graph.addVertex( a );
+        graph.addVertex( b );
+        graph.addVertex( c );
+
+        graph.addEdge( a, new BaseLabeledWeightedEdge<Double>( "a -> b", 14D ),
b );
+        graph.addEdge( b, new BaseLabeledWeightedEdge<Double>( "b -> c", 10D ),
c );
+
+        // expected path
+        InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>,
Double> expected =
+            new InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>,
Double>( a, c, new DoubleWeightBaseOperations(), new BaseWeightedEdge<Double>() );
+
+        expected.addConnectionInTail( a, new BaseLabeledWeightedEdge<Double>( "a ->
b", 14D ), b );
+        expected.addConnectionInTail( b, new BaseLabeledWeightedEdge<Double>( "b ->
c", 10D ), c );
+
+        // actual path
+        Path<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>> actual =
+                        findShortestPath( graph )
+                            .whereEdgesHaveWeights( new BaseWeightedEdge<Double>()
)
+                            .from( a )
+                            .to( c )
+                            .applyingBidirectionalDijkstra( new DoubleWeightBaseOperations()
);
+
+        // assert!
+        assertEquals( expected, actual );
+    }
+
+    @Test
+    public void compareToUnidirectional() {
+        // It is hard to get unidirectional Dijkstra's algorithm wrong;
+        // therefore compare a sequence of outputs.
+        Random r = new Random();
+
+        for ( int ii = 0; ii < TIMES; ii++ )
+        {
+            BaseLabeledVertex s = vertices.get( r.nextInt( vertices.size() ) );
+            BaseLabeledVertex t;
+
+            do
+            {
+                t = vertices.get( r.nextInt( vertices.size() ) );
+            }
+            while ( s.equals( t ) );
+
+            WeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double>
pathUni =
+                    findShortestPath( graph )
+                        .whereEdgesHaveWeights( new BaseWeightedEdge<Double>() )
+                        .from( s )
+                        .to( t )
+                        .applyingDijkstra( weightOperations );
+
+            WeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double>
pathBi =
+                    findShortestPath( graph )
+                        .whereEdgesHaveWeights( new BaseWeightedEdge<Double>() )
+                        .from( s )
+                        .to( t )
+                        .applyingBidirectionalDijkstra( weightOperations );
+
+            assertEquals( pathUni.getSize(), pathBi.getSize() );
+            assertEquals( pathUni.getWeight(), pathBi.getWeight(), EPSILON );
+        }
+    }
+}

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

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

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



Mime
View raw message