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
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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
37
38
39 @Test
40 public void shortestPath1()
41 {
42
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
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 }