KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > soot > toolkits > graph > StronglyConnectedComponents


1 /* Soot - a J*va Optimization Framework
2  * Copyright (C) 1999 Patrick Lam, Raja Vallee-Rai
3  *
4  * This library is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU Lesser General Public
6  * License as published by the Free Software Foundation; either
7  * version 2.1 of the License, or (at your option) any later version.
8  *
9  * This library is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12  * Lesser General Public License for more details.
13  *
14  * You should have received a copy of the GNU Lesser General Public
15  * License along with this library; if not, write to the
16  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17  * Boston, MA 02111-1307, USA.
18  */
19
20 /*
21  * Modified by the Sable Research Group and others 1997-1999.
22  * See the 'credits' file distributed with Soot for the complete list of
23  * contributors. (Soot is distributed at http://www.sable.mcgill.ca/soot)
24  */
25
26 package soot.toolkits.graph;
27 import soot.options.*;
28
29 import soot.*;
30 import soot.util.*;
31 import java.util.*;
32
33
34
35 /**
36  * Identifies and provides an interface to query the strongly-connected
37  * components of DirectedGraph instances.
38  * @see DirectedGraph
39  */
40
41 public class StronglyConnectedComponents
42 {
43     private HashMap nodeToColor;
44     private static final Object JavaDoc Visited=new Object JavaDoc();
45     private static final Object JavaDoc Black=new Object JavaDoc();
46     private LinkedList finishingOrder;
47     private List componentList = new ArrayList();
48     private HashMap nodeToComponent = new HashMap();
49     MutableDirectedGraph sccGraph = new HashMutableDirectedGraph();
50     private int[] indexStack;
51     private Object JavaDoc[] nodeStack;
52     private int last;
53     
54     /**
55      * @param g a graph for which we want to compute the strongly
56      * connected components.
57      * @see DirectedGraph
58      */
59     public StronglyConnectedComponents(DirectedGraph g)
60     {
61     nodeToColor = new HashMap((3*g.size())/2,0.7f);
62     indexStack = new int[g.size()];
63     nodeStack = new Object JavaDoc[g.size()];
64     finishingOrder = new LinkedList();
65     
66         // Visit each node
67 {
68             Iterator nodeIt = g.iterator();
69             
70             while(nodeIt.hasNext())
71             {
72                 Object JavaDoc s = nodeIt.next();
73                
74                 if(nodeToColor.get(s) == null)
75                     visitNode(g, s);
76             }
77         }
78
79     
80         // Re-color all nodes white
81 nodeToColor = new HashMap((3*g.size()),0.7f);
82
83         // Visit each node via transpose edges
84 {
85             Iterator revNodeIt = finishingOrder.iterator();
86             while (revNodeIt.hasNext())
87             {
88                 Object JavaDoc s = revNodeIt.next();
89
90                 if(nodeToColor.get(s) == null)
91                 {
92                     List currentComponent = null;
93
94             currentComponent = new StationaryArrayList();
95             nodeToComponent.put(s, currentComponent);
96             sccGraph.addNode(currentComponent);
97             componentList.add(currentComponent);
98
99                     visitRevNode(g, s, currentComponent);
100                 }
101             }
102         }
103         componentList = Collections.unmodifiableList(componentList);
104
105         if (Options.v().verbose())
106         {
107             G.v().out.println("Done computing scc components");
108             G.v().out.println("number of nodes in underlying graph: "+g.size());
109             G.v().out.println("number of components: "+sccGraph.size());
110         }
111     }
112
113     private void visitNode(DirectedGraph graph, Object JavaDoc startNode)
114     {
115         last=0;
116         nodeToColor.put(startNode, Visited);
117         
118         nodeStack[last]=startNode;
119         indexStack[last++]= -1;
120
121     while(last>0)
122         {
123         int toVisitIndex = ++indexStack[last-1];
124             Object JavaDoc toVisitNode = nodeStack[last-1];
125            
126         if(toVisitIndex >= graph.getSuccsOf(toVisitNode).size())
127             {
128                 // Visit this node now that we ran out of children
129 finishingOrder.addFirst(toVisitNode);
130
131                 // Pop this node off
132 last--;
133             }
134             else
135             {
136                 Object JavaDoc childNode = graph.getSuccsOf(toVisitNode).get(toVisitIndex);
137                 
138                 // Visit this child next if not already visited (or on stack)
139 if(nodeToColor.get(childNode) == null)
140                     {
141                         nodeToColor.put(childNode, Visited);
142                         
143             nodeStack[last]=childNode;
144             indexStack[last++]=-1;
145                     }
146             }
147         }
148     }
149
150     private void visitRevNode(DirectedGraph graph, Object JavaDoc startNode, List currentComponent)
151     {
152     last=0;
153         
154         nodeToColor.put(startNode, Visited);
155         
156     nodeStack[last]=startNode;
157         indexStack[last++]= -1;
158
159     while(last>0)
160         {
161         int toVisitIndex = ++indexStack[last-1];
162             Object JavaDoc toVisitNode = nodeStack[last-1];
163             
164             if(toVisitIndex >= graph.getPredsOf(toVisitNode).size())
165             {
166                 // No more nodes. Add toVisitNode to current component.
167 currentComponent.add(toVisitNode);
168         nodeToComponent.put(toVisitNode, currentComponent);
169         nodeToColor.put(toVisitNode, Black);
170                 // Pop this node off
171 last--;
172             }
173             else
174             {
175                 Object JavaDoc childNode = graph.getPredsOf(toVisitNode).get(toVisitIndex);
176                 
177                 // Visit this child next if not already visited (or on stack)
178 if(nodeToColor.get(childNode) == null)
179                 {
180             nodeToColor.put(childNode, Visited);
181             
182             nodeStack[last]=childNode;
183             indexStack[last++]=-1;
184         }
185
186         else if (nodeToColor.get(childNode) == Black)
187         {
188             /* we may be visiting a node in another component. if so, add edge to sccGraph. */
189             if (nodeToComponent.get(childNode) != currentComponent)
190             sccGraph.addEdge(nodeToComponent.get(childNode), currentComponent);
191         }
192             }
193         }
194     }
195
196
197     /**
198      * Checks if 2 nodes are in the same strongly-connnected component.
199      * @param a some graph node.
200      * @param b some graph node
201      * @return true if both nodes are in the same strongly-connnected component.
202      * false otherwise.
203      */
204     public boolean equivalent(Object JavaDoc a, Object JavaDoc b)
205     {
206         return nodeToComponent.get(a) == nodeToComponent.get(b);
207     }
208
209
210     /**
211      * @return a list of the strongly-connnected components that make
212      * up the computed strongly-connnect component graph.
213      */
214     public List getComponents()
215     {
216         return componentList;
217     }
218
219     /**
220      * @param a a node of the original graph.
221      * @return the strongly-connnected component node
222      * to which the parameter node belongs.
223      */
224     public List getComponentOf(Object JavaDoc a)
225     {
226         return (List)nodeToComponent.get(a);
227     }
228
229     /**
230      * @return the computed strongly-connnected component graph.
231      * @see DirectedGraph
232      */
233     public DirectedGraph getSuperGraph()
234     {
235         /* we should make this unmodifiable at some point. */
236         return sccGraph;
237     }
238 }
239
Popular Tags