01: /*
02: * Copyright (c) 2003-2008, Franz-Josef Elmer, All rights reserved.
03: *
04: * Redistribution and use in source and binary forms, with or without
05: * modification, are permitted provided that the following conditions are met:
06: *
07: * - Redistributions of source code must retain the above copyright notice,
08: * this list of conditions and the following disclaimer.
09: * - Redistributions in binary form must reproduce the above copyright notice,
10: * this list of conditions and the following disclaimer in the documentation
11: * and/or other materials provided with the distribution.
12: *
13: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
14: * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
15: * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16: * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
17: * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18: * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19: * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
20: * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
21: * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
22: * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
23: * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24: */
25: package classycle.graph;
26:
27: import java.util.HashMap;
28: import java.util.Map;
29:
30: /**
31: * Analyser of a directed graph for finding its strong components.
32: *
33: * @author Franz-Josef Elmer
34: */
35: public class StrongComponentAnalyser {
36: private final AtomicVertex[] _graph;
37: private StrongComponent[] _components;
38: private HashMap _layerMap;
39:
40: /**
41: * Creates an instance for the specified graph.
42: */
43: public StrongComponentAnalyser(AtomicVertex[] graph) {
44: _graph = graph;
45: //Arrays.sort(_graph, null);
46: }
47:
48: /** Returns the original graph. That is, the argument of the constructor. */
49: public AtomicVertex[] getGraph() {
50: return _graph;
51: }
52:
53: /** Returns the graph of strong components. */
54: public StrongComponent[] getCondensedGraph() {
55: if (_components == null) {
56: StrongComponentProcessor processor = new StrongComponentProcessor(
57: true);
58: processor.deepSearchFirst(_graph);
59: _components = processor.getStrongComponents();
60: }
61: return _components;
62: }
63:
64: /**
65: * Returns the maping of the nodes of the original graph onto a layer index
66: * (i.e. length of the longest path of the condensed graph).
67: * @return a map where the keys are instances of {@link AtomicVertex}
68: * and the values are instances of <tt>Integer</tt>.
69: */
70: public Map getLayerMap() {
71: if (_layerMap == null) {
72: StrongComponent[] components = getCondensedGraph();
73: new LongestWalkProcessor().deepSearchFirst(components);
74: _layerMap = new HashMap();
75: for (int i = 0; i < components.length; i++) {
76: StrongComponent component = components[i];
77: Integer layer = new Integer(component.getLongestWalk());
78: for (int j = 0, n = component.getNumberOfVertices(); j < n; j++) {
79: _layerMap.put(component.getVertex(j), layer);
80: }
81: }
82: }
83: return _layerMap;
84: }
85:
86: }
|