projects/dwt-addons: dwtx/draw2d/graph/HorizontalPlacement.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, 2007 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.HorizontalPlacement;
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.SpanningTreeVisitor;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	18 import dwtx.draw2d.graph.NodeCluster;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	19 import dwtx.draw2d.graph.NodePair;
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 import dwtx.draw2d.graph.DirectedGraph;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	23 import dwtx.draw2d.graph.RankList;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	24 import dwtx.draw2d.graph.CollapsedEdges;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	25 import dwtx.draw2d.graph.Rank;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	26 import dwtx.draw2d.graph.EdgeList;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	27 import dwtx.draw2d.graph.InitialRankSolver;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	28 import dwtx.draw2d.graph.TightSpanningTreeSolver;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	29 import dwtx.draw2d.graph.RankAssignmentSolver;
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 /**
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	32 * Assigns the X and width values for nodes in a directed graph.
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	33 * @author Randy Hudson
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	34 * @since 2.1.2
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 class HorizontalPlacement : SpanningTreeVisitor {
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 class ClusterSet {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	39 int freedom = Integer.MAX_VALUE;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	40 bool isRight;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	41 public List members;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	42 int pullWeight = 0;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	43 int rawPull = 0;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	44
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	45 public this(){
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	46 members = new ArrayList();
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
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	49 bool addCluster (NodeCluster seed) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	50 members.add(seed);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	51 seed.isSetMember = true;
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 rawPull += seed.weightedTotal;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	54 pullWeight += seed.weightedDivisor;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	55 if (isRight) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	56 freedom = Math.min(freedom, seed.rightNonzero);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	57 if (freedom is 0 \|\| rawPull <= 0)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	58 return true;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	59 addIncomingClusters(seed);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	60 if (addOutgoingClusters(seed))
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	61 return true;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	62 } else {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	63 freedom = Math.min(freedom, seed.leftNonzero);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	64 if (freedom is 0 \|\| rawPull >= 0)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	65 return true;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	66 addOutgoingClusters(seed);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	67 if (addIncomingClusters(seed))
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	68 return true;
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 return false;
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
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	73 bool addIncomingClusters(NodeCluster seed) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	74 for (int i = 0; i < seed.leftCount; i++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	75 NodeCluster neighbor = seed.leftNeighbors[i];
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	76 if (neighbor.isSetMember)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	77 continue;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	78 CollapsedEdges edges = seed.leftLinks[i];
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	79 if (!edges.isTight())
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	80 continue;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	81 if ((!isRight \|\| neighbor.getPull() > 0) && addCluster (neighbor))
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	82 return true;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	83 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	84 return false;
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 bool addOutgoingClusters(NodeCluster seed) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	88 for (int i = 0; i < seed.rightCount; i++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	89 NodeCluster neighbor = seed.rightNeighbors[i];
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	90 if (neighbor.isSetMember)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	91 continue;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	92 CollapsedEdges edges = seed.rightLinks[i];
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	93 if (!edges.isTight())
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	94 continue;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	95 if ((isRight \|\| neighbor.getPull() < 0) && addCluster (neighbor))
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	96 return true;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	97 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	98 return false;
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 bool build(NodeCluster seed) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	102 isRight = seed.weightedTotal > 0;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	103 if (!addCluster(seed)) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	104 int delta = rawPull / pullWeight;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	105 if (delta < 0)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	106 delta = Math.max(delta, -freedom);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	107 else
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	108 delta = Math.min(delta, freedom);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	109 if (delta !is 0) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	110 for (int i = 0; i < members.size(); i++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	111 NodeCluster c = cast(NodeCluster)members.get(i);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	112 c.adjustRank(delta, dirtyClusters);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	113 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	114 refreshDirtyClusters();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	115 reset();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	116 return 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 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	119 reset();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	120 return false;
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 void reset() {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	124 rawPull = pullWeight = 0;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	125 for (int i = 0; i < members.size(); i++)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	126 (cast(NodeCluster)members.get(i)).isSetMember = false;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	127 members.clear();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	128 freedom = Integer.MAX_VALUE;
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 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	131
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	132 static int step;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	133 private List allClusters;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	134 private Map clusterMap;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	135 ClusterSet clusterset;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	136 Collection dirtyClusters;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	137 DirectedGraph graph;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	138 Map map_;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	139 DirectedGraph prime;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	140 Node graphRight;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	141 Node graphLeft;
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 public this(){
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	144 clusterMap = new HashMap();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	145 clusterset = new ClusterSet();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	146 dirtyClusters = new HashSet();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	147 map_ = new HashMap();
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
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 * Inset the corresponding parts for the given 2 nodes along an edge E. The weight value
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	153 * is a value by which to scale the edges specified weighting factor.
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	154 * @param u the source
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	155 * @param v the target
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	156 * @param e the edge along which u and v exist
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	157 * @param weight a scaling for the weight
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 void addEdge(Node u, Node v, Edge e, int weight) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	160 Node ne = new Node(new NodePair(u, v));
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	161 prime.nodes.add(ne);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	162
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	163 ne.y = (u.y + u.height + v.y) / 2;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	164 Node uPrime = get(u);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	165 Node vPrime = get(v);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	166
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	167 int uOffset = e.getSourceOffset();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	168
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	169 int vOffset = e.getTargetOffset();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	170
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	171 Edge eu = new Edge(ne, uPrime, 0, e.weight * weight);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	172 Edge ev = new Edge(ne, vPrime, 0, e.weight * weight);
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 int dw = uOffset - vOffset;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	175 if (dw < 0)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	176 eu.delta = -dw;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	177 else
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	178 ev.delta = dw;
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 prime.edges.add(eu);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	181 prime.edges.add(ev);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	182 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	183
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	184 /**
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	185 * Adds all of the incoming edges to the graph.
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	186 * @param n the original node
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	187 * @param nPrime its corresponding node in the auxilary graph
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 void addEdges(Node n) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	190 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	191 Edge e = n.incoming.getEdge(i);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	192 addEdge(e.source, n, e, 1);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	193 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	194 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	195
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	196 void applyGPrime() {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	197 Node node;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	198 for (int n = 0; n < prime.nodes.size(); n++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	199 node = prime.nodes.getNode(n);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	200 if (null !is cast(Node)node.data )
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	201 (cast(Node)node.data).x = node.rank;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	202 }
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 void balanceClusters() {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	206 findAllClusters();
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 step = 0;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	209 bool somethingMoved = false;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	210
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	211 for (int i = 0; i < allClusters.size();) {
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 NodeCluster c = cast(NodeCluster)allClusters.get(i);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	214 int delta = c.getPull();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	215 if (delta < 0) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	216 if (c.leftFreedom > 0) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	217 c.adjustRank(Math.max(delta, -c.leftFreedom), dirtyClusters);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	218 refreshDirtyClusters();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	219 moveClusterForward(i, c);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	220 somethingMoved = true;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	221 step++;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	222 } else if (clusterset.build(c)) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	223 step++;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	224 moveClusterForward(i, c);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	225 somethingMoved = true;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	226 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	227 } else if (delta > 0) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	228 if (c.rightFreedom > 0) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	229 c.adjustRank(Math.min(delta, c.rightFreedom), dirtyClusters);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	230 refreshDirtyClusters();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	231 moveClusterForward(i, c);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	232 somethingMoved = true;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	233 step++;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	234 } else if (clusterset.build(c)) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	235 step++;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	236 moveClusterForward(i, c);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	237 somethingMoved = true;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	238 }
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 i++;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	241 if (i is allClusters.size() && somethingMoved) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	242 i = 0;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	243 somethingMoved = false;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	244 }
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 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	247
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	248 //bool balanceClusterSets() {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	249 // for (int i = 0; i < allClusters.size(); i++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	250 // NodeCluster c = (NodeCluster)allClusters.get(i);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	251 // if (c.weightedTotal < 0 && c.leftFreedom is 0) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	252 // if (clusterset.build(c)) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	253 // moveClusterForward(i, c);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	254 // return true;
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 // } else if (c.weightedTotal > 0 && c.rightFreedom is 0) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	257 // if (clusterset.build(c)) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	258 // moveClusterForward(i, c);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	259 // return true;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	260 // }
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 // return false;
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
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	266 void buildGPrime() {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	267 RankList ranks = graph.ranks;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	268 buildRankSeparators(ranks);
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 Rank rank;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	271 Node n;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	272 for (int r = 1; r < ranks.size(); r++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	273 rank = ranks.getRank(r);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	274 for (int i = 0; i < rank.count(); i++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	275 n = rank.getNode(i);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	276 addEdges(n);
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
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	281 void buildRankSeparators(RankList ranks) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	282 Rank rank;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	283 Node n, nPrime, prevNPrime;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	284 Edge e;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	285 for (int r = 0; r < ranks.size(); r++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	286 rank = ranks.getRank(r);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	287 prevNPrime = null;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	288 for (int i = 0; i < rank.count(); i++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	289 n = rank.getNode(i);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	290 nPrime = new Node(n);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	291 if (i is 0) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	292 e = new Edge(graphLeft, nPrime, 0, 0);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	293 prime.edges.add(e);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	294 e.delta = graph.getPadding(n).left + graph.getMargin().left;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	295 } else {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	296 e = new Edge(prevNPrime, nPrime);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	297 e.weight = 0;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	298 prime.edges.add(e);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	299 rowSeparation(e);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	300 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	301 prevNPrime = nPrime;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	302 prime.nodes.add(nPrime);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	303 map(n, nPrime);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	304 if (i is rank.count() - 1) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	305 e = new Edge(nPrime, graphRight, 0, 0);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	306 e.delta = n.width + graph.getPadding(n).right + graph.getMargin().right;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	307 prime.edges.add(e);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	308 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	309 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	310 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	311 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	312
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	313 private void calculateCellLocations() {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	314 graph.cellLocations = new int[][](graph.ranks.size() + 1);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	315 for (int row = 0; row < graph.ranks.size(); row++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	316 Rank rank = graph.ranks.getRank(row);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	317 int locations[] = graph.cellLocations[row] = new int[rank.size() + 1];
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	318 int cell;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	319 Node node = null;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	320 for (cell = 0; cell < rank.size(); cell++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	321 node = rank.getNode(cell);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	322 locations[cell] = node.x - graph.getPadding(node).left;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	323 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	324 locations[cell] = node.x + node.width + graph.getPadding(node).right;
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 private void findAllClusters() {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	329 Node root = prime.nodes.getNode(0);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	330 NodeCluster cluster = new NodeCluster();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	331 allClusters = new ArrayList();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	332 allClusters.add(cluster);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	333 growCluster(root, cluster);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	334
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	335 for (int i = 0; i < prime.edges.size(); i++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	336 Edge e = prime.edges.getEdge(i);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	337 NodeCluster sourceCluster = cast(NodeCluster)clusterMap.get(e.source);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	338 NodeCluster targetCluster = cast(NodeCluster)clusterMap.get(e.target);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	339
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	340 //Ignore cluster internal edges
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	341 if (targetCluster is sourceCluster)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	342 continue;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	343
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	344 CollapsedEdges link = sourceCluster.getRightNeighbor(targetCluster);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	345 if (link is null) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	346 link = new CollapsedEdges(e);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	347 sourceCluster.addRightNeighbor(targetCluster, link);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	348 targetCluster.addLeftNeighbor(sourceCluster, link);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	349 } else {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	350 prime.removeEdge(link.processEdge(e));
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	351 i--;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	352 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	353 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	354 for (int i = 0; i < allClusters.size(); i++)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	355 (cast(NodeCluster)allClusters.get(i)).initValues();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	356 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	357
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	358 Node get(Node key) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	359 return cast(Node)map_.get(key);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	360 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	361
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	362 void growCluster(Node root, NodeCluster cluster) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	363 cluster.add(root);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	364 clusterMap.put(root, cluster);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	365 EdgeList treeChildren = getSpanningTreeChildren(root);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	366 for (int i = 0; i < treeChildren.size(); i++) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	367 Edge e = treeChildren.getEdge(i);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	368 if (e.cut !is 0)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	369 growCluster(getTreeTail(e), cluster);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	370 else {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	371 NodeCluster newCluster = new NodeCluster();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	372 allClusters.add(newCluster);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	373 growCluster(getTreeTail(e), newCluster);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	374 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	375 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	376 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	377
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	378 void map(Node key, Node value) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	379 map_.put(key, value);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	380 }
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 private void moveClusterForward(int i, NodeCluster c) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	383 if (i is 0)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	384 return;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	385 int swapIndex = i / 2;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	386 Object temp = allClusters.get(swapIndex);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	387 allClusters.set(swapIndex, c);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	388 allClusters.set(i, temp);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	389 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	390
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	391 void refreshDirtyClusters() {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	392 for (Iterator iter = dirtyClusters.iterator(); iter.hasNext();)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	393 (cast(NodeCluster)iter.next()).refreshValues();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	394 dirtyClusters.clear();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	395 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	396
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	397 void rowSeparation(Edge e) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	398 Node source = cast(Node)e.source.data;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	399 Node target = cast(Node)e.target.data;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	400 e.delta = source.width
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	401 + graph.getPadding(source).right
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	402 + graph.getPadding(target).left;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	403 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	404
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	405 public void visit(DirectedGraph g) {
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	406 graph = g;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	407 prime = new DirectedGraph();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	408 prime.nodes.add(graphLeft = new Node(cast(Object)null));
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	409 prime.nodes.add(graphRight = new Node(cast(Object)null));
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	410 if (g.tensorStrength !is 0)
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	411 prime.edges.add(new Edge(graphLeft, graphRight, g.tensorSize, g.tensorStrength));
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	412 buildGPrime();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	413 (new InitialRankSolver())
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	414 .visit(prime);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	415 (new TightSpanningTreeSolver())
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	416 .visit(prime);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	417
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	418 RankAssignmentSolver solver = new RankAssignmentSolver();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	419 solver.visit(prime);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	420 graph.size.width = graphRight.rank;
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	421 balanceClusters();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	422
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	423 prime.nodes.adjustRank(-graphLeft.rank);
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	424 applyGPrime();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	425 calculateCellLocations();
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	426 }
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	427
95307ad235d9 Added Draw2d code, still work in progress Frank Benoit <benoit@tionex.de> parents: diff changeset	428 }

98

95307ad235d9 Added Draw2d code, still work in progress