KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > classycle > graph > StrongComponentProcessor


1 /*
2  * Copyright (c) 2003-2006, Franz-Josef Elmer, All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions are met:
6  *
7  * - Redistributions of source code must retain the above copyright notice,
8  * this list of conditions and the following disclaimer.
9  * - 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.Enumeration JavaDoc;
28 import java.util.Hashtable JavaDoc;
29 import java.util.Stack JavaDoc;
30 import java.util.Vector JavaDoc;
31
32 /**
33  * A processor which extracts the strong components of a directed graph.
34  * A strong component is a maximal strongly connected subgraph of a
35  * directed graph. The implementation is based on Tarjan's algorithm.
36  *
37  * @author Franz-Josef Elmer
38  */
39 public class StrongComponentProcessor extends GraphProcessor {
40   private final boolean _calculateAttributes;
41   private int _counter;
42   private Stack JavaDoc _vertexStack = new Stack JavaDoc();
43   private Vector JavaDoc _strongComponents = new Vector JavaDoc();
44   private Hashtable JavaDoc _vertexToComponents = new Hashtable JavaDoc();
45   private StrongComponent[] _graph;
46   
47   /**
48    * Creates an instance.
49    * @param calculateAttributes If <tt>true</tt> the attributes of the
50    * strong components will be calculated. Otherwise not.
51    */
52   public StrongComponentProcessor(boolean calculateAttributes) {
53     _calculateAttributes = calculateAttributes;
54   }
55
56   /**
57    * Returns the result of {@link #deepSearchFirst}.
58    */
59   public StrongComponent[] getStrongComponents() {
60     return _graph;
61   }
62
63   protected void initializeProcessing(Vertex[] graph) {
64     _counter = 0;
65     _vertexStack.setSize(0);
66     _strongComponents.setSize(0);
67     _vertexToComponents.clear();
68   }
69
70   /**
71    * @throws IllegalArgumentException if <tt>vertex</tt> is not an instance
72    * of {@link AtomicVertex}.
73    */
74   protected void processBefore(Vertex vertex) {
75     final AtomicVertex atomicVertex = castAsAtomicVertex(vertex);
76     atomicVertex.setOrder(_counter);
77     atomicVertex.setLow(_counter++);
78     _vertexStack.push(atomicVertex);
79   }
80
81   /**
82    * @throws IllegalArgumentException if <tt>tail</tt> and <tt>head</tt> are
83    * not an instances of {@link AtomicVertex}.
84    */
85   protected void processArc(Vertex tail, Vertex head) {
86     final AtomicVertex t = castAsAtomicVertex(tail);
87     final AtomicVertex h = castAsAtomicVertex(head);
88     if (h.isGraphVertex()) {
89       if (!h.isVisited()) {
90         process(h);
91         t.setLow(Math.min(t.getLow(), h.getLow()));
92       } else if (h.getOrder() < t.getOrder() && _vertexStack.contains(h)) {
93         t.setLow(Math.min(t.getLow(), h.getOrder()));
94       }
95     }
96   }
97
98   /**
99    * Processes the specified vertex after all its outgoing arcs are
100    * processed.
101    * @throws IllegalArgumentException if <tt>vertex</tt> is not an instance
102    * of {@link AtomicVertex}.
103    */
104   protected void processAfter(Vertex vertex) {
105     final AtomicVertex atomicVertex = castAsAtomicVertex(vertex);
106     if (atomicVertex.getLow() == atomicVertex.getOrder()) {
107       StrongComponent component = new StrongComponent();
108       while (!_vertexStack.isEmpty()
109              && ((AtomicVertex) _vertexStack.peek()).getOrder()
110           >= atomicVertex.getOrder()) {
111         AtomicVertex vertexOfComponent = (AtomicVertex) _vertexStack.pop();
112         component.addVertex(vertexOfComponent);
113         _vertexToComponents.put(vertexOfComponent, component);
114       }
115       _strongComponents.addElement(component);
116     }
117   }
118
119   /**
120    * Adds all arcs to the strong components. There is an arc from a strong
121    * component to another one if there is at least one arc from a vertex
122    * of one component to a vertex the other one.
123    */
124   protected void finishProcessing(Vertex[] graph) {
125     _graph = new StrongComponent[_strongComponents.size()];
126     for (int i = 0; i < _graph.length; i++) {
127       _graph[i] = (StrongComponent) _strongComponents.elementAt(i);
128       if (_calculateAttributes) {
129         _graph[i].calculateAttributes();
130       }
131     }
132
133     Enumeration JavaDoc keys = _vertexToComponents.keys();
134     while (keys.hasMoreElements()) {
135       AtomicVertex vertex = (AtomicVertex) keys.nextElement();
136       StrongComponent tail = (StrongComponent) _vertexToComponents.get(vertex);
137       for (int i = 0, n = vertex.getNumberOfOutgoingArcs(); i < n; i++) {
138         AtomicVertex h = (AtomicVertex) vertex.getHeadVertex(i);
139         if (h.isGraphVertex()) {
140           StrongComponent head = (StrongComponent) _vertexToComponents.get(h);
141           if (head != null && head != tail) {
142             tail.addOutgoingArcTo(head);
143           }
144         }
145       }
146     }
147   }
148
149   /**
150    * Casts the specified vertex as an {@link AtomicVertex}.
151    * @throws IllegalArgumentException if <tt>vertex</tt> is not an instance
152    * of {@link AtomicVertex}.
153    */
154   private AtomicVertex castAsAtomicVertex(Vertex vertex) {
155     if (vertex instanceof AtomicVertex) {
156       return (AtomicVertex) vertex;
157     } else {
158       throw new IllegalArgumentException JavaDoc(
159         vertex + " is not an instance of AtomicVertex");
160     }
161   }
162 } //class
Popular Tags