KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > jgrapht > alg > ShortestPathTestCase


1 /* ==========================================
2  * JGraphT : a free Java graph-theory library
3  * ==========================================
4  *
5  * Project Info: http://jgrapht.sourceforge.net/
6  * Project Creator: Barak Naveh (http://sourceforge.net/users/barak_naveh)
7  *
8  * (C) Copyright 2003-2006, by Barak Naveh and Contributors.
9  *
10  * This library is free software; you can redistribute it and/or modify it
11  * under the terms of the GNU Lesser General Public License as published by
12  * the Free Software Foundation; either version 2.1 of the License, or
13  * (at your option) any later version.
14  *
15  * This library is distributed in the hope that it will be useful, but
16  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
17  * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
18  * License for more details.
19  *
20  * You should have received a copy of the GNU Lesser General Public License
21  * along with this library; if not, write to the Free Software Foundation,
22  * Inc.,
23  * 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
24  */

25 /* ------------------------------
26  * ShortestPathTestCase.java
27  * ------------------------------
28  * (C) Copyright 2003-2006, by John V. Sichi and Contributors.
29  *
30  * Original Author: John V. Sichi
31  * Contributor(s): -
32  *
33  * $Id: ShortestPathTestCase.java 504 2006-07-03 02:37:26Z perfecthash $
34  *
35  * Changes
36  * -------
37  * 14-Jan-2006 : Factored out of DijkstraShortestPathTest (JVS);
38  *
39  */

40 package org.jgrapht.alg;
41
42 import java.util.*;
43
44 import junit.framework.*;
45
46 import org.jgrapht.*;
47 import org.jgrapht.graph.*;
48
49
50 /**
51  * .
52  *
53  * @author John V. Sichi
54  */

55 public abstract class ShortestPathTestCase
56     extends TestCase
57 {
58
59     //~ Static fields/initializers --------------------------------------------
60

61     static final String JavaDoc V1 = "v1";
62     static final String JavaDoc V2 = "v2";
63     static final String JavaDoc V3 = "v3";
64     static final String JavaDoc V4 = "v4";
65     static final String JavaDoc V5 = "v5";
66
67     //~ Instance fields -------------------------------------------------------
68

69     DefaultWeightedEdge e12;
70     DefaultWeightedEdge e13;
71     DefaultWeightedEdge e15;
72     DefaultWeightedEdge e24;
73     DefaultWeightedEdge e34;
74     DefaultWeightedEdge e45;
75
76     //~ Methods ---------------------------------------------------------------
77

78     /**
79      * .
80      */

81     public void testPathBetween()
82     {
83         List path;
84         Graph<String JavaDoc, DefaultWeightedEdge> g = create();
85
86         path = findPathBetween(g, V1, V2);
87         assertEquals(Arrays.asList(new DefaultEdge [] { e12 }), path);
88
89         path = findPathBetween(g, V1, V4);
90         assertEquals(Arrays.asList(new DefaultEdge [] {
91                     e12,
92                     e24
93                 }), path);
94
95         path = findPathBetween(g, V1, V5);
96         assertEquals(Arrays.asList(new DefaultEdge [] {
97                     e12,
98                     e24,
99                     e45
100                 }), path);
101
102         path = findPathBetween(g, V3, V4);
103         assertEquals(Arrays.asList(new DefaultEdge [] {
104                     e13,
105                     e12,
106                     e24
107                 }), path);
108     }
109
110     protected abstract List findPathBetween(
111         Graph<String JavaDoc, DefaultWeightedEdge> g,
112         String JavaDoc src,
113         String JavaDoc dest);
114
115     protected Graph<String JavaDoc, DefaultWeightedEdge> create()
116     {
117         return createWithBias(false);
118     }
119
120     protected Graph<String JavaDoc, DefaultWeightedEdge> createWithBias(
121         boolean negate)
122     {
123         Graph<String JavaDoc, DefaultWeightedEdge> g;
124         double bias = 1;
125         if (negate) {
126             // negative-weight edges are being tested, so only a directed graph
127
// makes sense
128
g =
129                 new SimpleDirectedWeightedGraph<String JavaDoc, DefaultWeightedEdge>(
130                     DefaultWeightedEdge.class);
131             bias = -1;
132         } else {
133             // by default, use an undirected graph
134
g =
135                 new SimpleWeightedGraph<String JavaDoc, DefaultWeightedEdge>(
136                     DefaultWeightedEdge.class);
137         }
138
139         g.addVertex(V1);
140         g.addVertex(V2);
141         g.addVertex(V3);
142         g.addVertex(V4);
143         g.addVertex(V5);
144
145         e12 = Graphs.addEdge(g, V1, V2, bias * 2);
146
147         e13 = Graphs.addEdge(g, V1, V3, bias * 3);
148
149         e24 = Graphs.addEdge(g, V2, V4, bias * 5);
150
151         e34 = Graphs.addEdge(g, V3, V4, bias * 20);
152
153         e45 = Graphs.addEdge(g, V4, V5, bias * 5);
154
155         e15 = Graphs.addEdge(g, V1, V5, bias * 100);
156
157         return g;
158     }
159 }
160
Popular Tags