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

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.Iterator;
14 import java.util.Map;
15  
16 import edu.uci.ics.jung.algorithms.connectivity.BFSDistanceLabeler;
17 import edu.uci.ics.jung.graph.ArchetypeVertex;
18 import edu.uci.ics.jung.graph.Edge;
19 import edu.uci.ics.jung.graph.Graph;
20 import edu.uci.ics.jung.graph.Vertex;
21 import edu.uci.ics.jung.utils.UserDataUtils;
22  
23 /**
24  * Computes the shortest path distances for graphs whose edges are not weighted (using BFS).
25  *
26  * @author Scott White
27  */
28 public class UnweightedShortestPath implements ShortestPath, Distance
29 {
30     private Map mDistanceMap;
31     private Map mIncomingEdgeMap;
32     private Graph mGraph;
33  
34     /**
35      * Constructs and initializes algorithm
36      * @param g the graph
37      */
38     public UnweightedShortestPath(Graph g)
395    {
405        mDistanceMap = new HashMap(g.numVertices() * 2);
415        mIncomingEdgeMap = new HashMap(g.numVertices() * 2);
425        mGraph = g;
435    }
44  
45     /**
46      * @see edu.uci.ics.jung.algorithms.shortestpath.Distance#getDistance(edu.uci.ics.jung.graph.ArchetypeVertex, edu.uci.ics.jung.graph.ArchetypeVertex)
47      */
48     public Number getDistance(ArchetypeVertex source, ArchetypeVertex target)
49     {
5072        Map sourceSPMap = getDistanceMap(source);
5172        return (Number) sourceSPMap.get(target);
52     }
53  
54     /**
55      * @see edu.uci.ics.jung.algorithms.shortestpath.Distance#getDistanceMap(edu.uci.ics.jung.graph.ArchetypeVertex)
56      */
57     public Map getDistanceMap(ArchetypeVertex source)
58     {
5974        Map sourceSPMap = (Map) mDistanceMap.get(source);
6074        if (sourceSPMap == null)
61         {
6220            computeShortestPathsFromSource(source);
6320            sourceSPMap = (Map) mDistanceMap.get(source);
64         }
6574        return sourceSPMap;
66     }
67  
68     /**
69      * @see edu.uci.ics.jung.algorithms.shortestpath.ShortestPath#getIncomingEdgeMap(edu.uci.ics.jung.graph.Vertex)
70      */
71     public Map getIncomingEdgeMap(Vertex source)
72     {
734        Map sourceIEMap = (Map) mIncomingEdgeMap.get(source);
744        if (sourceIEMap == null)
75         {
760            computeShortestPathsFromSource(source);
770            sourceIEMap = (Map) mIncomingEdgeMap.get(source);
78         }
794        return sourceIEMap;
80     }
81  
82     /**
83     * Computes the shortest path distance from the source to target. If the shortest path distance has not already
84     * been computed, then all pairs shortest paths will be computed.
85     * @param source the source node
86     * @param target the target node
87     * @return the shortest path value (if the target is unreachable, NPE is thrown)
88     * @deprecated use getDistance
89     */
90     public int getShortestPath(Vertex source, Vertex target)
91     {
920        return getDistance(source, target).intValue();
93     }
94  
95     /**
96      * Computes the shortest path distances from a given node to all other nodes.
97      * @param graph the graph
98      * @param source the source node
99      * @return A <code>Map</code> whose keys are target vertices and whose values are <code>Integers</code> representing the shortest path distance
100      */
101     private void computeShortestPathsFromSource(ArchetypeVertex source)
102     {
10320        String DISTANCE_KEY = "UnweightedShortestPath.DISTANCE";
10420        BFSDistanceLabeler labeler = new BFSDistanceLabeler(DISTANCE_KEY);
10520        labeler.labelDistances(mGraph, (Vertex)source);
10620        Map currentSourceSPMap = new HashMap();
10720        Map currentSourceEdgeMap = new HashMap();
108  
10920        for (Iterator vIt = mGraph.getVertices().iterator(); vIt.hasNext();)
110         {
111118            Vertex vertex = (Vertex) vIt.next();
112118            Number distanceVal = (Number) vertex.getUserDatum(DISTANCE_KEY);
113             // BFSDistanceLabeler uses -1 to indicate unreachable vertices;
114             // don't bother to store unreachable vertices
115118            if (distanceVal != null && distanceVal.intValue() >= 0)
116             {
11798                currentSourceSPMap.put(vertex, distanceVal);
11898                int minDistance = distanceVal.intValue();
11998                for (Iterator eIt = vertex.getInEdges().iterator(); eIt.hasNext();)
120                 {
121234                    Edge incomingEdge = (Edge) eIt.next();
122234                    Vertex neighbor = incomingEdge.getOpposite(vertex);
123234                    Number predDistanceVal =
124                         (Number) neighbor.getUserDatum(DISTANCE_KEY);
125234                    int pred_distance = predDistanceVal.intValue();
126 // if (predDistanceVal.intValue() < minDistance)
127234                    if (pred_distance < minDistance && pred_distance >= 0)
128                     {
12978                        minDistance = predDistanceVal.intValue();
13078                        currentSourceEdgeMap.put(vertex, incomingEdge);
131                     }
132                 }
133             }
134         }
135  
13620        UserDataUtils.cleanup(mGraph.getVertices(), DISTANCE_KEY);
137  
13820        mDistanceMap.put(source, currentSourceSPMap);
13920        mIncomingEdgeMap.put(source, currentSourceEdgeMap);
14020    }
141     
142     /**
143      * Clears all stored distances for this instance.
144      * Should be called whenever the graph is modified (edge weights
145      * changed or edges added/removed). If the user knows that
146      * some currently calculated distances are unaffected by a
147      * change, <code>reset(Vertex)</code> may be appropriate instead.
148      *
149      * @see #reset(Vertex)
150      */
151     public void reset()
152     {
1530        mDistanceMap = new HashMap(mGraph.numVertices() * 2);
1540        mIncomingEdgeMap = new HashMap(mGraph.numVertices() * 2);
1550    }
156     
157     /**
158      * Clears all stored distances for the specified source vertex
159      * <code>source</code>. Should be called whenever the stored distances
160      * from this vertex are invalidated by changes to the graph.
161      *
162      * @see #reset()
163      */
164     public void reset(Vertex v)
165     {
1660        mDistanceMap.put(v, null);
1670        mIncomingEdgeMap.put(v, null);
1680    }
169 }

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.