Mercurial > projects > dwt-addons
annotate dwtx/draw2d/graph/LocalOptimizer.d @ 98:95307ad235d9
Added Draw2d code, still work in progress
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.LocalOptimizer; |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
14 |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
15 import dwt.dwthelper.utils; |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
16 import dwtx.draw2d.graph.GraphVisitor; |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
17 import dwtx.draw2d.graph.GraphUtilities; |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
18 import dwtx.draw2d.graph.Node; |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
19 import dwtx.draw2d.graph.Rank; |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
20 import dwtx.draw2d.graph.DirectedGraph; |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
21 import dwtx.draw2d.graph.EdgeList; |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
22 import dwtx.draw2d.graph.Edge; |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
23 |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
24 /** |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
25 * This graph visitor examines all adjacent pairs of nodes and determines if |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
26 * swapping the two nodes provides improved graph aesthetics. |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
27 * @author Daniel Lee |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
28 * @since 2.1.2 |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
29 */ |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
30 class LocalOptimizer : GraphVisitor { |
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 bool shouldSwap(Node current, Node next) { |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
33 if (GraphUtilities.isConstrained(current, next)) |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
34 return false; |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
35 int crossCount = 0; |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
36 int invertedCrossCount = 0; |
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 EdgeList currentEdges = current.incoming; |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
39 EdgeList nextEdges = next.incoming; |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
40 int rank = current.rank - 1; |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
41 int iCurrent, iNext; |
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 for (int i = 0; i < currentEdges.size(); i++) { |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
44 Edge currentEdge = currentEdges.getEdge(i); |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
45 iCurrent = currentEdge.getIndexForRank(rank); |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
46 for (int j = 0; j < nextEdges.size(); j++) { |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
47 iNext = nextEdges.getEdge(j).getIndexForRank(rank); |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
48 if (iNext < iCurrent) |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
49 crossCount++; |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
50 else if (iNext > iCurrent) |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
51 invertedCrossCount++; |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
52 else { |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
53 //edges go to the same location |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
54 int offsetDiff = nextEdges.getEdge(j).getSourceOffset() |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
55 - currentEdge.getSourceOffset(); |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
56 if (offsetDiff < 0) |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
57 crossCount++; |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
58 else if (offsetDiff > 0) |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
59 invertedCrossCount++; |
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 } |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
62 } |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
63 |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
64 currentEdges = current.outgoing; |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
65 nextEdges = next.outgoing; |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
66 rank = current.rank + 1; |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
67 |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
68 for (int i = 0; i < currentEdges.size(); i++) { |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
69 Edge currentEdge = currentEdges.getEdge(i); |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
70 iCurrent = currentEdge.getIndexForRank(rank); |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
71 for (int j = 0; j < nextEdges.size(); j++) { |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
72 iNext = nextEdges.getEdge(j).getIndexForRank(rank); |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
73 if (iNext < iCurrent) |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
74 crossCount++; |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
75 else if (iNext > iCurrent) |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
76 invertedCrossCount++; |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
77 else { |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
78 //edges go to the same location |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
79 int offsetDiff = nextEdges.getEdge(j).getTargetOffset() |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
80 - currentEdge.getTargetOffset(); |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
81 if (offsetDiff < 0) |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
82 crossCount++; |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
83 else if (offsetDiff > 0) |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
84 invertedCrossCount++; |
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 } |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
88 if (invertedCrossCount < crossCount) |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
89 return true; |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
90 return false; |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
91 } |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
92 |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
93 private void swapNodes(Node current, Node next, Rank rank) { |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
94 int index = rank.indexOf(current); |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
95 rank.set(index + 1, current); |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
96 rank.set(index, next); |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
97 index = current.index; |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
98 current.index = next.index; |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
99 next.index = index; |
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 |
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 * @see GraphVisitor#visit(dwtx.draw2d.graph.DirectedGraph) |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
104 */ |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
105 public void visit(DirectedGraph g) { |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
106 bool flag; |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
107 do { |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
108 flag = false; |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
109 for (int r = 0; r < g.ranks.size(); r++) { |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
110 Rank rank = g.ranks.getRank(r); |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
111 for (int n = 0; n < rank.count() - 1; n++) { |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
112 Node currentNode = rank.getNode(n); |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
113 Node nextNode = rank.getNode(n + 1); |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
114 if (shouldSwap(currentNode, nextNode)) { |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
115 swapNodes(currentNode, nextNode, rank); |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
116 flag = true; |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
117 n = Math.max(0, n - 2); |
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 } |
95307ad235d9
Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff
changeset
|
121 } while (flag); |
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 } |