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