001: /*
002: * Copyright (c) 2003-2008, Franz-Josef Elmer, All rights reserved.
003: *
004: * Redistribution and use in source and binary forms, with or without
005: * modification, are permitted provided that the following conditions are met:
006: *
007: * - Redistributions of source code must retain the above copyright notice,
008: * this list of conditions and the following disclaimer.
009: * - Redistributions in binary form must reproduce the above copyright notice,
010: * this list of conditions and the following disclaimer in the documentation
011: * and/or other materials provided with the distribution.
012: *
013: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
014: * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
015: * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
016: * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
017: * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
018: * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
019: * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
020: * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
021: * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
022: * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
023: * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
024: */
025: package classycle.graph;
026:
027: import java.util.ArrayList;
028: import java.util.HashMap;
029: import java.util.Vector;
030:
031: /**
032: * A strong component is a subgraph of a directed graph where every two
033: * vertices are mutually reachable.
034: *
035: * @author Franz-Josef Elmer
036: */
037: public class StrongComponent extends Vertex {
038: private static class GeometryAttributes implements GraphAttributes {
039: private int _girth;
040: private int _radius;
041: private int _diameter;
042: private ArrayList _centerVertices = new ArrayList();
043: private int[] _eccentricities;
044: private int[] _maximumFragmentSizes;
045: private int _bestFragmentSize;
046: private ArrayList _bestFragmenters = new ArrayList();
047:
048: public GeometryAttributes() {
049: }
050:
051: public int getGirth() {
052: return _girth;
053: }
054:
055: void setGirth(int girth) {
056: _girth = girth;
057: }
058:
059: public int getRadius() {
060: return _radius;
061: }
062:
063: public int getDiameter() {
064: return _diameter;
065: }
066:
067: public int getBestFragmentSize() {
068: return _bestFragmentSize;
069: }
070:
071: public Vertex[] getCenterVertices() {
072: return (Vertex[]) _centerVertices
073: .toArray(new Vertex[_centerVertices.size()]);
074: }
075:
076: void addVertex(Vertex vertex) {
077: _centerVertices.add(vertex);
078: }
079:
080: public Vertex[] getBestFragmenters() {
081: return (Vertex[]) _bestFragmenters
082: .toArray(new Vertex[_bestFragmenters.size()]);
083: }
084:
085: void addFragmenter(Vertex vertex) {
086: _bestFragmenters.add(vertex);
087: }
088:
089: public int[] getEccentricities() {
090: return _eccentricities;
091: }
092:
093: void setEccentricities(int[] eccentricities) {
094: _eccentricities = eccentricities;
095:
096: // Calculate radius and diameter
097: _radius = Integer.MAX_VALUE;
098: _diameter = 0;
099: for (int i = 0; i < eccentricities.length; i++) {
100: _radius = Math.min(_radius, eccentricities[i]);
101: _diameter = Math.max(_diameter, eccentricities[i]);
102: }
103: }
104:
105: public int[] getMaximumFragmentSizes() {
106: return _maximumFragmentSizes;
107: }
108:
109: void setMaximumFragmentSizes(int[] maximumFragmentSizes) {
110: _maximumFragmentSizes = maximumFragmentSizes;
111:
112: _bestFragmentSize = Integer.MAX_VALUE;
113: for (int i = 0; i < maximumFragmentSizes.length; i++) {
114: _bestFragmentSize = Math.min(_bestFragmentSize,
115: maximumFragmentSizes[i]);
116: }
117: }
118:
119: public int compareTo(Object object) {
120: int result = 1;
121: if (object instanceof GeometryAttributes
122: && _bestFragmenters.size() > 0) {
123: ArrayList list = ((GeometryAttributes) object)._bestFragmenters;
124: if (list.size() > 0) {
125: Attributes attributes = ((Vertex) _bestFragmenters
126: .get(0)).getAttributes();
127: Attributes objectAttributes = ((Vertex) list.get(0))
128: .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: /**
142: * Default constructor. The {@link Attributes} of a strong component will
143: * a <tt>null</tt> pointer.
144: */
145: public StrongComponent() {
146: super (new GeometryAttributes());
147: }
148:
149: /** Returns the number of vertices building this strong component. */
150: public int getNumberOfVertices() {
151: return _vertices.size();
152: }
153:
154: /** Returns the vertex of the specified index. */
155: public AtomicVertex getVertex(int index) {
156: return (AtomicVertex) _vertices.elementAt(index);
157: }
158:
159: /**
160: * Adds the specified vertex to this strong component. Note, that added
161: * vertices are inserted at index 0 of the list of vertices.
162: */
163: public void addVertex(AtomicVertex vertex) {
164: _vertices.insertElementAt(vertex, 0);
165: }
166:
167: /**
168: * Calculates all graph properties of this component.
169: * These properties can be obtained from <tt>getAttributes</tt> casted as
170: * {@link GraphAttributes}.
171: */
172: public void calculateAttributes() {
173: HashMap indexMap = calculateIndexMap();
174: int[][] distances = calculateDistances(indexMap);
175:
176: // Calculate girth and eccentricity
177: 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],
186: distances[i][j]);
187: }
188: }
189: }
190: attributes.setEccentricities(eccentricities);
191: attributes.setGirth(girth);
192: attributes
193: .setMaximumFragmentSizes(calculateMaximumFragmentSizes(indexMap));
194:
195: // Obtain center vertices and best fragmenters
196: for (int i = 0, r = attributes.getRadius(), s = attributes
197: .getBestFragmentSize(); i < distances.length; i++) {
198: if (eccentricities[i] == r) {
199: attributes.addVertex(getVertex(i));
200: }
201: if (attributes.getMaximumFragmentSizes()[i] == s) {
202: attributes.addFragmenter(getVertex(i));
203: }
204: }
205:
206: }
207:
208: private int[][] calculateDistances(HashMap indexMap) {
209: // Calculate the adjacency matrix
210: int n = getNumberOfVertices();
211: int[][] distances = new int[n][n];
212: for (int i = 0; i < n; i++) {
213: int[] row = distances[i];
214: AtomicVertex vertex = getVertex(i);
215: for (int j = 0; j < n; j++) {
216: row[j] = Integer.MAX_VALUE / 2;
217: }
218: for (int j = 0, m = vertex.getNumberOfOutgoingArcs(); j < m; j++) {
219: Integer index = (Integer) indexMap.get(vertex
220: .getHeadVertex(j));
221: if (index != null) {
222: row[index.intValue()] = 1;
223: }
224: }
225: }
226:
227: // Floyd-Warshall algorithm for the distances
228: for (int k = 0; k < n; k++) {
229: for (int i = 0; i < n; i++) {
230: for (int j = 0; j < n; j++) {
231: if (distances[i][k] + distances[k][j] < distances[i][j]) {
232: distances[i][j] = distances[i][k]
233: + distances[k][j];
234: }
235: }
236: }
237: }
238:
239: return distances;
240: }
241:
242: private HashMap calculateIndexMap() {
243: HashMap result = new HashMap();
244: for (int i = 0, n = getNumberOfVertices(); i < n; i++) {
245: result.put(getVertex(i), new Integer(i));
246: }
247: return result;
248: }
249:
250: private int[] calculateMaximumFragmentSizes(HashMap indexMap) {
251: // clone graph defining this strong component
252: AtomicVertex[] graph = new AtomicVertex[getNumberOfVertices()];
253: for (int i = 0; i < graph.length; i++) {
254: graph[i] = new AtomicVertex(null);
255: }
256: for (int i = 0; i < graph.length; i++) {
257: AtomicVertex vertex = getVertex(i);
258: for (int j = 0, n = vertex.getNumberOfOutgoingArcs(); j < n; j++) {
259: Integer index = (Integer) indexMap.get(vertex
260: .getHeadVertex(j));
261: if (index != null) {
262: graph[i].addOutgoingArcTo(graph[index.intValue()]);
263: }
264: }
265: }
266:
267: StrongComponentProcessor processor = new StrongComponentProcessor(
268: false);
269: int[] maximumFragmentSizes = new int[getNumberOfVertices()];
270: for (int i = 0; i < maximumFragmentSizes.length; i++) {
271: graph[i].setDefaultValueOfGraphVertexFlag(false);
272: processor.deepSearchFirst(graph);
273: StrongComponent[] fragments = processor
274: .getStrongComponents();
275: maximumFragmentSizes[i] = 0;
276: for (int j = 0; j < fragments.length; j++) {
277: maximumFragmentSizes[i] = Math.max(
278: maximumFragmentSizes[i], fragments[j]
279: .getNumberOfVertices());
280: }
281: graph[i].setDefaultValueOfGraphVertexFlag(true);
282: }
283: return maximumFragmentSizes;
284: }
285:
286: /**
287: * Reset this component. Calls reset of the superclass. Sets the activity
288: * flag to false and the longest walk to -1.
289: */
290: public void reset() {
291: super .reset();
292: _active = false;
293: _longestWalk = -1;
294: }
295:
296: public boolean isActive() {
297: return _active;
298: }
299:
300: public void setActive(boolean active) {
301: _active = active;
302: }
303:
304: public int getLongestWalk() {
305: return _longestWalk;
306: }
307:
308: public void setLongestWalk(int longestWalk) {
309: _longestWalk = longestWalk;
310: }
311:
312: public String toString() {
313: StringBuffer result = new StringBuffer("Strong component with ");
314: int n = getNumberOfVertices();
315: result.append(n).append(n > 1 ? " vertices." : " vertex.");
316: result.append(" Longest walk: ").append(getLongestWalk());
317: for (int i = 0; i < n; i++) {
318: result.append("\n ").append(getVertex(i));
319: }
320: return new String(result);
321: }
322: } //class
|