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.Enumeration;
028: import java.util.Hashtable;
029: import java.util.Stack;
030: import java.util.Vector;
031:
032: /**
033: * A processor which extracts the strong components of a directed graph.
034: * A strong component is a maximal strongly connected subgraph of a
035: * directed graph. The implementation is based on Tarjan's algorithm.
036: *
037: * @author Franz-Josef Elmer
038: */
039: public class StrongComponentProcessor extends GraphProcessor {
040: private final boolean _calculateAttributes;
041: private int _counter;
042: private Stack _vertexStack = new Stack();
043: private Vector _strongComponents = new Vector();
044: private Hashtable _vertexToComponents = new Hashtable();
045: private StrongComponent[] _graph;
046:
047: /**
048: * Creates an instance.
049: * @param calculateAttributes If <tt>true</tt> the attributes of the
050: * strong components will be calculated. Otherwise not.
051: */
052: public StrongComponentProcessor(boolean calculateAttributes) {
053: _calculateAttributes = calculateAttributes;
054: }
055:
056: /**
057: * Returns the result of {@link #deepSearchFirst}.
058: */
059: public StrongComponent[] getStrongComponents() {
060: return _graph;
061: }
062:
063: protected void initializeProcessing(Vertex[] graph) {
064: _counter = 0;
065: _vertexStack.setSize(0);
066: _strongComponents.setSize(0);
067: _vertexToComponents.clear();
068: }
069:
070: /**
071: * @throws IllegalArgumentException if <tt>vertex</tt> is not an instance
072: * of {@link AtomicVertex}.
073: */
074: protected void processBefore(Vertex vertex) {
075: final AtomicVertex atomicVertex = castAsAtomicVertex(vertex);
076: atomicVertex.setOrder(_counter);
077: atomicVertex.setLow(_counter++);
078: _vertexStack.push(atomicVertex);
079: }
080:
081: /**
082: * @throws IllegalArgumentException if <tt>tail</tt> and <tt>head</tt> are
083: * not an instances of {@link AtomicVertex}.
084: */
085: protected void processArc(Vertex tail, Vertex head) {
086: final AtomicVertex t = castAsAtomicVertex(tail);
087: final AtomicVertex h = castAsAtomicVertex(head);
088: if (h.isGraphVertex()) {
089: if (!h.isVisited()) {
090: process(h);
091: t.setLow(Math.min(t.getLow(), h.getLow()));
092: } else if (h.getOrder() < t.getOrder()
093: && _vertexStack.contains(h)) {
094: t.setLow(Math.min(t.getLow(), h.getOrder()));
095: }
096: }
097: }
098:
099: /**
100: * Processes the specified vertex after all its outgoing arcs are
101: * processed.
102: * @throws IllegalArgumentException if <tt>vertex</tt> is not an instance
103: * of {@link AtomicVertex}.
104: */
105: protected void processAfter(Vertex vertex) {
106: final AtomicVertex atomicVertex = castAsAtomicVertex(vertex);
107: if (atomicVertex.getLow() == atomicVertex.getOrder()) {
108: StrongComponent component = new StrongComponent();
109: while (!_vertexStack.isEmpty()
110: && ((AtomicVertex) _vertexStack.peek()).getOrder() >= atomicVertex
111: .getOrder()) {
112: AtomicVertex vertexOfComponent = (AtomicVertex) _vertexStack
113: .pop();
114: component.addVertex(vertexOfComponent);
115: _vertexToComponents.put(vertexOfComponent, component);
116: }
117: _strongComponents.addElement(component);
118: }
119: }
120:
121: /**
122: * Adds all arcs to the strong components. There is an arc from a strong
123: * component to another one if there is at least one arc from a vertex
124: * of one component to a vertex the other one.
125: */
126: protected void finishProcessing(Vertex[] graph) {
127: _graph = new StrongComponent[_strongComponents.size()];
128: for (int i = 0; i < _graph.length; i++) {
129: _graph[i] = (StrongComponent) _strongComponents
130: .elementAt(i);
131: if (_calculateAttributes) {
132: _graph[i].calculateAttributes();
133: }
134: }
135:
136: Enumeration keys = _vertexToComponents.keys();
137: while (keys.hasMoreElements()) {
138: AtomicVertex vertex = (AtomicVertex) keys.nextElement();
139: StrongComponent tail = (StrongComponent) _vertexToComponents
140: .get(vertex);
141: for (int i = 0, n = vertex.getNumberOfOutgoingArcs(); i < n; i++) {
142: AtomicVertex h = (AtomicVertex) vertex.getHeadVertex(i);
143: if (h.isGraphVertex()) {
144: StrongComponent head = (StrongComponent) _vertexToComponents
145: .get(h);
146: if (head != null && head != tail) {
147: tail.addOutgoingArcTo(head);
148: }
149: }
150: }
151: }
152: }
153:
154: /**
155: * Casts the specified vertex as an {@link AtomicVertex}.
156: * @throws IllegalArgumentException if <tt>vertex</tt> is not an instance
157: * of {@link AtomicVertex}.
158: */
159: private AtomicVertex castAsAtomicVertex(Vertex vertex) {
160: if (vertex instanceof AtomicVertex) {
161: return (AtomicVertex) vertex;
162: } else {
163: throw new IllegalArgumentException(vertex
164: + " is not an instance of AtomicVertex");
165: }
166: }
167: } //class
|