Mercurial > hg > truffle

annotate visualizer/Layout/src/com/sun/hotspot/igv/layout/LayoutGraph.java @ 4680:acf7d88327fa

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Fixed two asserts in the implicit div exception handling for Windows that are not valid for Graal (as it deoptimizes to some place before the div instead of exactly to the div bytecode).
author Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
date Thu, 23 Feb 2012 23:06:28 +0100
parents 015fb895586b
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
4512
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
1 /*
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
2 * Copyright (c) 2008, Oracle and/or its affiliates. All rights reserved.
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
4 *
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
5 * This code is free software; you can redistribute it and/or modify it
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
6 * under the terms of the GNU General Public License version 2 only, as
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
7 * published by the Free Software Foundation.
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
8 *
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
9 * This code is distributed in the hope that it will be useful, but WITHOUT
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
12 * version 2 for more details (a copy is included in the LICENSE file that
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
13 * accompanied this code).
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
14 *
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
15 * You should have received a copy of the GNU General Public License version
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
16 * 2 along with this work; if not, write to the Free Software Foundation,
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
18 *
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
20 * or visit www.oracle.com if you need additional information or have any
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
21 * questions.
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
22 *
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
23 */
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
24 package com.sun.hotspot.igv.layout;
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
25
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
26 import java.util.*;
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
27
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
28 /**
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
29 *
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
30 * @author Thomas Wuerthinger
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
31 */
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
32 public class LayoutGraph {
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
33
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
34 private Set<? extends Link> links;
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
35 private SortedSet<Vertex> vertices;
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
36 private HashMap<Vertex, Set<Port>> inputPorts;
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
37 private HashMap<Vertex, Set<Port>> outputPorts;
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
38 private HashMap<Port, Set<Link>> portLinks;
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
39
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
40 public LayoutGraph(Set<? extends Link> links) {
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
41 this(links, new HashSet<Vertex>());
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
42 }
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
43
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
44 public LayoutGraph(Set<? extends Link> links, Set<? extends Vertex> additionalVertices) {
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
45 this.links = links;
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
46 assert verify();
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
47
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
48 vertices = new TreeSet<>();
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
49 portLinks = new HashMap<>(links.size());
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
50 inputPorts = new HashMap<>(links.size());
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
51 outputPorts = new HashMap<>(links.size());
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
52
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
53 for (Link l : links) {
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
54 Port p = l.getFrom();
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
55 Port p2 = l.getTo();
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
56 Vertex v1 = p.getVertex();
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
57 Vertex v2 = p2.getVertex();
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
58
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
59 if (!vertices.contains(v1)) {
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
60
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
61 outputPorts.put(v1, new HashSet<Port>(1));
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
62 inputPorts.put(v1, new HashSet<Port>(3));
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
63 vertices.add(v1);
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
64 assert vertices.contains(v1);
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
65 }
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
66
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
67 if (!vertices.contains(v2)) {
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
68 vertices.add(v2);
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
69 assert vertices.contains(v2);
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
70 outputPorts.put(v2, new HashSet<Port>(1));
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
71 inputPorts.put(v2, new HashSet<Port>(3));
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
72 }
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
73
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
74 if (!portLinks.containsKey(p)) {
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
75 HashSet<Link> hashSet = new HashSet<>(3);
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
76 portLinks.put(p, hashSet);
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
77 }
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
78
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
79 if (!portLinks.containsKey(p2)) {
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
80 portLinks.put(p2, new HashSet<Link>(3));
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
81 }
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
82
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
83 outputPorts.get(v1).add(p);
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
84 inputPorts.get(v2).add(p2);
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
85
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
86 portLinks.get(p).add(l);
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
87 portLinks.get(p2).add(l);
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
88 }
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
89
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
90 for (Vertex v : additionalVertices) {
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
91 if (!vertices.contains(v)) {
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
92 outputPorts.put(v, new HashSet<Port>(1));
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
93 inputPorts.put(v, new HashSet<Port>(3));
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
94 vertices.add(v);
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
95 vertices.contains(v);
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
96 }
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
97 }
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
98 }
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
99
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
100 public Set<Port> getInputPorts(Vertex v) {
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
101 return this.inputPorts.get(v);
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
102 }
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
103
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
104 public Set<Port> getOutputPorts(Vertex v) {
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
105 return this.outputPorts.get(v);
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
106 }
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
107
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
108 public Set<Link> getPortLinks(Port p) {
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
109 return portLinks.get(p);
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
110 }
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
111
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
112 public Set<? extends Link> getLinks() {
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
113 return links;
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
114 }
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
115
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
116 public boolean verify() {
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
117 return true;
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
118 }
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
119
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
120 public SortedSet<Vertex> getVertices() {
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
121 return vertices;
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
122 }
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
123
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
124 private void markNotRoot(Set<Vertex> notRootSet, Vertex v, Vertex startingVertex) {
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
125
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
126 if (notRootSet.contains(v)) {
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
127 return;
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
128 }
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
129 if (v != startingVertex) {
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
130 notRootSet.add(v);
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
131 }
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
132 Set<Port> outPorts = getOutputPorts(v);
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
133 for (Port p : outPorts) {
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
134 Set<Link> portLinks = getPortLinks(p);
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
135 for (Link l : portLinks) {
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
136 Port other = l.getTo();
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
137 Vertex otherVertex = other.getVertex();
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
138 if (otherVertex != startingVertex) {
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
139 markNotRoot(notRootSet, otherVertex, startingVertex);
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
140 }
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
141 }
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
142 }
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
143 }
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
144
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
145 // Returns a set of vertices with the following properties:
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
146 // - All Vertices in the set startingRoots are elements of the set.
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
147 // - When starting a DFS at every vertex in the set, every vertex of the
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
148 // whole graph is visited.
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
149 public Set<Vertex> findRootVertices(Set<Vertex> startingRoots) {
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
150
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
151 Set<Vertex> notRootSet = new HashSet<>();
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
152 for (Vertex v : startingRoots) {
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
153 if (!notRootSet.contains(v)) {
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
154 markNotRoot(notRootSet, v, v);
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
155 }
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
156 }
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
157
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
158 Set<Vertex> tmpVertices = getVertices();
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
159 for (Vertex v : tmpVertices) {
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
160 if (!notRootSet.contains(v)) {
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
161 if (this.getInputPorts(v).size() == 0) {
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
162 markNotRoot(notRootSet, v, v);
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
163 }
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
164 }
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
165 }
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
166
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
167 for (Vertex v : tmpVertices) {
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
168 if (!notRootSet.contains(v)) {
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
169 markNotRoot(notRootSet, v, v);
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
170 }
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
171 }
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
172
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
173 Set<Vertex> result = new HashSet<>();
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
174 for (Vertex v : tmpVertices) {
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
175 if (!notRootSet.contains(v)) {
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
176 result.add(v);
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
177 }
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
178 }
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
179 assert tmpVertices.size() == 0 || result.size() > 0;
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
180 return result;
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
181 }
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
182
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
183 public Set<Vertex> findRootVertices() {
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
184 return findRootVertices(new HashSet<Vertex>());
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
185 }
015fb895586b Moved visualizer to new directory.
Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
parents:
diff changeset
186 }