truffle: visualizer/Layout/src/com/sun/hotspot/igv/layout/LayoutGraph.java annotate

author	Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
date	Tue, 07 Feb 2012 22:41:09 +0100
parents
children

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 }

4512

015fb895586b Moved visualizer to new directory.