1 /* 2 * Copyright (c) 2008, 2015, 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 LayoutGraph(Set<? extends Link> links)40 public LayoutGraph(Set<? extends Link> links) { 41 this(links, new HashSet<Vertex>()); 42 } 43 LayoutGraph(Set<? extends Link> links, Set<? extends Vertex> additionalVertices)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 getInputPorts(Vertex v)100 public Set<Port> getInputPorts(Vertex v) { 101 return this.inputPorts.get(v); 102 } 103 getOutputPorts(Vertex v)104 public Set<Port> getOutputPorts(Vertex v) { 105 return this.outputPorts.get(v); 106 } 107 getPortLinks(Port p)108 public Set<Link> getPortLinks(Port p) { 109 return portLinks.get(p); 110 } 111 getLinks()112 public Set<? extends Link> getLinks() { 113 return links; 114 } 115 verify()116 public boolean verify() { 117 return true; 118 } 119 getVertices()120 public SortedSet<Vertex> getVertices() { 121 return vertices; 122 } 123 markNotRoot(Set<Vertex> notRootSet, Vertex v, Vertex startingVertex)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. findRootVertices(Set<Vertex> startingRoots)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 findRootVertices()183 public Set<Vertex> findRootVertices() { 184 return findRootVertices(new HashSet<Vertex>()); 185 } 186 getClusters()187 public SortedSet<Cluster> getClusters() { 188 189 SortedSet<Cluster> clusters = new TreeSet<Cluster>(); 190 for (Vertex v : getVertices()) { 191 if (v.getCluster() != null) { 192 clusters.add(v.getCluster()); 193 } 194 } 195 196 return clusters; 197 } 198 } 199