Mercurial > hg > truffle

comparison visualizer/Layout/src/com/sun/hotspot/igv/layout/LayoutGraph.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.layout;
25
26 import java.util.*;
27
28 /**
29 *
30 * @author Thomas Wuerthinger
31 */
32 public class LayoutGraph {
33
34 private Set<? extends Link> links;
35 private SortedSet<Vertex> vertices;
36 private HashMap<Vertex, Set<Port>> inputPorts;
37 private HashMap<Vertex, Set<Port>> outputPorts;
38 private HashMap<Port, Set<Link>> portLinks;
39
40 public LayoutGraph(Set<? extends Link> links) {
41 this(links, new HashSet<Vertex>());
42 }
43
44 public LayoutGraph(Set<? extends Link> links, Set<? extends Vertex> additionalVertices) {
45 this.links = links;
46 assert verify();
47
48 vertices = new TreeSet<>();
49 portLinks = new HashMap<>(links.size());
50 inputPorts = new HashMap<>(links.size());
51 outputPorts = new HashMap<>(links.size());
52
53 for (Link l : links) {
54 Port p = l.getFrom();
55 Port p2 = l.getTo();
56 Vertex v1 = p.getVertex();
57 Vertex v2 = p2.getVertex();
58
59 if (!vertices.contains(v1)) {
60
61 outputPorts.put(v1, new HashSet<Port>(1));
62 inputPorts.put(v1, new HashSet<Port>(3));
63 vertices.add(v1);
64 assert vertices.contains(v1);
65 }
66
67 if (!vertices.contains(v2)) {
68 vertices.add(v2);
69 assert vertices.contains(v2);
70 outputPorts.put(v2, new HashSet<Port>(1));
71 inputPorts.put(v2, new HashSet<Port>(3));
72 }
73
74 if (!portLinks.containsKey(p)) {
75 HashSet<Link> hashSet = new HashSet<>(3);
76 portLinks.put(p, hashSet);
77 }
78
79 if (!portLinks.containsKey(p2)) {
80 portLinks.put(p2, new HashSet<Link>(3));
81 }
82
83 outputPorts.get(v1).add(p);
84 inputPorts.get(v2).add(p2);
85
86 portLinks.get(p).add(l);
87 portLinks.get(p2).add(l);
88 }
89
90 for (Vertex v : additionalVertices) {
91 if (!vertices.contains(v)) {
92 outputPorts.put(v, new HashSet<Port>(1));
93 inputPorts.put(v, new HashSet<Port>(3));
94 vertices.add(v);
95 vertices.contains(v);
96 }
97 }
98 }
99
100 public Set<Port> getInputPorts(Vertex v) {
101 return this.inputPorts.get(v);
102 }
103
104 public Set<Port> getOutputPorts(Vertex v) {
105 return this.outputPorts.get(v);
106 }
107
108 public Set<Link> getPortLinks(Port p) {
109 return portLinks.get(p);
110 }
111
112 public Set<? extends Link> getLinks() {
113 return links;
114 }
115
116 public boolean verify() {
117 return true;
118 }
119
120 public SortedSet<Vertex> getVertices() {
121 return vertices;
122 }
123
124 private void markNotRoot(Set<Vertex> notRootSet, Vertex v, Vertex startingVertex) {
125
126 if (notRootSet.contains(v)) {
127 return;
128 }
129 if (v != startingVertex) {
130 notRootSet.add(v);
131 }
132 Set<Port> outPorts = getOutputPorts(v);
133 for (Port p : outPorts) {
134 Set<Link> portLinks = getPortLinks(p);
135 for (Link l : portLinks) {
136 Port other = l.getTo();
137 Vertex otherVertex = other.getVertex();
138 if (otherVertex != startingVertex) {
139 markNotRoot(notRootSet, otherVertex, startingVertex);
140 }
141 }
142 }
143 }
144
145 // Returns a set of vertices with the following properties:
146 // - All Vertices in the set startingRoots are elements of the set.
147 // - When starting a DFS at every vertex in the set, every vertex of the
148 // whole graph is visited.
149 public Set<Vertex> findRootVertices(Set<Vertex> startingRoots) {
150
151 Set<Vertex> notRootSet = new HashSet<>();
152 for (Vertex v : startingRoots) {
153 if (!notRootSet.contains(v)) {
154 markNotRoot(notRootSet, v, v);
155 }
156 }
157
158 Set<Vertex> tmpVertices = getVertices();
159 for (Vertex v : tmpVertices) {
160 if (!notRootSet.contains(v)) {
161 if (this.getInputPorts(v).size() == 0) {
162 markNotRoot(notRootSet, v, v);
163 }
164 }
165 }
166
167 for (Vertex v : tmpVertices) {
168 if (!notRootSet.contains(v)) {
169 markNotRoot(notRootSet, v, v);
170 }
171 }
172
173 Set<Vertex> result = new HashSet<>();
174 for (Vertex v : tmpVertices) {
175 if (!notRootSet.contains(v)) {
176 result.add(v);
177 }
178 }
179 assert tmpVertices.size() == 0 || result.size() > 0;
180 return result;
181 }
182
183 public Set<Vertex> findRootVertices() {
184 return findRootVertices(new HashSet<Vertex>());
185 }
186 }