projects/dwt-addons: dwtx/draw2d/graph/CompoundBreakCycles.d annotate

author	Frank Benoit <benoit@tionex.de>
date	Sun, 03 Aug 2008 00:52:14 +0200
parents
children

rev	line source
98 95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	1 /*******************************************************************************
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	2 * Copyright (c) 2003, 2005 IBM Corporation and others.
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	3 * All rights reserved. This program and the accompanying materials
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	4 * are made available under the terms of the Eclipse Public License v1.0
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	5 * which accompanies this distribution, and is available at
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	6 * http://www.eclipse.org/legal/epl-v10.html
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	7 *
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	8 * Contributors:
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	9 * IBM Corporation - initial API and implementation
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	10 * Port to the D programming language:
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	11 * Frank Benoit <benoit@tionex.de>
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	12 *******************************************************************************/
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	13 module dwtx.draw2d.graph.CompoundBreakCycles;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	14
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	15 import dwt.dwthelper.utils;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	16 import dwtx.draw2d.graph.GraphVisitor;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	17 import dwtx.draw2d.graph.NodeList;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	18 import dwtx.draw2d.graph.Node;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	19 import dwtx.draw2d.graph.DirectedGraph;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	20 import dwtx.draw2d.graph.Subgraph;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	21 import dwtx.draw2d.graph.Edge;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	22
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	23
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	24 /**
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	25 * This visitor eliminates cycles in the graph via a modified implementation of the
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	26 * greedy cycle removal algorithm for directed graphs. The algorithm has been modified to
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	27 * handle the presence of Subgraphs and compound cycles which may result. This algorithm
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	28 * determines a set of edges which can be inverted and result in a graph without compound
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	29 * cycles.
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	30 *
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	31 * @author Daniel Lee
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	32 * @author Randy Hudson
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	33 * @since 2.1.2
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	34 */
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	35 class CompoundBreakCycles : GraphVisitor {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	36
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	37 /*
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	38 * Caches all nodes in the graph. Used in identifying cycles and in cycle removal.
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	39 * Flag field indicates "presence". If true, the node has been removed from the list.
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	40 */
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	41 private NodeList graphNodes;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	42 private NodeList sL;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	43
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	44 public this(){
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	45 sL = new NodeList();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	46 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	47
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	48 private bool allFlagged(NodeList nodes) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	49 for (int i = 0; i < nodes.size(); i++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	50 if (nodes.getNode(i).flag is false)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	51 return false;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	52 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	53 return true;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	54 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	55
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	56 private int buildNestingTreeIndices(NodeList nodes, int base) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	57 for (int i = 0; i < nodes.size(); i++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	58 Node node = cast(Node)nodes.get(i);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	59 if (auto s = cast(Subgraph) node ) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	60 s.nestingTreeMin = base;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	61 base = buildNestingTreeIndices(s.members, base);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	62 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	63 node.nestingIndex = base++;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	64 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	65 return base++;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	66 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	67
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	68 private bool canBeRemoved(Node n) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	69 return !n.flag && getChildCount(n) is 0;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	70 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	71
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	72 private bool changeInDegree(Node n, int delta) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	73 return (n.workingInts[1] += delta) is 0;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	74 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	75
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	76 private bool changeOutDegree(Node n, int delta) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	77 return (n.workingInts[2] += delta) is 0;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	78 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	79
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	80 /*
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	81 * Execution of the modified greedy cycle removal algorithm.
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	82 */
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	83 private void cycleRemove(NodeList children) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	84 NodeList sR = new NodeList();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	85 do {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	86 findSinks(children, sR);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	87 findSources(children);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	88
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	89 // all sinks and sources added, find node with highest
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	90 // outDegree - inDegree
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	91 Node max = findNodeWithMaxDegree(children);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	92 if (max !is null) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	93 for (int i = 0; i < children.size(); i++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	94 Node child = cast(Node)children.get(i);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	95 if (child.flag)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	96 continue;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	97 if (child is max)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	98 restoreSinks(max, sR);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	99 else
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	100 restoreSources(child);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	101 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	102 remove(max);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	103 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	104 } while (!allFlagged(children));
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	105 while (!sR.isEmpty())
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	106 sL.add(sR.remove(sR.size() - 1));
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	107 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	108
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	109 private void findInitialSinks(NodeList children, NodeList sinks) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	110 for (int i = 0; i < children.size(); i++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	111 Node node = children.getNode(i);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	112 if (node.flag)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	113 continue;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	114 if (isSink(node) && canBeRemoved(node)) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	115 sinks.add(node);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	116 node.flag = true;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	117 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	118 if (null !is cast(Subgraph)node )
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	119 findInitialSinks((cast(Subgraph)node).members, sinks);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	120 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	121 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	122
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	123 private void findInitialSources(NodeList children, NodeList sources) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	124 for (int i = 0; i < children.size(); i++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	125 Node node = children.getNode(i);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	126 if (isSource(node) && canBeRemoved(node)) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	127 sources.add(node);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	128 node.flag = true;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	129 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	130 if (null !is cast(Subgraph)node )
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	131 findInitialSources((cast(Subgraph)node).members, sources);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	132 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	133 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	134
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	135 private Node findNodeWithMaxDegree(NodeList nodes) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	136 int max = Integer.MIN_VALUE;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	137 Node maxNode = null;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	138
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	139 for (int i = 0; i < nodes.size(); i++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	140 Node node = nodes.getNode(i);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	141 if (node.flag)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	142 continue;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	143 int degree = getNestedOutDegree(node) - getNestedInDegree(node);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	144 if (degree >= max && node.flag is false) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	145 max = degree;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	146 maxNode = node;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	147 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	148 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	149 return maxNode;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	150 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	151
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	152 /*
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	153 * Finds all sinks in graphNodes and adds them to the passed NodeList
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	154 */
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	155 private void findSinks(NodeList children, NodeList rightList) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	156 // NodeList rightList = new NodeList();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	157 NodeList sinks = new NodeList();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	158 findInitialSinks(children, sinks);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	159 while (!sinks.isEmpty()) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	160 Node sink = sinks.getNode(sinks.size() - 1);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	161 rightList.add(sink);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	162 sinks.remove(sink);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	163 removeSink(sink, sinks);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	164
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	165 // Check to see if the removal has made the parent node a sink
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	166 if (sink.getParent() !is null) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	167 Node parent = sink.getParent();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	168 setChildCount(parent, getChildCount(parent) - 1);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	169 if (isSink(parent) && canBeRemoved(parent)) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	170 sinks.add(parent);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	171 parent.flag = true;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	172 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	173 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	174 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	175 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	176
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	177 /*
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	178 * Finds all sources in graphNodes and adds them to the sL NodeList.
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	179 */
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	180 private void findSources(NodeList children) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	181 NodeList sources = new NodeList();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	182 findInitialSources(children, sources);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	183 while (!sources.isEmpty()) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	184 Node source = sources.getNode(sources.size() - 1);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	185 sL.add(source);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	186 sources.remove(source);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	187 removeSource(source, sources);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	188
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	189 // Check to see if the removal has made the parent node a source
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	190 if (source.getParent() !is null) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	191 Node parent = source.getParent();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	192 setChildCount(parent, getChildCount(parent) - 1);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	193 if (isSource(parent) && canBeRemoved(parent)) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	194 sources.add(parent);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	195 parent.flag = true;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	196 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	197 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	198 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	199 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	200
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	201 private int getChildCount(Node n) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	202 return n.workingInts[3];
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	203 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	204
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	205 private int getInDegree(Node n) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	206 return n.workingInts[1];
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	207 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	208
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	209 private int getNestedInDegree(Node n) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	210 int result = getInDegree(n);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	211 if ( auto s = cast(Subgraph)n ) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	212 for (int i = 0; i < s.members.size(); i++)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	213 if (!s.members.getNode(i).flag)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	214 result += getInDegree(s.members.getNode(i));
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	215 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	216 return result;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	217 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	218
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	219 private int getNestedOutDegree(Node n) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	220 int result = getOutDegree(n);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	221 if ( auto s = cast(Subgraph)n ) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	222 for (int i = 0; i < s.members.size(); i++)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	223 if (!s.members.getNode(i).flag)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	224 result += getOutDegree(s.members.getNode(i));
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	225 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	226 return result;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	227 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	228
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	229 private int getOrderIndex(Node n) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	230 return n.workingInts[0];
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	231 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	232
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	233 private int getOutDegree(Node n) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	234 return n.workingInts[2];
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	235 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	236
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	237 private void initializeDegrees(DirectedGraph g) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	238 g.nodes.resetFlags();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	239 g.edges.resetFlags(false);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	240 for (int i = 0; i < g.nodes.size(); i++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	241 Node n = g.nodes.getNode(i);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	242 setInDegree(n, n.incoming.size());
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	243 setOutDegree(n, n.outgoing.size());
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	244 if ( auto s = cast(Subgraph)n )
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	245 setChildCount(n, s.members.size());
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	246 else
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	247 setChildCount(n, 0);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	248 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	249 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	250
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	251 private void invertEdges(DirectedGraph g) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	252 // Assign order indices
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	253 int orderIndex = 0;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	254 for (int i = 0; i < sL.size(); i++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	255 setOrderIndex(sL.getNode(i), orderIndex++);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	256 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	257 // Invert edges that are causing a cycle
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	258 for (int i = 0; i < g.edges.size(); i++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	259 Edge e = g.edges.getEdge(i);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	260 if (getOrderIndex(e.source) > getOrderIndex(e.target)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	261 && !e.source.isNested(e.target)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	262 && !e.target.isNested(e.source)) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	263 e.invert();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	264 e.isFeedback_ = true;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	265 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	266 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	267 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	268
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	269 /**
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	270 * Removes all edges connecting the given subgraph to other nodes outside of it.
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	271 * @param s
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	272 * @param n
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	273 */
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	274 private void isolateSubgraph(Subgraph subgraph, Node member) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	275 Edge edge = null;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	276 for (int i = 0; i < member.incoming.size(); i++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	277 edge = member.incoming.getEdge(i);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	278 if (!subgraph.isNested(edge.source) && !edge.flag)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	279 removeEdge(edge);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	280 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	281 for (int i = 0; i < member.outgoing.size(); i++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	282 edge = member.outgoing.getEdge(i);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	283 if (!subgraph.isNested(edge.target) && !edge.flag)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	284 removeEdge(edge);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	285 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	286 if ( auto s = cast(Subgraph)member ) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	287 NodeList members = s.members;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	288 for (int i = 0; i < members.size(); i++)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	289 isolateSubgraph(subgraph, members.getNode(i));
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	290 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	291 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	292
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	293 private bool isSink(Node n) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	294 return getOutDegree(n) is 0
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	295 && (n.getParent() is null
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	296 \|\| isSink(n.getParent()));
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	297 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	298
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	299 private bool isSource(Node n) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	300 return getInDegree(n) is 0
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	301 && (n.getParent() is null
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	302 \|\| isSource(n.getParent()));
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	303 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	304
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	305 private void remove(Node n) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	306 n.flag = true;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	307 if (n.getParent() !is null)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	308 setChildCount(n.getParent(), getChildCount(n.getParent()) - 1);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	309 removeSink(n, null);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	310 removeSource(n, null);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	311 sL.add(n);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	312 if ( auto s = cast(Subgraph)n ) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	313 isolateSubgraph(s, s);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	314 cycleRemove(s.members);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	315 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	316 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	317
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	318 private bool removeEdge(Edge e) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	319 if (e.flag)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	320 return false;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	321 e.flag = true;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	322 changeOutDegree(e.source, -1);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	323 changeInDegree(e.target, -1);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	324 return true;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	325 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	326
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	327 /**
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	328 * Removes all edges between a parent and any of its children or descendants.
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	329 */
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	330 private void removeParentChildEdges(DirectedGraph g) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	331 for (int i = 0; i < g.edges.size(); i++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	332 Edge e = g.edges.getEdge(i);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	333 if (e.source.isNested(e.target) \|\| e.target.isNested(e.source))
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	334 removeEdge(e);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	335 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	336 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	337
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	338 private void removeSink(Node sink, NodeList allSinks) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	339 for (int i = 0; i < sink.incoming.size(); i++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	340 Edge e = sink.incoming.getEdge(i);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	341 if (!e.flag) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	342 removeEdge(e);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	343 Node source = e.source;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	344 if (allSinks !is null && isSink(source) && canBeRemoved(source)) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	345 allSinks.add(source);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	346 source.flag = true;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	347 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	348 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	349 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	350 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	351
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	352 private void removeSource(Node n, NodeList allSources) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	353 for (int i = 0; i < n.outgoing.size(); i++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	354 Edge e = n.outgoing.getEdge(i);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	355 if (!e.flag) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	356 e.flag = true;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	357 changeInDegree(e.target, -1);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	358 changeOutDegree(e.source, -1);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	359
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	360 Node target = e.target;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	361 if (allSources !is null && isSource(target) && canBeRemoved(target)) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	362 allSources.add(target);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	363 target.flag = true;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	364 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	365 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	366 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	367 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	368
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	369 /**
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	370 * Restores an edge if it has been removed, and both of its nodes are not removed.
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	371 * @param e the edge
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	372 * @return <code>true</code> if the edge was restored
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	373 */
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	374 private bool restoreEdge(Edge e) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	375 if (!e.flag \|\| e.source.flag \|\| e.target.flag)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	376 return false;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	377 e.flag = false;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	378 changeOutDegree(e.source, 1);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	379 changeInDegree(e.target, 1);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	380 return true;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	381 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	382
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	383 /**
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	384 * Brings back all nodes nested in the given node.
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	385 * @param node the node to restore
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	386 * @param sr current sinks
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	387 */
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	388 private void restoreSinks(Node node, NodeList sR) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	389 if (node.flag && sR.contains(node)) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	390 node.flag = false;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	391 if (node.getParent() !is null)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	392 setChildCount(node.getParent(), getChildCount(node.getParent()) + 1);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	393 sR.remove(node);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	394 for (int i = 0; i < node.incoming.size(); i++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	395 Edge e = node.incoming.getEdge(i);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	396 restoreEdge(e);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	397 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	398 for (int i = 0; i < node.outgoing.size(); i++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	399 Edge e = node.outgoing.getEdge(i);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	400 restoreEdge(e);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	401 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	402 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	403 if ( auto s = cast(Subgraph)node ) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	404 for (int i = 0; i < s.members.size(); i++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	405 Node member = s.members.getNode(i);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	406 restoreSinks(member, sR);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	407 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	408 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	409 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	410
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	411 /**
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	412 * Brings back all nodes nested in the given node.
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	413 * @param node the node to restore
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	414 * @param sr current sinks
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	415 */
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	416 private void restoreSources(Node node) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	417 if (node.flag && sL.contains(node)) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	418 node.flag = false;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	419 if (node.getParent() !is null)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	420 setChildCount(node.getParent(), getChildCount(node.getParent()) + 1);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	421 sL.remove(node);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	422 for (int i = 0; i < node.incoming.size(); i++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	423 Edge e = node.incoming.getEdge(i);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	424 restoreEdge(e);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	425 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	426 for (int i = 0; i < node.outgoing.size(); i++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	427 Edge e = node.outgoing.getEdge(i);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	428 restoreEdge(e);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	429 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	430 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	431 if ( auto s = cast(Subgraph)node ) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	432 for (int i = 0; i < s.members.size(); i++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	433 Node member = s.members.getNode(i);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	434 restoreSources(member);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	435 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	436 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	437 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	438
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	439 public void revisit(DirectedGraph g) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	440 for (int i = 0; i < g.edges.size(); i++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	441 Edge e = g.edges.getEdge(i);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	442 if (e.isFeedback())
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	443 e.invert();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	444 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	445 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	446
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	447 private void setChildCount(Node n, int count) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	448 n.workingInts[3] = count;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	449 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	450
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	451 private void setInDegree(Node n, int deg) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	452 n.workingInts[1] = deg;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	453 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	454
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	455 private void setOrderIndex(Node n, int index) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	456 n.workingInts[0] = index;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	457 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	458
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	459 private void setOutDegree(Node n, int deg) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	460 n.workingInts[2] = deg;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	461 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	462
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	463 /**
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	464 * @see GraphVisitor#visit(dwtx.draw2d.graph.DirectedGraph)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	465 */
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	466 public void visit(DirectedGraph g) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	467 initializeDegrees(g);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	468 graphNodes = g.nodes;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	469
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	470 NodeList roots = new NodeList();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	471 for (int i = 0; i < graphNodes.size(); i++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	472 if (graphNodes.getNode(i).getParent() is null)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	473 roots.add(graphNodes.getNode(i));
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	474 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	475 buildNestingTreeIndices(roots, 0);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	476 removeParentChildEdges(g);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	477 cycleRemove(roots);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	478 invertEdges(g);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	479 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	480
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	481 }

98

95307ad235d9 Added Draw2d code, still work in progress