|
1
19
20
25
26
27 package soot.toolkits.graph;
28
29
30 import java.util.*;
31 import soot.*;
32 import soot.util.*;
33
34
35
36
37
40
41 public class HashMutableDirectedGraph implements MutableDirectedGraph {
42
43
44 protected HashMap nodeToPreds = new HashMap();
45 protected HashMap nodeToSuccs = new HashMap();
46
47 protected Chain heads = new HashChain();
48 protected Chain tails = new HashChain();
49
50 public HashMutableDirectedGraph()
51 {
52 }
53
54
55 public void clearAll() {
56 nodeToPreds = new HashMap();
57 nodeToSuccs = new HashMap();
58 heads = new HashChain();
59 tails = new HashChain();
60 }
61
62 public Object  clone() {
63 HashMutableDirectedGraph g = new HashMutableDirectedGraph();
64 g.nodeToPreds = (HashMap)nodeToPreds.clone();
65 g.nodeToSuccs = (HashMap)nodeToSuccs.clone();
66 g.heads = HashChain.listToHashChain(HashChain.toList(heads));
67 g.tails = HashChain.listToHashChain(HashChain.toList(tails));
68 return g;
69 }
70
71
72 public List getHeads()
73 {
74 ArrayList l = new ArrayList(); l.addAll(heads);
75 return Collections.unmodifiableList(l);
76 }
77
78
79 public List getTails()
80 {
81 ArrayList l = new ArrayList(); l.addAll(tails);
82 return Collections.unmodifiableList(l);
83 }
84
85 public List getPredsOf(Object s)
86 {
87 List l = (List) nodeToPreds.get(s);
88 if (l != null)
89 return Collections.unmodifiableList(l);
90 else
91 throw new RuntimeException (s+"not in graph!");
92 }
93
94 public List getSuccsOf(Object s)
95 {
96 List l = (List) nodeToSuccs.get(s);
97 if (l != null)
98 return Collections.unmodifiableList(l);
99 else
100 throw new RuntimeException (s+"not in graph!");
101 }
102
103 public int size()
104 {
105 return nodeToPreds.keySet().size();
106 }
107
108 public Iterator iterator()
109 {
110 return nodeToPreds.keySet().iterator();
111 }
112
113 public void addEdge(Object from, Object to)
114 {
115 if (from == null || to == null)
116 throw new RuntimeException ("edge from or to null");
117
118 if (containsEdge(from, to))
119 return;
120
121 List succsList = (List)nodeToSuccs.get(from);
122 if (succsList == null)
123 throw new RuntimeException (from + " not in graph!");
124
125 List predsList = (List)nodeToPreds.get(to);
126 if (predsList == null)
127 throw new RuntimeException (to + " not in graph!");
128
129 if (heads.contains(to))
130 heads.remove(to);
131
132 if (tails.contains(from))
133 tails.remove(from);
134
135 succsList.add(to);
136 predsList.add(from);
137 }
138
139 public void removeEdge(Object from, Object to)
140 {
141 if (!containsEdge(from, to))
142 return;
143
144 List succsList = (List)nodeToSuccs.get(from);
145 if (succsList == null)
146 throw new RuntimeException (from + " not in graph!");
147
148 List predsList = (List)nodeToPreds.get(to);
149 if (predsList == null)
150 throw new RuntimeException (to + " not in graph!");
151
152 succsList.remove(to);
153 predsList.remove(from);
154
155 if (succsList.isEmpty())
156 tails.add(from);
157
158 if (predsList.isEmpty())
159 heads.add(to);
160 }
161
162 public boolean containsEdge(Object from, Object to)
163 {
164 List succs = (List)nodeToSuccs.get(from);
165 if (succs == null)
166 return false;
167 return succs.contains(to);
168 }
169
170 public boolean containsNode(Object node)
171 {
172 return nodeToPreds.keySet().contains(node);
173 }
174
175 public List getNodes()
176 {
177 return Arrays.asList(nodeToPreds.keySet().toArray());
178 }
179
180 public void addNode(Object node)
181 {
182 if (containsNode(node))
183 throw new RuntimeException ("Node already in graph");
184
185 nodeToSuccs.put(node, new ArrayList());
186 nodeToPreds.put(node, new ArrayList());
187 heads.add(node);
188 tails.add(node);
189 }
190
191 public void removeNode(Object node)
192 {
193 List succs = (List)((ArrayList)nodeToSuccs.get(node)).clone();
194 for (Iterator succsIt = succs.iterator(); succsIt.hasNext(); )
195 removeEdge(node, succsIt.next());
196 nodeToSuccs.remove(node);
197
198 List preds = (List)((ArrayList)nodeToPreds.get(node)).clone();
199 for (Iterator predsIt = preds.iterator(); predsIt.hasNext(); )
200 removeEdge(predsIt.next(), node);
201 nodeToPreds.remove(node);
202
203 if (heads.contains(node))
204 heads.remove(node);
205
206 if (tails.contains(node))
207 tails.remove(node);
208 }
209
210 public void printGraph() {
211
212 for (Iterator it = iterator(); it.hasNext(); ) {
213 Object node = it.next();
214 G.v().out.println("Node = "+node);
215 G.v().out.println("Preds:");
216 for (Iterator predsIt = getPredsOf(node).iterator(); predsIt.hasNext(); ) {
217 G.v().out.print(" ");
218 G.v().out.println(predsIt.next());
219 }
220 G.v().out.println("Succs:");
221 for (Iterator succsIt = getSuccsOf(node).iterator(); succsIt.hasNext(); ) {
222 G.v().out.print(" ");
223 G.v().out.println(succsIt.next());
224 }
225 }
226 }
227
228 }
229
230
231 |
Popular Tags |
Java API By Example, From Geeks To Geeks.