Mercurial > projects > dwt-addons

comparison dwtx/draw2d/graph/HorizontalPlacement.d @ 98:95307ad235d9

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Added Draw2d code, still work in progress
author Frank Benoit <benoit@tionex.de>
date Sun, 03 Aug 2008 00:52:14 +0200
parents
children
comparison
equal deleted inserted replaced
96:b492ba44e44d 98:95307ad235d9
1 /*******************************************************************************
2 * Copyright (c) 2003, 2007 IBM Corporation and others.
3 * All rights reserved. This program and the accompanying materials
4 * are made available under the terms of the Eclipse Public License v1.0
5 * which accompanies this distribution, and is available at
6 * http://www.eclipse.org/legal/epl-v10.html
7 *
8 * Contributors:
9 * IBM Corporation - initial API and implementation
10 * Port to the D programming language:
11 * Frank Benoit <benoit@tionex.de>
12 *******************************************************************************/
13 module dwtx.draw2d.graph.HorizontalPlacement;
14
15 import dwt.dwthelper.utils;
16 import dwtx.dwtxhelper.Collection;
17 import dwtx.draw2d.graph.SpanningTreeVisitor;
18 import dwtx.draw2d.graph.NodeCluster;
19 import dwtx.draw2d.graph.NodePair;
20 import dwtx.draw2d.graph.Node;
21 import dwtx.draw2d.graph.Edge;
22 import dwtx.draw2d.graph.DirectedGraph;
23 import dwtx.draw2d.graph.RankList;
24 import dwtx.draw2d.graph.CollapsedEdges;
25 import dwtx.draw2d.graph.Rank;
26 import dwtx.draw2d.graph.EdgeList;
27 import dwtx.draw2d.graph.InitialRankSolver;
28 import dwtx.draw2d.graph.TightSpanningTreeSolver;
29 import dwtx.draw2d.graph.RankAssignmentSolver;
30
31 /**
32 * Assigns the X and width values for nodes in a directed graph.
33 * @author Randy Hudson
34 * @since 2.1.2
35 */
36 class HorizontalPlacement : SpanningTreeVisitor {
37
38 class ClusterSet {
39 int freedom = Integer.MAX_VALUE;
40 bool isRight;
41 public List members;
42 int pullWeight = 0;
43 int rawPull = 0;
44
45 public this(){
46 members = new ArrayList();
47 }
48
49 bool addCluster (NodeCluster seed) {
50 members.add(seed);
51 seed.isSetMember = true;
52
53 rawPull += seed.weightedTotal;
54 pullWeight += seed.weightedDivisor;
55 if (isRight) {
56 freedom = Math.min(freedom, seed.rightNonzero);
57 if (freedom is 0 || rawPull <= 0)
58 return true;
59 addIncomingClusters(seed);
60 if (addOutgoingClusters(seed))
61 return true;
62 } else {
63 freedom = Math.min(freedom, seed.leftNonzero);
64 if (freedom is 0 || rawPull >= 0)
65 return true;
66 addOutgoingClusters(seed);
67 if (addIncomingClusters(seed))
68 return true;
69 }
70 return false;
71 }
72
73 bool addIncomingClusters(NodeCluster seed) {
74 for (int i = 0; i < seed.leftCount; i++) {
75 NodeCluster neighbor = seed.leftNeighbors[i];
76 if (neighbor.isSetMember)
77 continue;
78 CollapsedEdges edges = seed.leftLinks[i];
79 if (!edges.isTight())
80 continue;
81 if ((!isRight || neighbor.getPull() > 0) && addCluster (neighbor))
82 return true;
83 }
84 return false;
85 }
86
87 bool addOutgoingClusters(NodeCluster seed) {
88 for (int i = 0; i < seed.rightCount; i++) {
89 NodeCluster neighbor = seed.rightNeighbors[i];
90 if (neighbor.isSetMember)
91 continue;
92 CollapsedEdges edges = seed.rightLinks[i];
93 if (!edges.isTight())
94 continue;
95 if ((isRight || neighbor.getPull() < 0) && addCluster (neighbor))
96 return true;
97 }
98 return false;
99 }
100
101 bool build(NodeCluster seed) {
102 isRight = seed.weightedTotal > 0;
103 if (!addCluster(seed)) {
104 int delta = rawPull / pullWeight;
105 if (delta < 0)
106 delta = Math.max(delta, -freedom);
107 else
108 delta = Math.min(delta, freedom);
109 if (delta !is 0) {
110 for (int i = 0; i < members.size(); i++) {
111 NodeCluster c = cast(NodeCluster)members.get(i);
112 c.adjustRank(delta, dirtyClusters);
113 }
114 refreshDirtyClusters();
115 reset();
116 return true;
117 }
118 }
119 reset();
120 return false;
121 }
122
123 void reset() {
124 rawPull = pullWeight = 0;
125 for (int i = 0; i < members.size(); i++)
126 (cast(NodeCluster)members.get(i)).isSetMember = false;
127 members.clear();
128 freedom = Integer.MAX_VALUE;
129 }
130 }
131
132 static int step;
133 private List allClusters;
134 private Map clusterMap;
135 ClusterSet clusterset;
136 Collection dirtyClusters;
137 DirectedGraph graph;
138 Map map_;
139 DirectedGraph prime;
140 Node graphRight;
141 Node graphLeft;
142
143 public this(){
144 clusterMap = new HashMap();
145 clusterset = new ClusterSet();
146 dirtyClusters = new HashSet();
147 map_ = new HashMap();
148 }
149
150
151 /**
152 * Inset the corresponding parts for the given 2 nodes along an edge E. The weight value
153 * is a value by which to scale the edges specified weighting factor.
154 * @param u the source
155 * @param v the target
156 * @param e the edge along which u and v exist
157 * @param weight a scaling for the weight
158 */
159 void addEdge(Node u, Node v, Edge e, int weight) {
160 Node ne = new Node(new NodePair(u, v));
161 prime.nodes.add(ne);
162
163 ne.y = (u.y + u.height + v.y) / 2;
164 Node uPrime = get(u);
165 Node vPrime = get(v);
166
167 int uOffset = e.getSourceOffset();
168
169 int vOffset = e.getTargetOffset();
170
171 Edge eu = new Edge(ne, uPrime, 0, e.weight * weight);
172 Edge ev = new Edge(ne, vPrime, 0, e.weight * weight);
173
174 int dw = uOffset - vOffset;
175 if (dw < 0)
176 eu.delta = -dw;
177 else
178 ev.delta = dw;
179
180 prime.edges.add(eu);
181 prime.edges.add(ev);
182 }
183
184 /**
185 * Adds all of the incoming edges to the graph.
186 * @param n the original node
187 * @param nPrime its corresponding node in the auxilary graph
188 */
189 void addEdges(Node n) {
190 for (int i = 0; i < n.incoming.size(); i++) {
191 Edge e = n.incoming.getEdge(i);
192 addEdge(e.source, n, e, 1);
193 }
194 }
195
196 void applyGPrime() {
197 Node node;
198 for (int n = 0; n < prime.nodes.size(); n++) {
199 node = prime.nodes.getNode(n);
200 if (null !is cast(Node)node.data )
201 (cast(Node)node.data).x = node.rank;
202 }
203 }
204
205 private void balanceClusters() {
206 findAllClusters();
207
208 step = 0;
209 bool somethingMoved = false;
210
211 for (int i = 0; i < allClusters.size();) {
212
213 NodeCluster c = cast(NodeCluster)allClusters.get(i);
214 int delta = c.getPull();
215 if (delta < 0) {
216 if (c.leftFreedom > 0) {
217 c.adjustRank(Math.max(delta, -c.leftFreedom), dirtyClusters);
218 refreshDirtyClusters();
219 moveClusterForward(i, c);
220 somethingMoved = true;
221 step++;
222 } else if (clusterset.build(c)) {
223 step++;
224 moveClusterForward(i, c);
225 somethingMoved = true;
226 }
227 } else if (delta > 0) {
228 if (c.rightFreedom > 0) {
229 c.adjustRank(Math.min(delta, c.rightFreedom), dirtyClusters);
230 refreshDirtyClusters();
231 moveClusterForward(i, c);
232 somethingMoved = true;
233 step++;
234 } else if (clusterset.build(c)) {
235 step++;
236 moveClusterForward(i, c);
237 somethingMoved = true;
238 }
239 }
240 i++;
241 if (i is allClusters.size() && somethingMoved) {
242 i = 0;
243 somethingMoved = false;
244 }
245 }
246 }
247
248 //bool balanceClusterSets() {
249 // for (int i = 0; i < allClusters.size(); i++) {
250 // NodeCluster c = (NodeCluster)allClusters.get(i);
251 // if (c.weightedTotal < 0 && c.leftFreedom is 0) {
252 // if (clusterset.build(c)) {
253 // moveClusterForward(i, c);
254 // return true;
255 // }
256 // } else if (c.weightedTotal > 0 && c.rightFreedom is 0) {
257 // if (clusterset.build(c)) {
258 // moveClusterForward(i, c);
259 // return true;
260 // }
261 // }
262 // }
263 // return false;
264 //}
265
266 void buildGPrime() {
267 RankList ranks = graph.ranks;
268 buildRankSeparators(ranks);
269
270 Rank rank;
271 Node n;
272 for (int r = 1; r < ranks.size(); r++) {
273 rank = ranks.getRank(r);
274 for (int i = 0; i < rank.count(); i++) {
275 n = rank.getNode(i);
276 addEdges(n);
277 }
278 }
279 }
280
281 void buildRankSeparators(RankList ranks) {
282 Rank rank;
283 Node n, nPrime, prevNPrime;
284 Edge e;
285 for (int r = 0; r < ranks.size(); r++) {
286 rank = ranks.getRank(r);
287 prevNPrime = null;
288 for (int i = 0; i < rank.count(); i++) {
289 n = rank.getNode(i);
290 nPrime = new Node(n);
291 if (i is 0) {
292 e = new Edge(graphLeft, nPrime, 0, 0);
293 prime.edges.add(e);
294 e.delta = graph.getPadding(n).left + graph.getMargin().left;
295 } else {
296 e = new Edge(prevNPrime, nPrime);
297 e.weight = 0;
298 prime.edges.add(e);
299 rowSeparation(e);
300 }
301 prevNPrime = nPrime;
302 prime.nodes.add(nPrime);
303 map(n, nPrime);
304 if (i is rank.count() - 1) {
305 e = new Edge(nPrime, graphRight, 0, 0);
306 e.delta = n.width + graph.getPadding(n).right + graph.getMargin().right;
307 prime.edges.add(e);
308 }
309 }
310 }
311 }
312
313 private void calculateCellLocations() {
314 graph.cellLocations = new int[][](graph.ranks.size() + 1);
315 for (int row = 0; row < graph.ranks.size(); row++) {
316 Rank rank = graph.ranks.getRank(row);
317 int locations[] = graph.cellLocations[row] = new int[rank.size() + 1];
318 int cell;
319 Node node = null;
320 for (cell = 0; cell < rank.size(); cell++) {
321 node = rank.getNode(cell);
322 locations[cell] = node.x - graph.getPadding(node).left;
323 }
324 locations[cell] = node.x + node.width + graph.getPadding(node).right;
325 }
326 }
327
328 private void findAllClusters() {
329 Node root = prime.nodes.getNode(0);
330 NodeCluster cluster = new NodeCluster();
331 allClusters = new ArrayList();
332 allClusters.add(cluster);
333 growCluster(root, cluster);
334
335 for (int i = 0; i < prime.edges.size(); i++) {
336 Edge e = prime.edges.getEdge(i);
337 NodeCluster sourceCluster = cast(NodeCluster)clusterMap.get(e.source);
338 NodeCluster targetCluster = cast(NodeCluster)clusterMap.get(e.target);
339
340 //Ignore cluster internal edges
341 if (targetCluster is sourceCluster)
342 continue;
343
344 CollapsedEdges link = sourceCluster.getRightNeighbor(targetCluster);
345 if (link is null) {
346 link = new CollapsedEdges(e);
347 sourceCluster.addRightNeighbor(targetCluster, link);
348 targetCluster.addLeftNeighbor(sourceCluster, link);
349 } else {
350 prime.removeEdge(link.processEdge(e));
351 i--;
352 }
353 }
354 for (int i = 0; i < allClusters.size(); i++)
355 (cast(NodeCluster)allClusters.get(i)).initValues();
356 }
357
358 Node get(Node key) {
359 return cast(Node)map_.get(key);
360 }
361
362 void growCluster(Node root, NodeCluster cluster) {
363 cluster.add(root);
364 clusterMap.put(root, cluster);
365 EdgeList treeChildren = getSpanningTreeChildren(root);
366 for (int i = 0; i < treeChildren.size(); i++) {
367 Edge e = treeChildren.getEdge(i);
368 if (e.cut !is 0)
369 growCluster(getTreeTail(e), cluster);
370 else {
371 NodeCluster newCluster = new NodeCluster();
372 allClusters.add(newCluster);
373 growCluster(getTreeTail(e), newCluster);
374 }
375 }
376 }
377
378 void map(Node key, Node value) {
379 map_.put(key, value);
380 }
381
382 private void moveClusterForward(int i, NodeCluster c) {
383 if (i is 0)
384 return;
385 int swapIndex = i / 2;
386 Object temp = allClusters.get(swapIndex);
387 allClusters.set(swapIndex, c);
388 allClusters.set(i, temp);
389 }
390
391 void refreshDirtyClusters() {
392 for (Iterator iter = dirtyClusters.iterator(); iter.hasNext();)
393 (cast(NodeCluster)iter.next()).refreshValues();
394 dirtyClusters.clear();
395 }
396
397 void rowSeparation(Edge e) {
398 Node source = cast(Node)e.source.data;
399 Node target = cast(Node)e.target.data;
400 e.delta = source.width
401 + graph.getPadding(source).right
402 + graph.getPadding(target).left;
403 }
404
405 public void visit(DirectedGraph g) {
406 graph = g;
407 prime = new DirectedGraph();
408 prime.nodes.add(graphLeft = new Node(cast(Object)null));
409 prime.nodes.add(graphRight = new Node(cast(Object)null));
410 if (g.tensorStrength !is 0)
411 prime.edges.add(new Edge(graphLeft, graphRight, g.tensorSize, g.tensorStrength));
412 buildGPrime();
413 (new InitialRankSolver())
414 .visit(prime);
415 (new TightSpanningTreeSolver())
416 .visit(prime);
417
418 RankAssignmentSolver solver = new RankAssignmentSolver();
419 solver.visit(prime);
420 graph.size.width = graphRight.rank;
421 balanceClusters();
422
423 prime.nodes.adjustRank(-graphLeft.rank);
424 applyGPrime();
425 calculateCellLocations();
426 }
427
428 }