BellmanFordIterator


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   * BellmanFordIterator.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: BellmanFordIterator.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   * Helper class for {@link BellmanFordShortestPath}; not intended for general
50   * use.
51   */
52  class BellmanFordIterator<V, E>
53      implements Iterator<List<V>>
54  {
55  
56      //~ Static fields/initializers --------------------------------------------
57  
58      /**
59       * Error message.
60       */
61      protected final static String   NEGATIVE_UNDIRECTED_EDGE =
62          "Negative"
63          + "edge-weights are not allowed in an unidrected graph!";
64  
65      //~ Instance fields -------------------------------------------------------
66  
67      /**
68       * Graph on which shortest paths are searched.
69       */
70      protected Graph<V, E> graph;
71  
72      /**
73       * Start vertex.
74       */
75      protected V startVertex;
76  
77      /**
78       * Vertices whose shortest path cost have been improved during the previous
79       * pass.
80       */
81      private List<V> prevImprovedVertices = new ArrayList<V>();
82  
83      private Map<V, BellmanFordPathElement<V, E>> prevVertexData;
84  
85      private boolean startVertexEncountered = false;
86  
87      /**
88       * Stores the vertices that have been seen during iteration and (optionally)
89       * some additional traversal info regarding each vertex.
90       */
91      private Map<V, BellmanFordPathElement<V, E>> vertexData;
92  
93      //~ Constructors ----------------------------------------------------------
94  
95      /**
96       * @param graph
97       * @param startVertex start vertex.
98       */
99      protected BellmanFordIterator(Graph<V, E> graph, V startVertex)
100     {
101         assertBellmanFordIterator(graph, startVertex);
102 
103         this.graph = graph;
104         this.startVertex = startVertex;
105     }
106 
107     //~ Methods ---------------------------------------------------------------
108 
109     /**
110      * Returns the path element of the shortest path with less than <code>
111      * nMaxHops</code> edges between the start vertex and the end vertex.
112      *
113      * @param endVertex end vertex.
114      *
115      * @return .
116      */
117     public BellmanFordPathElement<V, E> getPathElement(V endVertex)
118     {
119         return getSeenData(endVertex);
120     }
121 
122     /**
123      * @return <code>true</code> if at least one path has been improved during
124      *         the previous pass, <code>false</code> otherwise.
125      */
126     public boolean hasNext()
127     {
128         if (!this.startVertexEncountered) {
129             encounterStartVertex();
130         }
131 
132         return !(this.prevImprovedVertices.isEmpty());
133     }
134 
135     /**
136      * Returns the list <code>Collection</code> of vertices whose path has been
137      * improved during the current pass.
138      *
139      * @see java.util.Iterator#next()
140      */
141     public List<V> next()
142     {
143         if (!this.startVertexEncountered) {
144             encounterStartVertex();
145         }
146 
147         if (hasNext()) {
148             List<V> improvedVertices = new ArrayList<V>();
149             for (int i = this.prevImprovedVertices.size() - 1; i >= 0; i--) {
150                 V vertex = this.prevImprovedVertices.get(i);
151                 for (
152                     Iterator<? extends E> iter = edgesOfIterator(vertex);
153                     iter.hasNext();) {
154                     E edge = iter.next();
155                     V oppositeVertex =
156                         Graphs.getOppositeVertex(
157                             graph,
158                             edge,
159                             vertex);
160                     if (getPathElement(oppositeVertex) != null) {
161                         boolean relaxed =
162                             relaxVertexAgain(oppositeVertex, edge);
163                         if (relaxed) {
164                             improvedVertices.add(oppositeVertex);
165                         }
166                     } else {
167                         relaxVertex(oppositeVertex, edge);
168                         improvedVertices.add(oppositeVertex);
169                     }
170                 }
171             }
172 
173             savePassData(improvedVertices);
174 
175             return improvedVertices;
176         }
177 
178         throw new NoSuchElementException();
179     }
180 
181     /**
182      * Unsupported
183      *
184      * @see java.util.Iterator#remove()
185      */
186     public void remove()
187     {
188         throw new UnsupportedOperationException  ();
189     }
190 
191     /**
192      * @param edge
193      *
194      * @throws IllegalArgumentException if the graph is undirected and the
195      *         edge-weight is negative.
196      */
197     protected void assertValidEdge(E edge)
198     {
199         if (this.graph instanceof UndirectedGraph) {
200             if (graph.getEdgeWeight(edge) < 0) {
201                 throw new IllegalArgumentException  (NEGATIVE_UNDIRECTED_EDGE);
202             }
203         }
204     }
205 
206     /**
207      * Costs taken into account are the weights stored in <code>Edge</code>
208      * objects.
209      *
210      * @param vertex a vertex which has just been encountered.
211      * @param edge the edge via which the vertex was encountered.
212      *
213      * @return the cost obtained by concatenation.
214      *
215      * @see Graph#getEdgeWeight(E)
216      */
217     protected double calculatePathCost(V vertex, E edge)
218     {
219         V oppositeVertex = Graphs.getOppositeVertex(graph, edge, vertex);
220 
221         // we get the data of the previous pass.
222         BellmanFordPathElement<V, E> oppositePrevData =
223             getPrevSeenData(oppositeVertex);
224 
225         double pathCost = graph.getEdgeWeight(edge);
226 
227         if (!oppositePrevData.getVertex().equals(this.startVertex)) {
228             // if it's not the start vertex, we add the cost of the previous
229             // pass.
230             pathCost += oppositePrevData.getCost();
231         }
232 
233         return pathCost;
234     }
235 
236     /**
237      * Returns an iterator to loop over outgoing edges <code>Edge</code> of the
238      * vertex.
239      *
240      * @param vertex
241      *
242      * @return .
243      */
244     protected Iterator<E> edgesOfIterator(V vertex)
245     {
246         if (this.graph instanceof DirectedGraph) {
247             return
248                 ((DirectedGraph<V, E>) this.graph).outgoingEdgesOf(vertex)
249                 .iterator();
250         } else {
251             return this.graph.edgesOf(vertex).iterator();
252         }
253     }
254 
255     /**
256      * Access the data stored for a seen vertex in the previous pass.
257      *
258      * @param vertex a vertex which has already been seen.
259      *
260      * @return data associated with the seen vertex or <code>null</code> if no
261      *         data was associated with the vertex.
262      */
263     protected BellmanFordPathElement<V, E> getPrevSeenData(V vertex)
264     {
265         return this.prevVertexData.get(vertex);
266     }
267 
268     /**
269      * Access the data stored for a seen vertex in the current pass.
270      *
271      * @param vertex a vertex which has already been seen.
272      *
273      * @return data associated with the seen vertex or <code>null</code> if no
274      *         data was associated with the vertex.
275      */
276     protected BellmanFordPathElement<V, E> getSeenData(V vertex)
277     {
278         return this.vertexData.get(vertex);
279     }
280 
281     /**
282      * Determines whether a vertex has been seen yet by this traversal.
283      *
284      * @param vertex vertex in question.
285      *
286      * @return <tt>true</tt> if vertex has already been seen.
287      */
288     protected boolean isSeenVertex(V vertex)
289     {
290         return this.vertexData.containsKey(vertex);
291     }
292 
293     /**
294      * @param vertex
295      * @param data
296      *
297      * @return .
298      */
299     protected BellmanFordPathElement<V, E> putPrevSeenData(
300         V vertex,
301         BellmanFordPathElement<V, E> data)
302     {
303         if (this.prevVertexData == null) {
304             this.prevVertexData =
305                 new HashMap<V, BellmanFordPathElement<V, E>>();
306         }
307 
308         return this.prevVertexData.put(vertex, data);
309     }
310 
311     /**
312      * Stores iterator-dependent data for a vertex that has been seen during the
313      * current pass.
314      *
315      * @param vertex a vertex which has been seen.
316      * @param data data to be associated with the seen vertex.
317      *
318      * @return previous value associated with specified vertex or <code>
319      *         null</code> if no data was associated with the vertex.
320      */
321     protected BellmanFordPathElement<V, E> putSeenData(
322         V vertex,
323         BellmanFordPathElement<V, E> data)
324     {
325         if (this.vertexData == null) {
326             this.vertexData = new HashMap<V, BellmanFordPathElement<V, E>>();
327         }
328 
329         return this.vertexData.put(vertex, data);
330     }
331 
332     private void assertBellmanFordIterator(Graph<V, E> graph, V startVertex)
333     {
334         if (!(graph.containsVertex(startVertex))) {
335             throw new IllegalArgumentException  (
336                 "Graph must contain the start vertex!");
337         }
338     }
339 
340     /**
341      * The first time we see a vertex, make up a new entry for it.
342      *
343      * @param vertex a vertex which has just been encountered.
344      * @param edge the edge via which the vertex was encountered.
345      * @param cost cost of the created path element.
346      *
347      * @return the new entry.
348      */
349     private BellmanFordPathElement<V, E> createSeenData(
350         V vertex,
351         E edge,
352         double cost)
353     {
354         BellmanFordPathElement<V, E> prevPathElement =
355             getPrevSeenData(
356                 Graphs.getOppositeVertex(graph, edge, vertex));
357 
358         BellmanFordPathElement<V, E> data =
359             new BellmanFordPathElement<V, E>(
360                 graph,
361                 prevPathElement,
362                 edge,
363                 cost);
364 
365         return data;
366     }
367 
368     private void encounterStartVertex()
369     {
370         BellmanFordPathElement<V, E> data =
371             new BellmanFordPathElement<V, E>(
372                 this.startVertex);
373 
374         // first the only vertex considered as improved is the start vertex.
375         this.prevImprovedVertices.add(this.startVertex);
376 
377         putSeenData(this.startVertex, data);
378         putPrevSeenData(this.startVertex, data);
379 
380         this.startVertexEncountered = true;
381     }
382 
383     /**
384      * Upates data first time a vertex is reached by a path.
385      *
386      * @param vertex a vertex which has just been encountered.
387      * @param edge the edge via which the vertex was encountered.
388      */
389     private void relaxVertex(V vertex, E edge)
390     {
391         assertValidEdge(edge);
392 
393         double shortestPathCost = calculatePathCost(vertex, edge);
394 
395         BellmanFordPathElement<V, E> data =
396             createSeenData(vertex, edge,
397                 shortestPathCost);
398 
399         putSeenData(vertex, data);
400     }
401 
402     /**
403      * Check if the cost of the best path so far reaching the specified vertex
404      * could be improved if the vertex is reached through the specified edge.
405      *
406      * @param vertex a vertex which has just been encountered.
407      * @param edge the edge via which the vertex was encountered.
408      *
409      * @return <code>true</code> if the cost has been improved, <code>
410      *         false</code> otherwise.
411      */
412     private boolean relaxVertexAgain(V vertex, E edge)
413     {
414         assertValidEdge(edge);
415 
416         double candidateCost = calculatePathCost(vertex, edge);
417 
418         // we get the data of the previous pass.
419         BellmanFordPathElement<V, E> oppositePrevData =
420             getPrevSeenData(
421                 Graphs.getOppositeVertex(graph, edge, vertex));
422 
423         BellmanFordPathElement<V, E> pathElement = getSeenData(vertex);
424         return pathElement.improve(oppositePrevData, edge, candidateCost);
425     }
426 
427     private void savePassData(List<V> improvedVertices)
428     {
429         for (V vertex : improvedVertices) {
430             BellmanFordPathElement<V, E> orig = getSeenData(vertex);
431             BellmanFordPathElement<V, E> clonedData =
432                 new BellmanFordPathElement<V, E>(orig);
433             putPrevSeenData(vertex, clonedData);
434         }
435 
436         this.prevImprovedVertices = improvedVertices;
437     }
438 }
439
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags