1   package org.apache.commons.graph.shortestpath;
2   
3   import org.apache.commons.graph.Path;
4   import org.apache.commons.graph.model.BaseLabeledVertex;
5   import org.apache.commons.graph.model.BaseLabeledWeightedEdge;
6   import org.apache.commons.graph.model.DirectedMutableWeightedGraph;
7   import org.apache.commons.graph.model.InMemoryPath;
8   import org.junit.Test;
9   
10  /*
11   * Licensed to the Apache Software Foundation (ASF) under one
12   * or more contributor license agreements.  See the NOTICE file
13   * distributed with this work for additional information
14   * regarding copyright ownership.  The ASF licenses this file
15   * to you under the Apache License, Version 2.0 (the
16   * "License"); you may not use this file except in compliance
17   * with the License.  You may obtain a copy of the License at
18   *
19   *   http://www.apache.org/licenses/LICENSE-2.0
20   *
21   * Unless required by applicable law or agreed to in writing,
22   * software distributed under the License is distributed on an
23   * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
24   * KIND, either express or implied.  See the License for the
25   * specific language governing permissions and limitations
26   * under the License.
27   */
28  
29  import static org.apache.commons.graph.shortestpath.Dijkstra.findShortestPath;
30  import static junit.framework.Assert.assertEquals;
31  
32  public final class DijkstraTestCase
33  {
34  
35      /**
36       * Test Graph and Dijkstra's solution can be seen on
37       * Wikipedia {@link http://en.wikipedia.org/wiki/Dijkstra's_algorithm}
38       */
39      @Test
40      public void shortestPath1()
41      {
42          // test Graph
43  
44          BaseLabeledVertex one = new BaseLabeledVertex( "1" );
45          BaseLabeledVertex two = new BaseLabeledVertex( "2" );
46          BaseLabeledVertex three = new BaseLabeledVertex( "3" );
47          BaseLabeledVertex four = new BaseLabeledVertex( "4" );
48          BaseLabeledVertex five = new BaseLabeledVertex( "5" );
49          BaseLabeledVertex six = new BaseLabeledVertex( "6" );
50  
51          DirectedMutableWeightedGraph<BaseLabeledVertex, BaseLabeledWeightedEdge> testGraph =
52              new DirectedMutableWeightedGraph<BaseLabeledVertex, BaseLabeledWeightedEdge>();
53  
54          testGraph.addVertex( one );
55          testGraph.addVertex( two );
56          testGraph.addVertex( three );
57          testGraph.addVertex( four );
58          testGraph.addVertex( five );
59          testGraph.addVertex( six );
60  
61          testGraph.addEdge( new BaseLabeledWeightedEdge( "", one, six, 14D ) );
62          testGraph.addEdge( new BaseLabeledWeightedEdge( "", one, three, 9D ) );
63          testGraph.addEdge( new BaseLabeledWeightedEdge( "", one, two, 7D ) );
64  
65          testGraph.addEdge( new BaseLabeledWeightedEdge( "", two, three, 10D ) );
66          testGraph.addEdge( new BaseLabeledWeightedEdge( "", two, four, 15D ) );
67  
68          testGraph.addEdge( new BaseLabeledWeightedEdge( "", three, six, 2D ) );
69          testGraph.addEdge( new BaseLabeledWeightedEdge( "", three, four, 11D ) );
70  
71          testGraph.addEdge( new BaseLabeledWeightedEdge( "", four, five, 6D ) );
72          testGraph.addEdge( new BaseLabeledWeightedEdge( "", six, five, 9D ) );
73  
74          // expected path
75  
76          Path<BaseLabeledVertex, BaseLabeledWeightedEdge> actual = findShortestPath( testGraph, one, five );
77  
78          InMemoryPath<BaseLabeledVertex, BaseLabeledWeightedEdge> expected =
79              new InMemoryPath<BaseLabeledVertex, BaseLabeledWeightedEdge>( one, five, 20D );
80  
81          expected.addVertexInTail( three );
82          expected.addVertexInTail( six );
83          expected.addVertexInTail( five );
84  
85          expected.addEdgeInTail( new BaseLabeledWeightedEdge( "", one, three, 9D ) );
86          expected.addEdgeInTail( new BaseLabeledWeightedEdge( "", three, six, 2D ) );
87          expected.addEdgeInTail( new BaseLabeledWeightedEdge( "", six, five, 9D ) );
88  
89          assertEquals( expected, actual );
90      }
91  
92  }