KickJava   Java API By Example, From Geeks To Geeks.

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


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  * BellmanFordShortestPath.java
27  * -------------------------
28  * (C) Copyright 2006-2006, by France Telecom and Contributors.
29  *
30  * Original Author: Guillaume Boulmier and Contributors.
31  * Contributor(s): John V. Sichi
32  *
33  * $Id: BellmanFordShortestPath.java 504 2006-07-03 02:37:26Z perfecthash $
34  *
35  * Changes
36  * -------
37  * 05-Jan-2006 : Initial revision (GB);
38  * 14-Jan-2006 : Added support for generics (JVS);
39  *
40  */
41 package org.jgrapht.alg;
42
43 import java.util.*;
44
45 import org.jgrapht.*;
46
47
48 /**
49  * <a HREF="http://www.nist.gov/dads/HTML/dijkstraalgo.html">Bellman-Ford
50  * algorithm</a>: weights could be negative, paths could be constrained by a
51  * maximum number of edges.
52  */
53 public class BellmanFordShortestPath<V, E>
54 {
55
56     //~ Instance fields -------------------------------------------------------
57
58     /**
59      * Graph on which shortest paths are searched.
60      */
61     protected Graph<V, E> graph;
62
63     /**
64      * Start vertex.
65      */
66     protected V startVertex;
67
68     private BellmanFordIterator<V, E> iter;
69
70     /**
71      * Maximum number of edges of the calculated paths.
72      */
73     private int nMaxHops;
74
75     private int passNumber;
76
77     //~ Constructors ----------------------------------------------------------
78
79     /**
80      * Creates an object to calculate shortest paths between the start vertex
81      * and others vertices using the Bellman-Ford algorithm.
82      *
83      * @param graph
84      * @param startVertex
85      */
86     public BellmanFordShortestPath(Graph<V, E> graph, V startVertex)
87     {
88         this(graph, startVertex, graph.vertexSet().size() - 1);
89     }
90
91     /**
92      * Creates an object to calculate shortest paths between the start vertex
93      * and others vertices using the Bellman-Ford algorithm.
94      *
95      * @param graph
96      * @param startVertex
97      * @param nMaxHops maximum number of edges of the calculated paths.
98      */
99     public BellmanFordShortestPath(
100         Graph<V, E> graph,
101         V startVertex,
102         int nMaxHops)
103     {
104         this.startVertex = startVertex;
105         this.nMaxHops = nMaxHops;
106         this.graph = graph;
107
108         this.passNumber = 1;
109     }
110
111     //~ Methods ---------------------------------------------------------------
112
113     /**
114      * @param endVertex end vertex.
115      *
116      * @return the cost of the shortest path between the start vertex and the
117      * end vertex.
118      */
119     public double getCost(V endVertex)
120     {
121         lazyCalculate();
122
123         assertGetPath(endVertex);
124
125         return this.iter.getPathElement(endVertex).getCost();
126     }
127
128     /**
129      * @param endVertex end vertex.
130      *
131      * @return list of <code>Edge</code>, or null if no path exists between the
132      * start vertex and the end vertex.
133      */
134     public List<E> getPathEdgeList(V endVertex)
135     {
136         assertGetPath(endVertex);
137
138         lazyCalculate();
139
140         if (this.iter.getPathElement(endVertex) == null) {
141             return null;
142         }
143
144         return createPath(endVertex);
145     }
146
147     private void assertGetPath(V endVertex)
148     {
149         if (endVertex.equals(this.startVertex)) {
150             throw new IllegalArgumentException JavaDoc(
151                 "The end vertex is the same as the start vertex!");
152         }
153
154         if (!this.graph.containsVertex(endVertex)) {
155             throw new IllegalArgumentException JavaDoc(
156                 "Graph must contain the end vertex!");
157         }
158     }
159
160     /**
161      * Complexity = O(length of path)
162      *
163      * @param endVertex end vertex.
164      *
165      * @return list of <code>Edge</code>.
166      */
167     private List<E> createPath(V endVertex)
168     {
169         AbstractPathElement<V, E> pathElement =
170             this.iter.getPathElement(endVertex);
171
172         return pathElement.createEdgeListPath();
173     }
174
175     private void lazyCalculate()
176     {
177         if (this.iter == null) {
178             this.iter =
179                 new BellmanFordIterator<V, E>(this.graph, this.startVertex);
180         }
181
182         // at the i-th pass the shortest paths with less (or equal) than i edges
183 // are calculated.
184 for (
185             ;
186             (this.passNumber <= this.nMaxHops) && this.iter.hasNext();
187             this.passNumber++) {
188             this.iter.next();
189         }
190     }
191
192     /**
193      * Convenience method to find the shortest path via a single static method
194      * call. If you need a more advanced search (e.g. limited by hops, or
195      * computation of the path length), use the constructor instead.
196      *
197      * @param graph the graph to be searched
198      * @param startVertex the vertex at which the path should start
199      * @param endVertex the vertex at which the path should end
200      *
201      * @return List of Edges, or null if no path exists
202      */
203     public static <V, E> List<E> findPathBetween(
204         Graph<V, E> graph,
205         V startVertex,
206         V endVertex)
207     {
208         BellmanFordShortestPath<V, E> alg =
209             new BellmanFordShortestPath<V, E>(
210                 graph,
211                 startVertex);
212
213         return alg.getPathEdgeList(endVertex);
214     }
215 }
216
Popular Tags