Coverage details for edu.uci.ics.jung.algorithms.connectivity.BFSDistanceLabeler

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.connectivity;
11  
12 import edu.uci.ics.jung.graph.Vertex;
13 import edu.uci.ics.jung.graph.Graph;
14 import edu.uci.ics.jung.graph.decorators.NumericDecorator;
15 import edu.uci.ics.jung.utils.UserData;
16  
17 import java.util.*;
18  
19 /**
20  * Labels each node in the graph according to the BFS distance from the start node(s). If nodes are unreachable, then
21  * they are assigned a distance of -1.
22  * All nodes traversed at step k are marked as predecessors of their successors traversed at step k+1.
23  * <p>
24  * Running time is: O(m)
25  * @author Scott White
26  */
27 public class BFSDistanceLabeler {
28     public static final String DEFAULT_DISTANCE_KEY = "algorithms.connectivity.BFSDiststanceLabeler.DISTANCE_KEY";
29     private NumericDecorator mDistanceDecorator;
30     private List mCurrentList;
31     private Set mUnvisitedVertices;
32     private List mVerticesInOrderVisited;
33     private Map mPredecessorMap;
34  
35  
36     /**
37      * Creates a new BFS labeler for the specified graph and root set.
38      * @param distanceKey the UserDatum key the algorithm should use to store/decorate the distances from the root set
39      * The distances are stored in the corresponding Vertex objects and are of type MutableInteger
40      */
4123    public BFSDistanceLabeler(String distanceKey) {
4223        mDistanceDecorator = new NumericDecorator(distanceKey,UserData.SHARED);
4323        mPredecessorMap = new HashMap();
4423    }
45     
46     /**
47      * Creates a new BFS labeler for the specified graph and root set
48      * The distances are stored in the corresponding Vertex objects and are of type MutableInteger
49      */
500    public BFSDistanceLabeler() {
510        mDistanceDecorator = new NumericDecorator(DEFAULT_DISTANCE_KEY,UserData.SHARED);
520        mPredecessorMap = new HashMap();
530    }
54  
55     /**
56      * Returns the list of vertices visited in order of traversal
57      * @return the list of vertices
58      */
59     public List getVerticesInOrderVisited() {
602        return mVerticesInOrderVisited;
61     }
62  
63     /**
64      * Returns the set of all vertices that were not visited
65      * @return the list of unvisited vertices
66      */
67     public Set getUnivistedVertices() {
682        return mUnvisitedVertices;
69     }
70  
71     /**
72      * Given a vertex, returns the shortest distance from any node in the root set to v
73      * @param v the vertex whose distance is to be retrieved
74      * @return the shortest distance from any node in the root set to v
75      */
76     public int getDistance(Graph g, Vertex v) {
776        if (!g.getVertices().contains(v)) {
780            throw new IllegalArgumentException("Vertex is not contained in the graph.");
79         }
80  
816        return mDistanceDecorator.getValue(v).intValue();
82     }
83  
84     /**
85      * Returns set of predecessors of the given vertex
86      * @param v the vertex whose predecessors are to be retrieved
87      * @return the set of predecessors
88      */
89     public Set getPredecessors(Vertex v) {
906        return (Set) mPredecessorMap.get(v);
91     }
92  
93     protected void initialize(Graph g, Set rootSet) {
9423        mVerticesInOrderVisited = new ArrayList();
9523        mUnvisitedVertices = new HashSet();
9623        for (Iterator vIt=g.getVertices().iterator(); vIt.hasNext();) {
97138            Vertex currentVertex = (Vertex) vIt.next();
98138            mUnvisitedVertices.add(currentVertex);
99138            mPredecessorMap.put(currentVertex,new HashSet());
100         }
101  
10223        mCurrentList = new ArrayList();
10323        for (Iterator rootIt = rootSet.iterator(); rootIt.hasNext();) {
10424            Vertex v = (Vertex) rootIt.next();
10524            mDistanceDecorator.setValue(new Integer(0),v);
10624            mCurrentList.add(v);
10724            mUnvisitedVertices.remove(v);
10824            mVerticesInOrderVisited.add(v);
109         }
11023    }
111  
112     private void addPredecessor(Vertex predecessor,Vertex sucessor) {
11398        HashSet predecessors = (HashSet) mPredecessorMap.get(sucessor);
11498        predecessors.add(predecessor);
11598    }
116  
117     public void removeDecorations(Graph g) {
1182        for (Iterator vIt=g.getVertices().iterator();vIt.hasNext();) {
11914            Vertex v = (Vertex) vIt.next();
12014            mDistanceDecorator.removeValue(v);
121         }
1222    }
123  
124     /**
125      * Computes the distances of all the node from the starting root nodes. If there is more than one root node
126      * the minimum distance from each root node is used as the designated distance to a given node. Also keeps track
127      * of the predecessors of each node traversed as well as the order of nodes traversed.
128      * @param graph the graph to label
129      * @param rootSet the set of starting vertices to traverse from
130      */
131     public void labelDistances(Graph graph, Set rootSet) {
132  
13323        initialize(graph,rootSet);
134  
13523        int distance = 1;
136         while (true) {
13762            List newList = new ArrayList();
138  
13962           for (Iterator vIt = mCurrentList.iterator(); vIt.hasNext();) {
140112                Vertex currentVertex = (Vertex) vIt.next();
141112                for (Iterator uIt = currentVertex.getSuccessors().iterator(); uIt.hasNext();) {
142250                    visitNewVertex(currentVertex,(Vertex) uIt.next(), distance, newList);
143                 }
144             }
14562            if (newList.size() == 0) break;
14639            mCurrentList = newList;
14739            distance++;
148         }
149  
15023        for (Iterator vIt = mUnvisitedVertices.iterator(); vIt.hasNext();) {
15126            Vertex v = (Vertex) vIt.next();
15226            mDistanceDecorator.setValue(new Integer(-1),v);
153  
154         }
15523    }
156  
157     /**
158      * Computes the distances of all the node from the specified root node. Also keeps track
159      * of the predecessors of each node traveresed as well as the order of nodes traversed.
160      * @param graph the graph to label
161      * @param root the single starting vertex to traverse from
162      */
163     public void labelDistances(Graph graph, Vertex root) {
16421        Set rootSet = new HashSet();
16521        rootSet.add(root);
16621        labelDistances(graph,rootSet);
167  
16821    }
169  
170     private void visitNewVertex(Vertex predecessor,Vertex neighbor, int distance, List newList) {
171250        if (mUnvisitedVertices.contains(neighbor)) {
17288            mDistanceDecorator.setValue(new Integer(distance),neighbor);
17388            newList.add(neighbor);
17488            mVerticesInOrderVisited.add(neighbor);
17588            mUnvisitedVertices.remove(neighbor);
176         }
177250        int predecessorDistance = mDistanceDecorator.getValue(predecessor).intValue();
178250        int successorDistance = mDistanceDecorator.getValue(neighbor).intValue();
179250        if (predecessorDistance < successorDistance) {
18098            addPredecessor(predecessor,neighbor);
181         }
182250    }
183 }

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.