Clover coverage report - Convert - proto0
Coverage timestamp: Fr Nov 26 2004 21:48:14 CET
Overview   Package   File
    FRAMES   NO FRAMES  
file stats: LOC: 305   Methods: 16
NCLOC: 118   Classes: 1
 
 Source file Conditionals Statements Methods TOTAL
ShortestPathEngine.java 85% 92,7% 93,8% 91,2%
coverage coverage
 1    /*
 2    * Copyright 2004 Ronald Blaschke.
 3    *
 4    * Licensed under the Apache License, Version 2.0 (the "License");
 5    * you may not use this file except in compliance with the License.
 6    * You may obtain a copy of the License at
 7    *
 8    * http://www.apache.org/licenses/LICENSE-2.0
 9    *
 10    * Unless required by applicable law or agreed to in writing, software
 11    * distributed under the License is distributed on an "AS IS" BASIS,
 12    * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 13    * See the License for the specific language governing permissions and
 14    * limitations under the License.
 15    */
 16    package org.rblasch.convert.dijkstra;
 17   
 18    import org.rblasch.convert.graph.Connection;
 19    import org.rblasch.convert.graph.Edge;
 20    import org.rblasch.convert.graph.ListPath;
 21    import org.rblasch.convert.graph.Path;
 22    import org.rblasch.convert.graph.Vertex;
 23    import org.rblasch.convert.graph.WeightedDirectedGraph;
 24    import org.rblasch.convert.graph.WeightedEdge;
 25   
 26    import java.util.Collections;
 27    import java.util.Comparator;
 28    import java.util.HashMap;
 29    import java.util.HashSet;
 30    import java.util.Iterator;
 31    import java.util.LinkedList;
 32    import java.util.List;
 33    import java.util.Map;
 34    import java.util.Set;
 35   
 36    /**
 37    * An implementation of Dijkstra's shortest path algorithm. It computes the shortest path (in distance)
 38    * to all cities in the map. The output of the algorithm is the shortest distance from the start vertex
 39    * to every other vertex, and the shortest path from the start vertex to every other.
 40    * <p/>
 41    * Upon calling
 42    * {@link #execute(Vertex, Vertex)},
 43    * the results of the algorithm are made available by calling
 44    * {@link #getPredecessor(Vertex)}
 45    * and
 46    * {@link #getShortestDistance(Vertex)}.
 47    * <p/>
 48    * To get the shortest path between the vertex <var>destination</var> and
 49    * the source vertex after running the algorithm, one would do:
 50    * <pre>
 51    * List l = new ArrayList();
 52    * <p/>
 53    * for (Object vertex = destination; vertex != null; vertex = engine.getPredecessor(vertex))
 54    * {
 55    * l.add(vertex);
 56    * }
 57    * <p/>
 58    * Collections.reverse(l);
 59    * <p/>
 60    * return l;
 61    * </pre>
 62    *
 63    * @author Renaud Waldura &lt;renaud+tw@waldura.com&gt;
 64    * @version $Id: DijkstraEngine.java,v 1.4 2003/03/03 01:26:22 renaud Exp $
 65    * @see #execute(Vertex, Vertex)
 66    */
 67    public class ShortestPathEngine {
 68    /**
 69    * Infinity value for distances.
 70    */
 71    public static final int INFINITE_DISTANCE = Integer.MAX_VALUE;
 72   
 73    /**
 74    * This comparator orders cities according to their shortest distances,
 75    * in ascending fashion. If two cities have the same shortest distance,
 76    * we compare the cities themselves.
 77    */
 78    private final Comparator shortestDistanceComparator = new Comparator() {
 79  13701 public int compare(final Object left, final Object right) {
 80    // note that this trick doesn't work for huge distances, close to Integer.MAX_VALUE
 81  13701 return getShortestDistance((Vertex) left) - getShortestDistance((Vertex) right);
 82    }
 83    };
 84   
 85    /**
 86    * The graph.
 87    */
 88    private final WeightedDirectedGraph graph;
 89   
 90    /**
 91    * The working set of cities, kept ordered by shortest distance.
 92    */
 93    private final Set /* of Vertex */ unsettledNodes = new HashSet();
 94   
 95    /**
 96    * The set of cities for which the shortest distance to the source
 97    * has been found.
 98    */
 99    private final Set /* of Vertex */ settledNodes = new HashSet();
 100   
 101    /**
 102    * The currently known shortest distance for all vertices.
 103    */
 104    private final Map /* of Vertex -> Integer */ shortestDistances = new HashMap();
 105   
 106    /**
 107    * Predecessors list: maps a vertex to its predecessor in the spanning tree of
 108    * shortest paths.
 109    */
 110    private final Map /* of Vertex -> Vertex */ predecessors = new HashMap();
 111   
 112    /**
 113    * Constructor.
 114    */
 115  655 public ShortestPathEngine(final WeightedDirectedGraph map) {
 116  655 this.graph = map;
 117    }
 118   
 119    /**
 120    * Initialize all data structures used by the algorithm.
 121    *
 122    * @param start the source node
 123    */
 124  655 private void init(final Vertex start) {
 125  655 settledNodes.clear();
 126  655 unsettledNodes.clear();
 127   
 128  655 shortestDistances.clear();
 129  655 predecessors.clear();
 130   
 131    // add source
 132  655 setShortestDistance(start, 0);
 133  655 unsettledNodes.add(start);
 134    }
 135   
 136    /**
 137    * Run Dijkstra's shortest path algorithm on the map.
 138    * The results of the algorithm are available through
 139    * {@link #getPredecessor(Vertex)}
 140    * and
 141    * {@link #getShortestDistance(Vertex)}
 142    * upon completion of this method.
 143    *
 144    * @param start the starting vertex
 145    * @param destination the destination vertex. If this argument is <code>null</code>, the algorithm is
 146    * run on the entire graph, instead of being stopped as soon as the destination is reached.
 147    */
 148  655 public void execute(final Vertex start, final Vertex destination) {
 149  655 init(start);
 150   
 151    // the current node
 152  655 Vertex u;
 153   
 154    // extract the node with the shortest distance
 155  ? while ((u = extractMin()) != null) {
 156    //assert !isSettled(u);
 157   
 158    // destination reached, stop
 159  0 if (u == destination) break;
 160   
 161  5770 markSettled(u);
 162   
 163  5770 relaxNeighbors(u);
 164    }
 165    }
 166   
 167  655 public Path getShortestPath(final Vertex start, final Vertex end) {
 168  655 execute(start, end);
 169   
 170  655 final List /* of Vertex, Edge */ path = new LinkedList();
 171  655 if (getShortestDistance(end) == ShortestPathEngine.INFINITE_DISTANCE) {
 172  55 return null;
 173    }
 174  600 Vertex nextVertex = end;
 175  600 path.add(nextVertex);
 176  600 while (nextVertex != null) {
 177  1690 final Vertex vertex = getPredecessor(nextVertex);
 178  1690 if (vertex != null) {
 179  1090 path.add(getMinWeightEdge(vertex, nextVertex));
 180  1090 path.add(vertex);
 181    }
 182  1690 nextVertex = vertex;
 183    }
 184   
 185  600 Collections.reverse(path);
 186   
 187  600 return new ListPath(path);
 188    }
 189   
 190  12294 private Edge getMinWeightEdge(final Vertex start, final Vertex end) {
 191  12294 return ((WeightedEdge) ((Connection) Collections.min(graph.getConnections(start, end), new Comparator() {
 192  0 public int compare(final Object o1, final Object o2) {
 193  0 final Connection c1 = (Connection) o1;
 194  0 final Connection c2 = (Connection) o2;
 195   
 196  0 return new Integer(((WeightedEdge) c1.getEdge()).getWeight()).compareTo(new Integer(((WeightedEdge) c2.getEdge()).getWeight()));
 197    }
 198    })).getEdge());
 199    }
 200   
 201    /**
 202    * Get the value of a segment.
 203    */
 204  11204 public int getMinWeight(final Vertex start, final Vertex end) {
 205  11204 return ((WeightedEdge) getMinWeightEdge(start, end)).getWeight();
 206    }
 207   
 208    /**
 209    * Extract the vertex with the currently shortest distance, and remove it from
 210    * the priority queue.
 211    *
 212    * @return the minimum vertex, or <code>null</code> if the queue is empty.
 213    */
 214  6425 private Vertex extractMin() {
 215  655 if (unsettledNodes.isEmpty()) return null;
 216   
 217  5770 final Object min = Collections.min(unsettledNodes, shortestDistanceComparator);
 218  5770 unsettledNodes.remove(min);
 219   
 220  5770 return (Vertex) min;
 221    }
 222   
 223    /**
 224    * Compute new shortest distance for neighboring nodes and update if a better
 225    * distance is found.
 226    *
 227    * @param u the node
 228    */
 229  5770 private void relaxNeighbors(final Vertex u) {
 230  5770 for (Iterator i = graph.getOutbound(u).iterator(); i.hasNext();) {
 231  12590 final Vertex v = (Vertex) i.next();
 232   
 233    // skip node already settled
 234  6501 if (isSettled(v)) continue;
 235   
 236  6089 if (getShortestDistance(v) > getShortestDistance(u) + getMinWeight(u, v)) {
 237    // assign new shortest distance and mark unsettled
 238  5115 setShortestDistance(v, getShortestDistance(u) + getMinWeight(u, v));
 239   
 240    // assign predecessor in shortest path
 241  5115 setPredecessor(v, u);
 242    }
 243    }
 244    }
 245   
 246    /**
 247    * Mark a node as settled.
 248    *
 249    * @param u the node
 250    */
 251  5770 private void markSettled(final Vertex u) {
 252  5770 settledNodes.add(u);
 253    }
 254   
 255    /**
 256    * Test a node.
 257    *
 258    * @param v the node to consider
 259    * @return whether the node is settled, ie. its shortest distance
 260    * has been found.
 261    */
 262  12590 private boolean isSettled(final Vertex v) {
 263  12590 return settledNodes.contains(v);
 264    }
 265   
 266    /**
 267    * @return the shortest distance from the source to the given vertex, or
 268    * {@link ShortestPathEngine#INFINITE_DISTANCE} if there is no route to the destination.
 269    */
 270  45350 public int getShortestDistance(final Vertex vertex) {
 271  45350 final Number d = (Number) shortestDistances.get(vertex);
 272  45350 return (d == null) ? INFINITE_DISTANCE : d.intValue();
 273    }
 274   
 275    /**
 276    * Set the new shortest distance for the given node,
 277    * and re-balance the set according to new shortest distances.
 278    *
 279    * @param vertex the node to set
 280    * @param distance new shortest distance value
 281    */
 282  5770 private void setShortestDistance(final Vertex vertex, final int distance) {
 283    // this crucial step ensure no duplicates will be created in the queue
 284    // when an existing unsettled node is updated with a new shortest distance
 285  5770 unsettledNodes.remove(vertex);
 286   
 287  5770 shortestDistances.put(vertex, new Integer(distance));
 288   
 289    // re-balance the sorted set according to the new shortest distance found
 290    // (see the comparator the set was initialized with)
 291  5770 unsettledNodes.add(vertex);
 292    }
 293   
 294    /**
 295    * @return the vertex leading to the given vertex on the shortest path, or
 296    * <code>null</code> if there is no route to the destination.
 297    */
 298  1690 public Vertex getPredecessor(final Vertex vertex) {
 299  1690 return (Vertex) predecessors.get(vertex);
 300    }
 301   
 302  5115 private void setPredecessor(final Vertex a, final Vertex b) {
 303  5115 predecessors.put(a, b);
 304    }
 305    }
 
CloverReport generated by Clover v1.3_01
Fr Nov 26 2004 21:48:14 CET.		   30 day Evaluation Version distributed via the Maven Jar Repository. Clover is not free. You have 30 days to evaluate it. After this, please visit http://www.cenqua.com to obtain a licensed version of Clover