KickJava   Java API By Example, From Geeks To Geeks.

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


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  * BellmanFordShortestPathTest.java
27  * ------------------------------
28  * (C) Copyright 2006-2006, by John V. Sichi and Contributors.
29  *
30  * Original Author: John V. Sichi
31  * Contributor(s): -
32  *
33  * $Id: BellmanFordShortestPathTest.java 504 2006-07-03 02:37:26Z perfecthash $
34  *
35  * Changes
36  * -------
37  * 14-Jan-2006 : Initial revision (JVS);
38  *
39  */

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

53 public class BellmanFordShortestPathTest
54     extends ShortestPathTestCase
55 {
56
57     //~ Methods ---------------------------------------------------------------
58

59     /**
60      * .
61      */

62     public void testConstructor()
63     {
64         BellmanFordShortestPath<String JavaDoc, DefaultWeightedEdge> path;
65         Graph<String JavaDoc, DefaultWeightedEdge> g = create();
66
67         path = new BellmanFordShortestPath<String JavaDoc, DefaultWeightedEdge>(g, V3);
68
69         // find best path with no constraint on number of hops
70
assertEquals(
71             Arrays.asList(new DefaultEdge [] {
72                     e13,
73                     e12,
74                     e24,
75                     e45
76                 }),
77             path.getPathEdgeList(V5));
78         assertEquals(15.0, path.getCost(V5), 0);
79
80         // find best path within 2 hops (less than optimal)
81
path =
82             new BellmanFordShortestPath<String JavaDoc, DefaultWeightedEdge>(
83                 g,
84                 V3,
85                 2);
86         assertEquals(
87             Arrays.asList(new DefaultEdge [] {
88                     e34,
89                     e45
90                 }),
91             path.getPathEdgeList(V5));
92         assertEquals(25.0, path.getCost(V5), 0);
93
94         // find best path within 1 hop (doesn't exist!)
95
path =
96             new BellmanFordShortestPath<String JavaDoc, DefaultWeightedEdge>(
97                 g,
98                 V3,
99                 1);
100         assertNull(path.getPathEdgeList(V5));
101     }
102
103     protected List findPathBetween(
104         Graph<String JavaDoc, DefaultWeightedEdge> g,
105         String JavaDoc src,
106         String JavaDoc dest)
107     {
108         return BellmanFordShortestPath.findPathBetween(g, src, dest);
109     }
110
111     public void testWithNegativeEdges()
112     {
113         Graph<String JavaDoc, DefaultWeightedEdge> g = createWithBias(true);
114
115         List path;
116
117         path = findPathBetween(g, V1, V4);
118         assertEquals(Arrays.asList(new DefaultEdge [] {
119                     e13,
120                     e34
121                 }), path);
122
123         path = findPathBetween(g, V1, V5);
124         assertEquals(Arrays.asList(new DefaultEdge [] { e15 }), path);
125     }
126 }
127
128 // End BellmanFordShortestPathTest.java
129
Popular Tags