KickJava   Java API By Example, From Geeks To Geeks.

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


1 /* Soot - a J*va Optimization Framework
2  * Copyright (C) 1997-1999 Raja Vallee-Rai, Patrick Lam
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
27 package soot.toolkits.graph;
28
29 import soot.*;
30 import soot.util.*;
31 import java.util.*;
32
33
34 /**
35  * Orders in pseudo-topological order,
36  * the nodes of a DirectedGraph instance.
37  */

38
39 /* Updated By Marc Berndl May 13 */
40
41 public class PseudoTopologicalOrderer
42 {
43     public static final boolean REVERSE = true;
44     public PseudoTopologicalOrderer() {}
45     public PseudoTopologicalOrderer(boolean isReversed) { mIsReversed = isReversed;}
46
47     private Map stmtToColor;
48     private static final Object JavaDoc GRAY = new Object JavaDoc();
49     private LinkedList order;
50     private boolean mIsReversed = false;
51     private DirectedGraph graph;
52     private int[] indexStack;
53     private Object JavaDoc[] stmtStack;
54     private int last;
55         
56     /**
57      * @param g a DirectedGraph instance whose nodes we wish to order.
58      * @return a pseudo-topologically ordered list of the graph's nodes.
59      */

60     public List newList(DirectedGraph g)
61     {
62         return computeOrder(g);
63     }
64
65     /**
66      * Set the ordering for the orderer.
67      * @param isReverse specify if we want reverse pseudo-topological ordering, or not.
68      */

69     public void setReverseOrder(boolean isReversed)
70     {
71         mIsReversed = isReversed;
72     }
73
74     /**
75      * Check the ordering for the orderer.
76      * @return true if we have reverse pseudo-topological ordering, false otherwise.
77      */

78     public boolean isReverseOrder()
79     {
80         return mIsReversed;
81     }
82
83     /**
84      * Orders in pseudo-topological order.
85      * @param g a DirectedGraph instance we want to order the nodes for.
86      * @return an ordered list of the graph's nodes.
87      */

88     LinkedList computeOrder(DirectedGraph g)
89     {
90         stmtToColor = new HashMap((3*g.size())/2,0.7f);
91         indexStack = new int[g.size()];
92         stmtStack = new Object JavaDoc[g.size()];
93         order = new LinkedList();
94         graph = g;
95         
96         // Visit each node
97
{
98             Iterator stmtIt = g.iterator();
99             while(stmtIt.hasNext())
100             {
101                 Object JavaDoc s = stmtIt.next();
102                 if(stmtToColor.get(s) == null)
103                     visitNode(s);
104             }
105         }
106         indexStack = null;
107         stmtStack = null;
108         stmtToColor = null;
109         return order;
110     }
111
112     // Unfortunately, the nice recursive solution fails
113
// because of stack overflows
114

115     // Fill in the 'order' list with a pseudo topological order (possibly reversed)
116
// list of statements starting at s. Simulates recursion with a stack.
117

118     
119     private void visitNode(Object JavaDoc startStmt)
120     {
121         last = 0;
122         
123         stmtToColor.put(startStmt, GRAY);
124         
125         stmtStack[last] = startStmt;
126         indexStack[last++]= -1;
127         while(last > 0)
128     {
129             int toVisitIndex = ++indexStack[last-1];
130             Object JavaDoc toVisitNode = stmtStack[last-1];
131             
132             if(toVisitIndex >= graph.getSuccsOf(toVisitNode).size())
133             {
134                 // Visit this node now that we ran out of children
135
if(mIsReversed)
136                         order.addLast(toVisitNode);
137                     else
138                         order.addFirst(toVisitNode);
139                            
140             last--;
141             }
142             else
143             {
144                 Object JavaDoc childNode = graph.getSuccsOf(toVisitNode).get(toVisitIndex);
145                 
146                     if(stmtToColor.get(childNode) == null)
147                     {
148                         stmtToColor.put(childNode, GRAY);
149                         stmtStack[last]=childNode;
150             indexStack[last++]=-1;
151             }
152             }
153         }
154     }
155     
156 }
157
Popular Tags