Mercurial > hg > truffle

comparison visualizer/HierarchicalLayout/src/com/sun/hotspot/igv/hierarchicallayout/Graph.java @ 4512:015fb895586b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Moved visualizer to new directory.
author Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
date Tue, 07 Feb 2012 22:41:09 +0100
parents
children
comparison
equal deleted inserted replaced
4511:6cb549627941 4512:015fb895586b
1 /*
2 * Copyright (c) 2008, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
24 package com.sun.hotspot.igv.hierarchicallayout;
25
26 import java.util.*;
27
28 /**
29 *
30 * @author Thomas Wuerthinger
31 */
32 public class Graph<N, E> {
33
34 private HashMap<Object, Node<N, E>> nodes;
35 private HashMap<Object, Edge<N, E>> edges;
36 private List<Node<N, E>> nodeList;
37
38 public Graph() {
39 nodes = new HashMap<>();
40 edges = new HashMap<>();
41 nodeList = new ArrayList<>();
42 }
43
44 public Node<N, E> createNode(N data, Object key) {
45 Node<N, E> n = new Node<>(this, data);
46 assert key == null || !nodes.containsKey(key);
47 if (key != null) {
48 nodes.put(key, n);
49 }
50 nodeList.add(n);
51 return n;
52 }
53
54 public Edge<N, E> createEdge(Node<N, E> source, Node<N, E> dest, E data, Object key) {
55 Edge<N, E> e = new Edge<>(this, source, dest, data);
56 source.addOutEdge(e);
57 dest.addInEdge(e);
58 if (key != null) {
59 edges.put(key, e);
60 }
61 return e;
62 }
63
64 public Node<N, E> getNode(Object key) {
65 return nodes.get(key);
66 }
67
68 public Edge<N, E> getEdge(Object key) {
69 return edges.get(key);
70 }
71
72 public Collection<Edge<N, E>> getEdges() {
73 return Collections.unmodifiableCollection(edges.values());
74 }
75
76 public Collection<Node<N, E>> getNodes() {
77 return Collections.unmodifiableList(nodeList);
78 }
79
80 public void removeEdge(Edge<N, E> e, Object key) {
81 assert key == null || edges.containsKey(key);
82 if (key != null) {
83 edges.remove(key);
84 }
85 e.getSource().removeOutEdge(e);
86 e.getDest().removeInEdge(e);
87 }
88
89 public class DFSTraversalVisitor {
90
91 public void visitNode(Node<N, E> n) {
92 }
93
94 public boolean visitEdge(Edge<N, E> e, boolean backEdge) {
95 return true;
96 }
97 }
98
99 public class BFSTraversalVisitor {
100
101 public void visitNode(Node<N, E> n, int depth) {
102 }
103 }
104
105 public List<Node<N, E>> getNodesWithInDegree(int x) {
106 return getNodesWithInDegree(x, true);
107 }
108
109 public List<Node<N, E>> getNodesWithInDegree(int x, boolean countSelfLoops) {
110
111 List<Node<N, E>> result = new ArrayList<>();
112 for (Node<N, E> n : getNodes()) {
113 if (n.getInDegree(countSelfLoops) == x) {
114 result.add(n);
115 }
116 }
117
118 return result;
119
120 }
121
122 private void markReachable(Node<N, E> startingNode) {
123 ArrayList<Node<N, E>> arr = new ArrayList<>();
124 arr.add(startingNode);
125 for (Node<N, E> n : getNodes()) {
126 n.setReachable(false);
127 }
128 traverseDFS(arr, new DFSTraversalVisitor() {
129
130 @Override
131 public void visitNode(Node<N, E> n) {
132 n.setReachable(true);
133 }
134 });
135 }
136
137 public void traverseBFS(Node<N, E> startingNode, BFSTraversalVisitor tv, boolean longestPath) {
138
139 if (longestPath) {
140 markReachable(startingNode);
141 }
142
143 for (Node<N, E> n : getNodes()) {
144 n.setVisited(false);
145 n.setActive(false);
146 }
147
148 Queue<Node<N, E>> queue = new LinkedList<>();
149 queue.add(startingNode);
150 startingNode.setVisited(true);
151 int layer = 0;
152 Node<N, E> lastOfLayer = startingNode;
153 Node<N, E> lastAdded = null;
154
155 while (!queue.isEmpty()) {
156
157 Node<N, E> current = queue.poll();
158 tv.visitNode(current, layer);
159 current.setActive(false);
160
161
162 for (Edge<N, E> e : current.getOutEdges()) {
163 if (!e.getDest().isVisited()) {
164
165 boolean allow = true;
166 if (longestPath) {
167 for (Node<N, E> pred : e.getDest().getPredecessors()) {
168 if ((!pred.isVisited() || pred.isActive()) && pred.isReachable()) {
169 allow = false;
170 break;
171 }
172 }
173 }
174
175 if (allow) {
176 queue.offer(e.getDest());
177 lastAdded = e.getDest();
178 e.getDest().setVisited(true);
179 e.getDest().setActive(true);
180 }
181 }
182 }
183
184 if (current == lastOfLayer && !queue.isEmpty()) {
185 lastOfLayer = lastAdded;
186 layer++;
187 }
188 }
189 }
190
191 public void traverseDFS(DFSTraversalVisitor tv) {
192 traverseDFS(getNodes(), tv);
193 }
194
195 public void traverseDFS(Collection<Node<N, E>> startingNodes, DFSTraversalVisitor tv) {
196
197 for (Node<N, E> n : getNodes()) {
198 n.setVisited(false);
199 n.setActive(false);
200 }
201
202 boolean result = false;
203 for (Node<N, E> n : startingNodes) {
204 traverse(tv, n);
205 }
206 }
207
208 private void traverse(DFSTraversalVisitor tv, Node<N, E> n) {
209
210 if (!n.isVisited()) {
211 n.setVisited(true);
212 n.setActive(true);
213 tv.visitNode(n);
214
215 for (Edge<N, E> e : n.getOutEdges()) {
216
217 Node<N, E> next = e.getDest();
218 if (next.isActive()) {
219 tv.visitEdge(e, true);
220 } else {
221 if (tv.visitEdge(e, false)) {
222 traverse(tv, next);
223 }
224 }
225 }
226
227 n.setActive(false);
228 }
229
230 }
231
232 public boolean hasCycles() {
233
234 for (Node<N, E> n : getNodes()) {
235 n.setVisited(false);
236 n.setActive(false);
237 }
238
239 boolean result = false;
240 for (Node<N, E> n : getNodes()) {
241 result |= checkCycles(n);
242 if (result) {
243 break;
244 }
245 }
246 return result;
247 }
248
249 private boolean checkCycles(Node<N, E> n) {
250
251 if (n.isActive()) {
252 return true;
253 }
254
255 if (!n.isVisited()) {
256
257 n.setVisited(true);
258 n.setActive(true);
259
260 for (Node<N, E> succ : n.getSuccessors()) {
261 if (checkCycles(succ)) {
262 return true;
263 }
264 }
265
266 n.setActive(false);
267
268 }
269
270 return false;
271 }
272
273 @Override
274 public String toString() {
275
276 StringBuilder s = new StringBuilder();
277 s.append("Nodes: ");
278 for (Node<N, E> n : getNodes()) {
279 s.append(n.toString());
280 s.append("\n");
281 }
282
283 s.append("Edges: ");
284
285 for (Edge<N, E> e : getEdges()) {
286 s.append(e.toString());
287 s.append("\n");
288 }
289
290 return s.toString();
291 }
292 }