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 [[email protected]] 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
