| Line | Hits | Source |
|---|---|---|
| 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 | */ | |
| 41 | 23 | public BFSDistanceLabeler(String distanceKey) { |
| 42 | 23 | mDistanceDecorator = new NumericDecorator(distanceKey,UserData.SHARED); |
| 43 | 23 | mPredecessorMap = new HashMap(); |
| 44 | 23 | } |
| 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 | */ | |
| 50 | 0 | public BFSDistanceLabeler() { |
| 51 | 0 | mDistanceDecorator = new NumericDecorator(DEFAULT_DISTANCE_KEY,UserData.SHARED); |
| 52 | 0 | mPredecessorMap = new HashMap(); |
| 53 | 0 | } |
| 54 | ||
| 55 | /** | |
| 56 | * Returns the list of vertices visited in order of traversal | |
| 57 | * @return the list of vertices | |
| 58 | */ | |
| 59 | public List getVerticesInOrderVisited() { | |
| 60 | 2 | 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() { | |
| 68 | 2 | 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) { | |
| 77 | 6 | if (!g.getVertices().contains(v)) { |
| 78 | 0 | throw new IllegalArgumentException("Vertex is not contained in the graph."); |
| 79 | } | |
| 80 | ||
| 81 | 6 | 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) { | |
| 90 | 6 | return (Set) mPredecessorMap.get(v); |
| 91 | } | |
| 92 | ||
| 93 | protected void initialize(Graph g, Set rootSet) { | |
| 94 | 23 | mVerticesInOrderVisited = new ArrayList(); |
| 95 | 23 | mUnvisitedVertices = new HashSet(); |
| 96 | 23 | for (Iterator vIt=g.getVertices().iterator(); vIt.hasNext();) { |
| 97 | 138 | Vertex currentVertex = (Vertex) vIt.next(); |
| 98 | 138 | mUnvisitedVertices.add(currentVertex); |
| 99 | 138 | mPredecessorMap.put(currentVertex,new HashSet()); |
| 100 | } | |
| 101 | ||
| 102 | 23 | mCurrentList = new ArrayList(); |
| 103 | 23 | for (Iterator rootIt = rootSet.iterator(); rootIt.hasNext();) { |
| 104 | 24 | Vertex v = (Vertex) rootIt.next(); |
| 105 | 24 | mDistanceDecorator.setValue(new Integer(0),v); |
| 106 | 24 | mCurrentList.add(v); |
| 107 | 24 | mUnvisitedVertices.remove(v); |
| 108 | 24 | mVerticesInOrderVisited.add(v); |
| 109 | } | |
| 110 | 23 | } |
| 111 | ||
| 112 | private void addPredecessor(Vertex predecessor,Vertex sucessor) { | |
| 113 | 98 | HashSet predecessors = (HashSet) mPredecessorMap.get(sucessor); |
| 114 | 98 | predecessors.add(predecessor); |
| 115 | 98 | } |
| 116 | ||
| 117 | public void removeDecorations(Graph g) { | |
| 118 | 2 | for (Iterator vIt=g.getVertices().iterator();vIt.hasNext();) { |
| 119 | 14 | Vertex v = (Vertex) vIt.next(); |
| 120 | 14 | mDistanceDecorator.removeValue(v); |
| 121 | } | |
| 122 | 2 | } |
| 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 | ||
| 133 | 23 | initialize(graph,rootSet); |
| 134 | ||
| 135 | 23 | int distance = 1; |
| 136 | while (true) { | |
| 137 | 62 | List newList = new ArrayList(); |
| 138 | ||
| 139 | 62 | for (Iterator vIt = mCurrentList.iterator(); vIt.hasNext();) { |
| 140 | 112 | Vertex currentVertex = (Vertex) vIt.next(); |
| 141 | 112 | for (Iterator uIt = currentVertex.getSuccessors().iterator(); uIt.hasNext();) { |
| 142 | 250 | visitNewVertex(currentVertex,(Vertex) uIt.next(), distance, newList); |
| 143 | } | |
| 144 | } | |
| 145 | 62 | if (newList.size() == 0) break; |
| 146 | 39 | mCurrentList = newList; |
| 147 | 39 | distance++; |
| 148 | } | |
| 149 | ||
| 150 | 23 | for (Iterator vIt = mUnvisitedVertices.iterator(); vIt.hasNext();) { |
| 151 | 26 | Vertex v = (Vertex) vIt.next(); |
| 152 | 26 | mDistanceDecorator.setValue(new Integer(-1),v); |
| 153 | ||
| 154 | } | |
| 155 | 23 | } |
| 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) { | |
| 164 | 21 | Set rootSet = new HashSet(); |
| 165 | 21 | rootSet.add(root); |
| 166 | 21 | labelDistances(graph,rootSet); |
| 167 | ||
| 168 | 21 | } |
| 169 | ||
| 170 | private void visitNewVertex(Vertex predecessor,Vertex neighbor, int distance, List newList) { | |
| 171 | 250 | if (mUnvisitedVertices.contains(neighbor)) { |
| 172 | 88 | mDistanceDecorator.setValue(new Integer(distance),neighbor); |
| 173 | 88 | newList.add(neighbor); |
| 174 | 88 | mVerticesInOrderVisited.add(neighbor); |
| 175 | 88 | mUnvisitedVertices.remove(neighbor); |
| 176 | } | |
| 177 | 250 | int predecessorDistance = mDistanceDecorator.getValue(predecessor).intValue(); |
| 178 | 250 | int successorDistance = mDistanceDecorator.getValue(neighbor).intValue(); |
| 179 | 250 | if (predecessorDistance < successorDistance) { |
| 180 | 98 | addPredecessor(predecessor,neighbor); |
| 181 | } | |
| 182 | 250 | } |
| 183 | } |
|
this report was generated by version 1.0.5 of jcoverage. |
copyright © 2003, jcoverage ltd. all rights reserved. |