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. |