|
1
25 package classycle.graph;
26
27 import java.util.ArrayList  ;
28 import java.util.HashMap ;
29 import java.util.Vector ;
30
31
37 public class StrongComponent extends Vertex {
38 private static class GeometryAttributes implements GraphAttributes {
39 private int _girth;
40 private int _radius;
41 private int _diameter;
42 private ArrayList _centerVertices = new ArrayList ();
43 private int[] _eccentricities;
44 private int[] _maximumFragmentSizes;
45 private int _bestFragmentSize;
46 private ArrayList _bestFragmenters = new ArrayList ();
47
48 public GeometryAttributes() {}
49
50 public int getGirth() {
51 return _girth;
52 }
53
54 void setGirth(int girth) {
55 _girth = girth;
56 }
57
58 public int getRadius() {
59 return _radius;
60 }
61
62 public int getDiameter() {
63 return _diameter;
64 }
65
66 public int getBestFragmentSize() {
67 return _bestFragmentSize;
68 }
69
70 public Vertex[] getCenterVertices() {
71 return (Vertex[]) _centerVertices.toArray(
72 new Vertex[_centerVertices.size()]);
73 }
74
75 void addVertex(Vertex vertex) {
76 _centerVertices.add(vertex);
77 }
78
79 public Vertex[] getBestFragmenters() {
80 return (Vertex[]) _bestFragmenters.toArray(
81 new Vertex[_bestFragmenters.size()]);
82 }
83
84 void addFragmenter(Vertex vertex) {
85 _bestFragmenters.add(vertex);
86 }
87
88 public int[] getEccentricities() {
89 return _eccentricities;
90 }
91
92 void setEccentricities(int[] eccentricities) {
93 _eccentricities = eccentricities;
94
95 _radius = Integer.MAX_VALUE;
97 _diameter = 0;
98 for (int i = 0; i < eccentricities.length; i++) {
99 _radius = Math.min(_radius, eccentricities[i]);
100 _diameter = Math.max(_diameter, eccentricities[i]);
101 }
102 }
103
104 public int[] getMaximumFragmentSizes() {
105 return _maximumFragmentSizes;
106 }
107
108 void setMaximumFragmentSizes(int[] maximumFragmentSizes) {
109 _maximumFragmentSizes = maximumFragmentSizes;
110
111 _bestFragmentSize = Integer.MAX_VALUE;
112 for (int i = 0; i < maximumFragmentSizes.length; i++) {
113 _bestFragmentSize = Math.min(_bestFragmentSize,
114 maximumFragmentSizes[i]);
115 }
116 }
117
118 public int compareTo(Object object)
119 {
120 int result = 1;
121 if (object instanceof GeometryAttributes && _bestFragmenters.size() > 0)
122 {
123 ArrayList list = ((GeometryAttributes) object)._bestFragmenters;
124 if (list.size() > 0)
125 {
126 Attributes attributes
127 = ((Vertex) _bestFragmenters.get(0)).getAttributes();
128 Attributes objectAttributes = ((Vertex) list.get(0)).getAttributes();
129 result = attributes.compareTo(objectAttributes);
130 }
131 }
132 return result;
133 }
134
135 }
136
137 private final Vector _vertices = new Vector ();
138 private boolean _active;
139 private int _longestWalk;
140
141
145 public StrongComponent() {
146 super(new GeometryAttributes());
147 }
148
149
150 public int getNumberOfVertices() {
151 return _vertices.size();
152 }
153
154
155 public AtomicVertex getVertex(int index) {
156 return (AtomicVertex) _vertices.elementAt(index);
157 }
158
159
163 public void addVertex(AtomicVertex vertex) {
164 _vertices.insertElementAt(vertex, 0);
165 }
166
167
172 public void calculateAttributes() {
173 HashMap indexMap = calculateIndexMap();
174 int[][] distances = calculateDistances(indexMap);
175
176 GeometryAttributes attributes = (GeometryAttributes) getAttributes();
178 int girth = Integer.MAX_VALUE;
179 int[] eccentricities = new int[distances.length];
180 for (int i = 0; i < distances.length; i++) {
181 girth = Math.min(girth, distances[i][i]);
182 eccentricities[i] = 0;
183 for (int j = 0; j < distances.length; j++) {
184 if (i != j) {
185 eccentricities[i] = Math.max(eccentricities[i], distances[i][j]);
186 }
187 }
188 }
189 attributes.setEccentricities(eccentricities);
190 attributes.setGirth(girth);
191 attributes.setMaximumFragmentSizes(
192 calculateMaximumFragmentSizes(indexMap));
193
194 for (int i = 0, r = attributes.getRadius(),
196 s = attributes.getBestFragmentSize(); i < distances.length; i++) {
197 if (eccentricities[i] == r) {
198 attributes.addVertex(getVertex(i));
199 }
200 if (attributes.getMaximumFragmentSizes()[i] == s) {
201 attributes.addFragmenter(getVertex(i));
202 }
203 }
204
205 }
206
207 private int[][] calculateDistances(HashMap indexMap) {
208 int n = getNumberOfVertices();
210 int[][] distances = new int[n][n];
211 for (int i = 0; i < n; i++) {
212 int[] row = distances[i];
213 AtomicVertex vertex = getVertex(i);
214 for (int j = 0; j < n; j++) {
215 row[j] = Integer.MAX_VALUE / 2;
216 }
217 for (int j = 0, m = vertex.getNumberOfOutgoingArcs(); j < m; j++) {
218 Integer index = (Integer ) indexMap.get(vertex.getHeadVertex(j));
219 if (index != null) {
220 row[index.intValue()] = 1;
221 }
222 }
223 }
224
225 for (int k = 0; k < n; k++) {
227 for (int i = 0; i < n; i++) {
228 for (int j = 0; j < n; j++) {
229 if (distances[i][k] + distances[k][j] < distances[i][j]) {
230 distances[i][j] = distances[i][k] + distances[k][j];
231 }
232 }
233 }
234 }
235
236 return distances;
237 }
238
239 private HashMap calculateIndexMap() {
240 HashMap result = new HashMap ();
241 for (int i = 0, n = getNumberOfVertices(); i < n; i++) {
242 result.put(getVertex(i), new Integer (i));
243 }
244 return result;
245 }
246
247 private int[] calculateMaximumFragmentSizes(HashMap indexMap) {
248 AtomicVertex[] graph = new AtomicVertex[getNumberOfVertices()];
250 for (int i = 0; i < graph.length; i++) {
251 graph[i] = new AtomicVertex(null);
252 }
253 for (int i = 0; i < graph.length; i++) {
254 AtomicVertex vertex = getVertex(i);
255 for (int j = 0, n = vertex.getNumberOfOutgoingArcs(); j < n; j++) {
256 Integer index = (Integer ) indexMap.get(vertex.getHeadVertex(j));
257 if (index != null) {
258 graph[i].addOutgoingArcTo(graph[index.intValue()]);
259 }
260 }
261 }
262
263 StrongComponentProcessor processor = new StrongComponentProcessor(false);
264 int[] maximumFragmentSizes = new int[getNumberOfVertices()];
265 for (int i = 0; i < maximumFragmentSizes.length; i++) {
266 graph[i].setDefaultValueOfGraphVertexFlag(false);
267 processor.deepSearchFirst(graph);
268 StrongComponent[] fragments = processor.getStrongComponents();
269 maximumFragmentSizes[i] = 0;
270 for (int j = 0; j < fragments.length; j++) {
271 maximumFragmentSizes[i] = Math.max(maximumFragmentSizes[i],
272 fragments[j].getNumberOfVertices());
273 }
274 graph[i].setDefaultValueOfGraphVertexFlag(true);
275 }
276 return maximumFragmentSizes;
277 }
278
279
283 public void reset() {
284 super.reset();
285 _active = false;
286 _longestWalk = -1;
287 }
288
289 public boolean isActive() {
290 return _active;
291 }
292
293 public void setActive(boolean active) {
294 _active = active;
295 }
296
297 public int getLongestWalk() {
298 return _longestWalk;
299 }
300
301 public void setLongestWalk(int longestWalk) {
302 _longestWalk = longestWalk;
303 }
304
305 public String toString() {
306 StringBuffer result = new StringBuffer ("Strong component with ");
307 int n = getNumberOfVertices();
308 result.append(n).append(n > 1 ? " vertices." : " vertex.");
309 result.append(" Longest walk: ").append(getLongestWalk());
310 for (int i = 0; i < n; i++) {
311 result.append("\n ").append(getVertex(i));
312 }
313 return new String (result);
314 }
315 } |
Popular Tags |
Java API By Example, From Geeks To Geeks.