Coverage details for edu.uci.ics.jung.algorithms.shortestpath.DijkstraShortestPath

LineHitsSource
1 /*
2 * Copyright (c) 2003, the JUNG Project and the Regents of the University
3 * of California
4 * All rights reserved.
5 *
6 * This software is open-source under the BSD license; see either
7 * "license.txt" or
8 * http://jung.sourceforge.net/license.txt for a description.
9 */
10 package edu.uci.ics.jung.algorithms.shortestpath;
11  
12 import java.util.HashMap;
13 import java.util.HashSet;
14 import java.util.LinkedHashMap;
15 import java.util.LinkedList;
16 import java.util.List;
17 import java.util.Map;
18 import java.util.Set;
19  
20 import edu.uci.ics.jung.graph.ArchetypeEdge;
21 import edu.uci.ics.jung.graph.ArchetypeGraph;
22 import edu.uci.ics.jung.graph.ArchetypeVertex;
23 import edu.uci.ics.jung.graph.Edge;
24 import edu.uci.ics.jung.graph.Vertex;
25 import edu.uci.ics.jung.graph.decorators.NumberEdgeValue;
26 import edu.uci.ics.jung.utils.Pair;
27  
28 /**
29  * <p>Calculates distances and shortest paths using Dijkstra's
30  * single-source-shortest-path algorithm. This is a lightweight
31  * extension of <code>DijkstraDistance</code> that also stores
32  * path information, so that the shortest paths can be reconstructed.</p>
33  *
34  * <p> The elements in the maps returned by
35  * <code>getIncomingEdgeMap</code> are ordered (that is, returned
36  * by the iterator) by nondecreasing distance from <code>source</code>.</p>
37  *
38  * @author Joshua O'Madadhain
39  * @see DijkstraDistance
40  */
41 public class DijkstraShortestPath extends DijkstraDistance implements ShortestPath
42 {
43     /**
44      * <p>Creates an instance of <code>DijkstraShortestPath</code> for
45      * the specified graph and the specified method of extracting weights
46      * from edges, which caches results locally if and only if
47      * <code>cached</code> is <code>true</code>.
48      *
49      * @param g the graph on which distances will be calculated
50      * @param nev the class responsible for returning weights for edges
51      * @param cached specifies whether the results are to be cached
52      */
53     public DijkstraShortestPath(ArchetypeGraph g, NumberEdgeValue nev, boolean cached)
54     {
5540        super(g, nev, cached);
5640    }
57     
58     /**
59      * <p>Creates an instance of <code>DijkstraShortestPath</code> for
60      * the specified graph and the specified method of extracting weights
61      * from edges, which caches results locally.
62      *
63      * @param g the graph on which distances will be calculated
64      * @param nev the class responsible for returning weights for edges
65      */
66     public DijkstraShortestPath(ArchetypeGraph g, NumberEdgeValue nev)
67     {
684        super(g, nev);
694    }
70     
71     /**
72      * <p>Creates an instance of <code>DijkstraShortestPath</code> for
73      * the specified unweighted graph (that is, all weights 1) which
74      * caches results locally.
75      *
76      * @param g the graph on which distances will be calculated
77      */
78     public DijkstraShortestPath(ArchetypeGraph g)
79     {
800        super(g);
810    }
82  
83     /**
84      * <p>Creates an instance of <code>DijkstraShortestPath</code> for
85      * the specified unweighted graph (that is, all weights 1) which
86      * caches results locally.
87      *
88      * @param g the graph on which distances will be calculated
89      * @param cached specifies whether the results are to be cached
90      */
91     public DijkstraShortestPath(ArchetypeGraph g, boolean cached)
92     {
930        super(g, cached);
940    }
95     
96     protected SourceData getSourceData(ArchetypeVertex source)
97     {
981702        SourceData sd = (SourcePathData)sourceMap.get(source);
991702        if (sd == null)
100964            sd = new SourcePathData(source);
1011702        return sd;
102     }
103     
104     /**
105      * <p>Returns the last edge on a shortest path from <code>source</code>
106      * to <code>target</code>, or null if <code>target</code> is not
107      * reachable from <code>source</code>.</p>
108      *
109      * <p>If either vertex is not in the graph for which this instance
110      * was created, throws <code>IllegalArgumentException</code>.</p>
111      */
112     public Edge getIncomingEdge(Vertex source, Vertex target)
113     {
114404        if (source.getGraph() != g)
1152            throw new IllegalArgumentException("Specified source vertex " +
116                     source + " is not part of graph " + g);
117  
118402        if (target.getGraph() != g)
1192            throw new IllegalArgumentException("Specified target vertex " +
120                     target + " is not part of graph " + g);
121  
122400        Set targets = new HashSet();
123400        targets.add(target);
124400        singleSourceShortestPath(source, targets, g.numVertices());
125400        Map incomingEdgeMap =
126             ((SourcePathData)sourceMap.get(source)).incomingEdges;
127400        Edge incomingEdge = (Edge)incomingEdgeMap.get(target);
128         
129400        if (!cached)
130200            reset(source);
131         
132400        return incomingEdge;
133     }
134  
135     /**
136      * <p>Returns a <code>LinkedHashMap</code> which maps each vertex
137      * in the graph (including the <code>source</code> vertex)
138      * to the last edge on the shortest path from the
139      * <code>source</code> vertex.
140      * The map's iterator will return the elements in order of
141      * increasing distance from <code>source</code>.</p>
142      *
143      * @see DijkstraDistance#getDistanceMap(Vertex,int)
144      * @see DijkstraDistance#getDistance(Vertex,Vertex)
145      * @param source the vertex from which distances are measured
146      */
147     public Map getIncomingEdgeMap(Vertex source)
148     {
14940        return getIncomingEdgeMap(source, g.numVertices());
150     }
151  
152     /**
153      * Returns a <code>List</code> of the edges on the shortest path from
154      * <code>source</code> to <code>target</code>, in order of their
155      * occurrence on this path.
156      * If either vertex is not in the graph for which this instance
157      * was created, throws <code>IllegalArgumentException</code>.
158      */
159     public List getPath(Vertex source, Vertex target)
160     {
16120        if (source.getGraph() != g)
1620            throw new IllegalArgumentException("Specified source vertex " +
163                     source + " is not part of graph " + g);
164  
16520        if (target.getGraph() != g)
1660            throw new IllegalArgumentException("Specified target vertex " +
167                     target + " is not part of graph " + g);
168         
16920        LinkedList path = new LinkedList();
170  
171         // collect path data; must use internal method rather than
172         // calling getIncomingEdge() because getIncomingEdge() may
173         // wipe out results if results are not cached
17420        Set targets = new HashSet();
17520        targets.add(target);
17620        singleSourceShortestPath(source, targets, g.numVertices());
17720        Map incomingEdges =
178             ((SourcePathData)sourceMap.get(source)).incomingEdges;
179         
18020        if (incomingEdges.isEmpty() || incomingEdges.get(target) == null)
1818            return path;
18212        Vertex current = target;
18334        while (current != source)
184         {
18522            Edge incoming = (Edge)incomingEdges.get(current);
18622            path.addFirst(incoming);
18722            current = incoming.getOpposite(current);
188         }
18912        return path;
190     }
191  
192     
193     /**
194      * <p>Returns a <code>LinkedHashMap</code> which maps each of the closest
195      * <code>numDist</code> vertices to the <code>source</code> vertex
196      * in the graph (including the <code>source</code> vertex)
197      * to the incoming edge along the path from that vertex. Throws
198      * an <code>IllegalArgumentException</code> if <code>source</code>
199      * is not in this instance's graph, or if <code>numDests</code> is
200      * either less than 1 or greater than the number of vertices in the
201      * graph.
202      *
203      * @see #getIncomingEdgeMap(Vertex)
204      * @see #getPath(Vertex,Vertex)
205      * @param source the vertex from which distances are measured
206      * @param numDests the number of vertics for which to measure distances
207      */
208     public LinkedHashMap getIncomingEdgeMap(Vertex source, int numDests)
209     {
210444        if (source.getGraph() != g)
2112            throw new IllegalArgumentException("Specified source vertex " +
212                     source + " is not part of graph " + g);
213  
214442        if (numDests < 1 || numDests > g.numVertices())
2152            throw new IllegalArgumentException("numDests must be >= 1 " +
216             "and <= g.numVertices()");
217  
218440        singleSourceShortestPath(source, null, numDests);
219         
220440        LinkedHashMap incomingEdgeMap =
221             ((SourcePathData)sourceMap.get(source)).incomingEdges;
222         
223440        if (!cached)
224220            reset(source);
225         
226440        return incomingEdgeMap;
227     }
228      
229     
230     /**
231      * For a given source vertex, holds the estimated and final distances,
232      * tentative and final assignments of incoming edges on the shortest path from
233      * the source vertex, and a priority queue (ordered by estimaed distance)
234      * of the vertices for which distances are unknown.
235      *
236      * @author Joshua O'Madadhain
237      */
238     protected class SourcePathData extends SourceData
239     {
240         public Map tentativeIncomingEdges;
241         public LinkedHashMap incomingEdges;
242  
243         public SourcePathData(ArchetypeVertex source)
244         {
245             super(source);
246             incomingEdges = new LinkedHashMap();
247             tentativeIncomingEdges = new HashMap();
248         }
249         
250         public void update(ArchetypeVertex dest, ArchetypeEdge tentative_edge, double new_dist)
251         {
252             super.update(dest, tentative_edge, new_dist);
253             tentativeIncomingEdges.put(dest, tentative_edge);
254         }
255         
256         public Pair getNextVertex()
257         {
258             Pair p = super.getNextVertex();
259             ArchetypeVertex v = (ArchetypeVertex)p.getFirst();
260             Edge incoming = (Edge)tentativeIncomingEdges.remove(v);
261             incomingEdges.put(v, incoming);
262             return p;
263         }
264         
265         public void createRecord(ArchetypeVertex w, ArchetypeEdge e, double new_dist)
266         {
267             super.createRecord(w, e, new_dist);
268             tentativeIncomingEdges.put(w, e);
269         }
270        
271     }
272  
273 }

this report was generated by version 1.0.5 of jcoverage.
visit www.jcoverage.com for updates.

copyright © 2003, jcoverage ltd. all rights reserved.
Java is a trademark of Sun Microsystems, Inc. in the United States and other countries.