projects/dwt-addons: dwtx/draw2d/graph/BreakCycles.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.BreakCycles;
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.dwtxhelper.Collection;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	17 import dwtx.draw2d.graph.GraphVisitor;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	18 import dwtx.draw2d.graph.NodeList;
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.Node;
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 * This visitor eliminates cycles in the graph using a "greedy" heuristic. Nodes which
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	25 * are sources and sinks are marked and placed in a source and sink list, leaving only
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	26 * nodes involved in cycles. A remaining node with the highest (outgoing-incoming) edges
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	27 * score is then chosen greedily as if it were a source. The process is repeated until all
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	28 * nodes have been marked and placed in a list. The lists are then concatenated, and any
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	29 * edges which go backwards in this list will be inverted during the layout procedure.
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 * @since 2.1.2
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	33 */
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	34 class BreakCycles : GraphVisitor {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	35
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	36 // Used in identifying cycles and in cycle removal.
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	37 // 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	38 NodeList graphNodes;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	39
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	40 public this(){
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	41 graphNodes = new NodeList();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	42 }
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 private bool allNodesFlagged() {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	45 for (int i = 0; i < graphNodes.size(); i++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	46 if (graphNodes.getNode(i).flag is false)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	47 return false;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	48 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	49 return true;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	50 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	51
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	52 private void breakCycles(DirectedGraph g) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	53 initializeDegrees(g);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	54 greedyCycleRemove(g);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	55 invertEdges(g);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	56 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	57
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	58 /*
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	59 * Returns true if g contains cycles, false otherwise
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	60 */
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	61 private bool containsCycles(DirectedGraph g) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	62 List noLefts = new ArrayList();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	63 //Identify all initial nodes for removal
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	64 for (int i = 0; i < graphNodes.size(); i++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	65 Node node = graphNodes.getNode(i);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	66 if (getIncomingCount(node) is 0)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	67 sortedInsert(noLefts, node);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	68 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	69
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	70 while (noLefts.size() > 0) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	71 Node node = cast(Node)noLefts.remove(noLefts.size() - 1);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	72 node.flag = true;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	73 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	74 Node right = node.outgoing.getEdge(i).target;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	75 setIncomingCount(right, getIncomingCount(right) - 1);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	76 if (getIncomingCount(right) is 0)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	77 sortedInsert(noLefts, right);
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 if (allNodesFlagged())
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	82 return false;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	83 return true;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	84 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	85
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	86 /*
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	87 * Returns the node in graphNodes with the largest
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	88 * (outgoing edge count - incoming edge count) value
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	89 */
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	90 private Node findNodeWithMaxDegree() {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	91 int max = Integer.MIN_VALUE;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	92 Node maxNode = null;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	93
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	94 for (int i = 0; i < graphNodes.size(); i++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	95 Node node = graphNodes.getNode(i);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	96 if (getDegree(node) >= max && node.flag is false) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	97 max = getDegree(node);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	98 maxNode = node;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	99 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	100 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	101 return maxNode;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	102 }
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 private int getDegree(Node n) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	105 return n.workingInts[3];
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	106 }
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 private int getIncomingCount(Node n) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	109 return n.workingInts[0];
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	110 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	111
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	112 private int getInDegree(Node n) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	113 return n.workingInts[1];
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	114 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	115
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	116 private int getOrderIndex(Node n) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	117 return n.workingInts[0];
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	118 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	119
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	120 private int getOutDegree(Node n) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	121 return n.workingInts[2];
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
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	124 private void greedyCycleRemove(DirectedGraph g) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	125 NodeList sL = new NodeList();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	126 NodeList sR = new NodeList();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	127
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	128 do {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	129 // Add all sinks and isolated nodes to sR
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	130 bool hasSink;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	131 do {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	132 hasSink = false;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	133 for (int i = 0; i < graphNodes.size(); i++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	134 Node node = graphNodes.getNode(i);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	135 if (getOutDegree(node) is 0 && node.flag is false) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	136 hasSink = true;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	137 node.flag = true;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	138 updateIncoming(node);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	139 sR.add(node);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	140 break;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	141 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	142 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	143 } while (hasSink);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	144
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	145 // Add all sources to sL
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	146 bool hasSource;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	147 do {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	148 hasSource = false;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	149 for (int i = 0; i < graphNodes.size(); i++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	150 Node node = graphNodes.getNode(i);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	151 if (getInDegree(node) is 0 && node.flag is false) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	152 hasSource = true;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	153 node.flag = true;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	154 updateOutgoing(node);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	155 sL.add(node);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	156 break;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	157 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	158 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	159 } while (hasSource);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	160
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	161 // When all sinks and sources are removed, choose a node with the
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	162 // maximum degree (outDegree - inDegree) and add it to sL
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	163 Node max = findNodeWithMaxDegree();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	164 if (max !is null) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	165 sL.add(max);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	166 max.flag = true;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	167 updateIncoming(max);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	168 updateOutgoing(max);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	169 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	170 } while (!allNodesFlagged());
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	171
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	172 // Assign order indexes
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	173 int orderIndex = 0;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	174 for (int i = 0; i < sL.size(); i++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	175 setOrderIndex(sL.getNode(i), orderIndex++);
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 for (int i = sR.size() - 1; i >= 0; i--) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	178 setOrderIndex(sR.getNode(i), orderIndex++);
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 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	181
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	182 private void initializeDegrees(DirectedGraph g) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	183 graphNodes.resetFlags();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	184 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	185 Node n = graphNodes.getNode(i);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	186 setInDegree(n, n.incoming.size());
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	187 setOutDegree(n, n.outgoing.size());
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	188 setDegree(n, n.outgoing.size() - n.incoming.size());
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	189 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	190 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	191
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	192 private void invertEdges(DirectedGraph g) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	193 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	194 Edge e = g.edges.getEdge(i);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	195 if (getOrderIndex(e.source) > getOrderIndex(e.target)) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	196 e.invert();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	197 e.isFeedback_ = true;
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
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	202 private void setDegree(Node n, int deg) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	203 n.workingInts[3] = deg;
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
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	206 private void setIncomingCount(Node n, int count) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	207 n.workingInts[0] = count;
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
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	210 private void setInDegree(Node n, int deg) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	211 n.workingInts[1] = deg;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	212 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	213
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	214 private void setOutDegree(Node n, int deg) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	215 n.workingInts[2] = deg;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	216 }
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 private void setOrderIndex(Node n, int index) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	219 n.workingInts[0] = index;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	220 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	221
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	222 private void sortedInsert(List list, Node node) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	223 int insert = 0;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	224 while (insert < list.size()
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	225 && (cast(Node)list.get(insert)).sortValue > node.sortValue)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	226 insert++;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	227 list.add(insert, node);
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
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	230 /*
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	231 * Called after removal of n. Updates the degree values of n's incoming nodes.
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 void updateIncoming(Node n) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	234 for (int i = 0; i < n.incoming.size(); i++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	235 Node in_ = n.incoming.getEdge(i).source;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	236 if (in_.flag is false) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	237 setOutDegree(in_, getOutDegree(in_) - 1);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	238 setDegree(in_, getOutDegree(in_) - getInDegree(in_));
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	239 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	240 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	241 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	242
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	243 /*
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	244 * Called after removal of n. Updates the degree values of n's outgoing nodes.
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	245 */
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	246 private void updateOutgoing(Node n) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	247 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	248 Node out_ = n.outgoing.getEdge(i).target;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	249 if (out_.flag is false) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	250 setInDegree(out_, getInDegree(out_) - 1);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	251 setDegree(out_, getOutDegree(out_) - getInDegree(out_));
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	252 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	253 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	254 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	255
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	256 public void revisit(DirectedGraph g) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	257 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	258 Edge e = g.edges.getEdge(i);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	259 if (e.isFeedback())
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	260 e.invert();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	261 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	262 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	263
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	264 /**
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	265 * @see GraphVisitor#visit(dwtx.draw2d.graph.DirectedGraph)
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 public void visit(DirectedGraph g) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	268 // put all nodes in list, initialize index
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	269 graphNodes.resetFlags();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	270 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	271 Node n = g.nodes.getNode(i);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	272 setIncomingCount(n, n.incoming.size());
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	273 graphNodes.add(n);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	274 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	275 if (containsCycles(g)) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	276 breakCycles(g);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	277 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	278 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	279
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	280 }

98

95307ad235d9 Added Draw2d code, still work in progress