ClosestFirstIterator


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   * ClosestFirstIterator.java
27   * -------------------------
28   * (C) Copyright 2003-2006, by John V. Sichi and Contributors.
29   *
30   * Original Author:  John V. Sichi
31   * Contributor(s):   Barak Naveh
32   *
33   * $Id: ClosestFirstIterator.java 504 2006-07-03 02:37:26Z perfecthash $
34   *
35   * Changes
36   * -------
37   * 02-Sep-2003 : Initial revision (JVS);
38   * 31-Jan-2004 : Reparented and changed interface to parent class (BN);
39   * 29-May-2005 : Added radius support (JVS);
40   * 06-Jun-2005 : Made generic (CH);
41   *
42   */
43  package org.jgrapht.traverse;
44  
45  import org.jgrapht.*;
46  import org.jgrapht.util.*;
47  
48  
49  /**
50   * A closest-first iterator for a directed or undirected graph. For this
51   * iterator to work correctly the graph must not be modified during iteration.
52   * Currently there are no means to ensure that, nor to fail-fast. The results of
53   * such modifications are undefined.
54   *
55   * <p>The metric for <i>closest</i> here is the path length from a start vertex.
56   * Graph.getEdgeWeight(Edge) is summed to calculate path length. Negative edge
57   * weights will result in an IllegalArgumentException. Optionally, path length
58   * may be bounded by a finite radius.</p>
59   *
60   * @author John V. Sichi
61   * @since Sep 2, 2003
62   */
63  public class ClosestFirstIterator<V, E>
64      extends CrossComponentIterator<V, E, FibonacciHeapNode<ClosestFirstIterator.QueueEntry<V, E>>>
65  {
66  
67      //~ Instance fields -------------------------------------------------------
68  
69      /**
70       * Priority queue of fringe vertices.
71       */
72      private FibonacciHeap<QueueEntry<V, E>> heap =
73          new FibonacciHeap<QueueEntry<V, E>>();
74  
75      /**
76       * Maximum distance to search.
77       */
78      private double radius = Double.POSITIVE_INFINITY;
79  
80      //~ Constructors ----------------------------------------------------------
81  
82      /**
83       * Creates a new closest-first iterator for the specified graph.
84       *
85       * @param g the graph to be iterated.
86       */
87      public ClosestFirstIterator(Graph<V, E> g)
88      {
89          this(g, null);
90      }
91  
92      /**
93       * Creates a new closest-first iterator for the specified graph. Iteration
94       * will start at the specified start vertex and will be limited to the
95       * connected component that includes that vertex. If the specified start
96       * vertex is <code>null</code>, iteration will start at an arbitrary vertex
97       * and will not be limited, that is, will be able to traverse all the graph.
98       *
99       * @param g the graph to be iterated.
100      * @param startVertex the vertex iteration to be started.
101      */
102     public ClosestFirstIterator(Graph<V, E> g, V startVertex)
103     {
104         this(g, startVertex, Double.POSITIVE_INFINITY);
105     }
106 
107     /**
108      * Creates a new radius-bounded closest-first iterator for the specified
109      * graph. Iteration will start at the specified start vertex and will be
110      * limited to the subset of the connected component which includes that
111      * vertex and is reachable via paths of length less than or equal to the
112      * specified radius.  The specified start vertex may not be <code>
113      * null</code>.
114      *
115      * @param g the graph to be iterated.
116      * @param startVertex the vertex iteration to be started.
117      * @param radius limit on path length, or Double.POSITIVE_INFINITY for
118      *               unbounded search.
119      */
120     public ClosestFirstIterator(Graph<V, E> g, V startVertex, double radius)
121     {
122         super(g, startVertex);
123         this.radius = radius;
124         checkRadiusTraversal(isCrossComponentTraversal());
125     }
126 
127     //~ Methods ---------------------------------------------------------------
128 
129     // override AbstractGraphIterator
130     public void setCrossComponentTraversal(boolean crossComponentTraversal)
131     {
132         checkRadiusTraversal(crossComponentTraversal);
133         super.setCrossComponentTraversal(crossComponentTraversal);
134     }
135 
136     /**
137      * Get the length of the shortest path known to the given vertex.  If the
138      * vertex has already been visited, then it is truly the shortest path
139      * length; otherwise, it is the best known upper bound.
140      *
141      * @param vertex vertex being sought from start vertex
142      *
143      * @return length of shortest path known, or Double.POSITIVE_INFINITY if no
144      *         path found yet
145      */
146     public double getShortestPathLength(V vertex)
147     {
148         FibonacciHeapNode<QueueEntry<V, E>> node = getSeenData(vertex);
149 
150         if (node == null) {
151             return Double.POSITIVE_INFINITY;
152         }
153 
154         return node.getKey();
155     }
156 
157     /**
158      * Get the spanning tree edge reaching a vertex which has been seen already
159      * in this traversal.  This edge is the last link in the shortest known path
160      * between the start vertex and the requested vertex.  If the vertex has
161      * already been visited, then it is truly the minimum spanning tree edge;
162      * otherwise, it is the best candidate seen so far.
163      *
164      * @param vertex the spanned vertex.
165      *
166      * @return the spanning tree edge, or null if the vertex either has not been
167      *         seen yet or is the start vertex.
168      */
169     public E getSpanningTreeEdge(V vertex)
170     {
171         FibonacciHeapNode<QueueEntry<V, E>> node = getSeenData(vertex);
172 
173         if (node == null) {
174             return null;
175         }
176 
177         return node.getData().spanningTreeEdge;
178     }
179 
180     /**
181      * @see CrossComponentIterator#isConnectedComponentExhausted()
182      */
183     protected boolean isConnectedComponentExhausted()
184     {
185         if (heap.size() == 0) {
186             return true;
187         } else {
188             if (heap.min().getKey() > radius) {
189                 heap.clear();
190 
191                 return true;
192             } else {
193                 return false;
194             }
195         }
196     }
197 
198     /**
199      * @see CrossComponentIterator#encounterVertex(Object, Object)
200      */
201     protected void encounterVertex(V vertex, E edge)
202     {
203         FibonacciHeapNode<QueueEntry<V, E>> node = createSeenData(vertex, edge);
204         putSeenData(vertex, node);
205         heap.insert(node, node.getKey());
206     }
207 
208     /**
209      * Override superclass.  When we see a vertex again, we need to see if the
210      * new edge provides a shorter path than the old edge.
211      *
212      * @param vertex the vertex re-encountered
213      * @param edge the edge via which the vertex was re-encountered
214      */
215     protected void encounterVertexAgain(V vertex, E edge)
216     {
217         FibonacciHeapNode<QueueEntry<V, E>> node = getSeenData(vertex);
218 
219         if (node.getData().frozen) {
220             // no improvement for this vertex possible
221             return;
222         }
223 
224         double candidatePathLength = calculatePathLength(vertex, edge);
225 
226         if (candidatePathLength < node.getKey()) {
227             node.getData().spanningTreeEdge = edge;
228             heap.decreaseKey(node, candidatePathLength);
229         }
230     }
231 
232     /**
233      * @see CrossComponentIterator#provideNextVertex()
234      */
235     protected V provideNextVertex()
236     {
237         FibonacciHeapNode<QueueEntry<V, E>> node = heap.removeMin();
238         node.getData().frozen = true;
239 
240         return node.getData().vertex;
241     }
242 
243     private void assertNonNegativeEdge(E edge)
244     {
245         if (getGraph().getEdgeWeight(edge) < 0) {
246             throw new IllegalArgumentException  (
247                 "negative edge weights not allowed");
248         }
249     }
250 
251     /**
252      * Determine path length to a vertex via an edge, using the path length for
253      * the opposite vertex.
254      *
255      * @param vertex the vertex for which to calculate the path length.
256      * @param edge the edge via which the path is being extended.
257      *
258      * @return calculated path length.
259      */
260     private double calculatePathLength(V vertex, E edge)
261     {
262         assertNonNegativeEdge(edge);
263 
264         V otherVertex = Graphs.getOppositeVertex(getGraph(), edge, vertex);
265         FibonacciHeapNode<QueueEntry<V, E>> otherEntry =
266             getSeenData(otherVertex);
267 
268         return otherEntry.getKey()
269             + getGraph().getEdgeWeight(edge);
270     }
271 
272     private void checkRadiusTraversal(boolean crossComponentTraversal)
273     {
274         if (crossComponentTraversal && (radius != Double.POSITIVE_INFINITY)) {
275             throw new IllegalArgumentException  (
276                 "radius may not be specified for cross-component traversal");
277         }
278     }
279 
280     /**
281      * The first time we see a vertex, make up a new heap node for it.
282      *
283      * @param vertex a vertex which has just been encountered.
284      * @param edge the edge via which the vertex was encountered.
285      *
286      * @return the new heap node.
287      */
288     private FibonacciHeapNode<QueueEntry<V, E>> createSeenData(
289         V vertex,
290         E edge)
291     {
292         double shortestPathLength;
293 
294         if (edge == null) {
295             shortestPathLength = 0;
296         } else {
297             shortestPathLength = calculatePathLength(vertex, edge);
298         }
299 
300         QueueEntry<V, E> entry = new QueueEntry<V, E>();
301         entry.vertex = vertex;
302         entry.spanningTreeEdge = edge;
303 
304         return
305             new FibonacciHeapNode<QueueEntry<V, E>>(
306                 entry,
307                 shortestPathLength);
308     }
309 
310     //~ Inner Classes ---------------------------------------------------------
311 
312     /**
313      * Private data to associate with each entry in the priority queue.
314      */
315     static class QueueEntry<V, E>
316     {
317         /**
318          * Best spanning tree edge to vertex seen so far.
319          */
320         E spanningTreeEdge;
321 
322         /**
323          * The vertex reached.
324          */
325         V vertex;
326 
327         /**
328          * True once spanningTreeEdge is guaranteed to be the true minimum.
329          */
330         boolean frozen;
331 
332         QueueEntry()
333         {
334         }
335     }
336 }
337
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags