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 2013/05/18 19:50:01 UTC
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/
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