Mercurial > projects > dwt2

comparison org.eclipse.draw2d/src/org/eclipse/draw2d/graph/RankAssignmentSolver.d @ 12:bc29606a740c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Added dwt-addons in original directory structure of eclipse.org
author Frank Benoit <benoit@tionex.de>
date Sat, 14 Mar 2009 18:23:29 +0100
parents
children dbfb303e8fb0
comparison
equal deleted inserted replaced
11:43904fec5dca 12:bc29606a740c
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 org.eclipse.draw2d.graph.RankAssignmentSolver;
14
15 import java.lang.all;
16 import org.eclipse.draw2d.graph.SpanningTreeVisitor;
17 import org.eclipse.draw2d.graph.EdgeList;
18 import org.eclipse.draw2d.graph.Edge;
19 import org.eclipse.draw2d.graph.Node;
20 import org.eclipse.draw2d.graph.DirectedGraph;
21 import org.eclipse.draw2d.graph.NodeList;
22
23 /**
24 * Assigns the final rank assignment for a DirectedGraph with an initial feasible
25 * spanning tree.
26 * @author Randy Hudson
27 * @since 2.1.2
28 */
29 class RankAssignmentSolver : SpanningTreeVisitor {
30
31 DirectedGraph graph;
32 EdgeList spanningTree;
33 bool searchDirection;
34
35 int depthFirstCutValue(Edge edge, int count) {
36 Node n = getTreeTail(edge);
37 setTreeMin(n, count);
38 int cutvalue = 0;
39 int multiplier = (edge.target is n) ? 1 : -1;
40 EdgeList list;
41
42 list = n.outgoing;
43 Edge e;
44 for (int i = 0; i < list.size(); i++) {
45 e = list.getEdge(i);
46 if (e.tree && e !is edge) {
47 count = depthFirstCutValue(e, count);
48 cutvalue += (e.cut - e.weight) * multiplier;
49 } else {
50 cutvalue -= e.weight * multiplier;
51 }
52 }
53 list = n.incoming;
54 for (int i = 0; i < list.size(); i++) {
55 e = list.getEdge(i);
56 if (e.tree && e !is edge) {
57 count = depthFirstCutValue(e, count);
58 cutvalue -= (e.cut - e.weight) * multiplier;
59 } else {
60 cutvalue += e.weight * multiplier;
61 }
62 }
63
64 edge.cut = cutvalue;
65 if (cutvalue < 0)
66 spanningTree.add(edge);
67 setTreeMax(n, count);
68 return count + 1;
69 }
70
71 /**
72 * returns the Edge which should be entered.
73 * @param branch
74 * @return Edge
75 */
76 Edge enter(Node branch) {
77 Node n;
78 Edge result = null;
79 int minSlack = Integer.MAX_VALUE;
80 bool incoming = getParentEdge(branch).target !is branch;
81 // searchDirection = !searchDirection;
82 for (int i = 0; i < graph.nodes.size(); i++) {
83 if (searchDirection)
84 n = graph.nodes.getNode(i);
85 else
86 n = graph.nodes.getNode(graph.nodes.size() - 1 - i);
87 if (subtreeContains(branch, n)) {
88 EdgeList edges;
89 if (incoming)
90 edges = n.incoming;
91 else
92 edges = n.outgoing;
93 for (int j = 0; j < edges.size(); j++) {
94 Edge e = edges.getEdge(j);
95 if (!subtreeContains(branch, e.opposite(n))
96 && !e.tree
97 && e.getSlack() < minSlack) {
98 result = e;
99 minSlack = e.getSlack();
100 }
101 }
102 }
103 }
104 return result;
105 }
106
107 int getTreeMax(Node n) {
108 return n.workingInts[1];
109 }
110
111 int getTreeMin(Node n) {
112 return n.workingInts[0];
113 }
114
115 void initCutValues() {
116 Node root = graph.nodes.getNode(0);
117 spanningTree = new EdgeList();
118 Edge e;
119 setTreeMin(root, 1);
120 setTreeMax(root, 1);
121
122 for (int i = 0; i < root.outgoing.size(); i++) {
123 e = root.outgoing.getEdge(i);
124 if (!getSpanningTreeChildren(root).contains(e))
125 continue;
126 setTreeMax(root, depthFirstCutValue(e, getTreeMax(root)));
127 }
128 for (int i = 0; i < root.incoming.size(); i++) {
129 e = root.incoming.getEdge(i);
130 if (!getSpanningTreeChildren(root).contains(e))
131 continue;
132 setTreeMax(root, depthFirstCutValue(e, getTreeMax(root)));
133 }
134 }
135
136 Edge leave() {
137 Edge result = null;
138 Edge e;
139 int minCut = 0;
140 int weight = -1;
141 for (int i = 0; i < spanningTree.size(); i++) {
142 e = spanningTree.getEdge(i);
143 if (e.cut < minCut) {
144 result = e;
145 minCut = result.cut;
146 weight = result.weight;
147 } else if (e.cut is minCut && e.weight > weight) {
148 result = e;
149 weight = result.weight;
150 }
151 }
152 return result;
153 }
154
155 void networkSimplexLoop() {
156 Edge leave_, enter_;
157 int count = 0;
158 while ((leave_ = leave()) !is null && count < 900) {
159
160 count++;
161
162 Node leaveTail = getTreeTail(leave_);
163 Node leaveHead = getTreeHead(leave_);
164
165 enter_ = enter(leaveTail);
166 if (enter_ is null)
167 break;
168
169 //Break the "leave" edge from the spanning tree
170 getSpanningTreeChildren(leaveHead).remove(leave_);
171 setParentEdge(leaveTail, null);
172 leave_.tree = false;
173 spanningTree.remove(leave_);
174
175 Node enterTail = enter_.source;
176 if (!subtreeContains(leaveTail, enterTail))
177 //Oops, wrong end of the edge
178 enterTail = enter_.target;
179 Node enterHead = enter_.opposite(enterTail);
180
181 //Prepare enterTail by making it the root of its sub-tree
182 updateSubgraph(enterTail);
183
184 //Add "enter" edge to the spanning tree
185 getSpanningTreeChildren(enterHead).add(enter_);
186 setParentEdge(enterTail, enter_);
187 enter_.tree = true;
188
189 repairCutValues(enter_);
190
191 Node commonAncestor = enterHead;
192
193 while (!subtreeContains(commonAncestor, leaveHead)) {
194 repairCutValues(getParentEdge(commonAncestor));
195 commonAncestor = getTreeParent(commonAncestor);
196 }
197 while (leaveHead !is commonAncestor) {
198 repairCutValues(getParentEdge(leaveHead));
199 leaveHead = getTreeParent(leaveHead);
200 }
201 updateMinMax(commonAncestor, getTreeMin(commonAncestor));
202 tightenEdge(enter_);
203 }
204 }
205
206 void repairCutValues(Edge edge) {
207 spanningTree.remove(edge);
208 Node n = getTreeTail(edge);
209 int cutvalue = 0;
210 int multiplier = (edge.target is n) ? 1 : -1;
211 EdgeList list;
212
213 list = n.outgoing;
214 Edge e;
215 for (int i = 0; i < list.size(); i++) {
216 e = list.getEdge(i);
217 if (e.tree && e !is edge)
218 cutvalue += (e.cut - e.weight) * multiplier;
219 else
220 cutvalue -= e.weight * multiplier;
221 }
222 list = n.incoming;
223 for (int i = 0; i < list.size(); i++) {
224 e = list.getEdge(i);
225 if (e.tree && e !is edge)
226 cutvalue -= (e.cut - e.weight) * multiplier;
227 else
228 cutvalue += e.weight * multiplier;
229 }
230
231 edge.cut = cutvalue;
232 if (cutvalue < 0)
233 spanningTree.add(edge);
234 }
235
236 void setTreeMax(Node n, int value) {
237 n.workingInts[1] = value;
238 }
239
240 void setTreeMin(Node n, int value) {
241 n.workingInts[0] = value;
242 }
243
244 bool subtreeContains(Node parent, Node child) {
245 return parent.workingInts[0] <= child.workingInts[1]
246 && child.workingInts[1] <= parent.workingInts[1];
247 }
248
249 void tightenEdge(Edge edge) {
250 Node tail = getTreeTail(edge);
251 int delta = edge.getSlack();
252 if (tail is edge.target)
253 delta = -delta;
254 Node n;
255 for (int i = 0; i < graph.nodes.size(); i++) {
256 n = graph.nodes.getNode(i);
257 if (subtreeContains(tail, n))
258 n.rank += delta;
259 }
260 }
261
262 int updateMinMax(Node root, int count) {
263 setTreeMin(root, count);
264 EdgeList edges = getSpanningTreeChildren(root);
265 for (int i = 0; i < edges.size(); i++)
266 count = updateMinMax(getTreeTail(edges.getEdge(i)), count);
267 setTreeMax(root, count);
268 return count + 1;
269 }
270
271 void updateSubgraph(Node root) {
272 Edge flip = getParentEdge(root);
273 if (flip !is null) {
274 Node rootParent = getTreeParent(root);
275 getSpanningTreeChildren(rootParent).remove(flip);
276 updateSubgraph(rootParent);
277 setParentEdge(root, null);
278 setParentEdge(rootParent, flip);
279 repairCutValues(flip);
280 getSpanningTreeChildren(root).add(flip);
281 }
282 }
283
284 public void visit(DirectedGraph graph) {
285 this.graph = graph;
286 initCutValues();
287 networkSimplexLoop();
288 if (graph.forestRoot is null)
289 graph.nodes.normalizeRanks();
290 else
291 normalizeForest();
292 }
293
294 private void normalizeForest() {
295 NodeList tree = new NodeList();
296 graph.nodes.resetFlags();
297 graph.forestRoot.flag = true;
298 EdgeList rootEdges = graph.forestRoot.outgoing;
299 Stack stack = new Stack();
300 for (int i = 0; i < rootEdges.size(); i++) {
301 Node node = rootEdges.getEdge(i).target;
302 node.flag = true;
303 stack.push(node);
304 while (!stack.isEmpty()) {
305 node = cast(Node) stack.pop();
306 tree.add(node);
307 Iterator neighbors = node.iteratorNeighbors();
308 while (neighbors.hasNext()) {
309 Node neighbor = cast(Node) neighbors.next();
310 if (!neighbor.flag) {
311 neighbor.flag = true;
312 stack.push(neighbor);
313 }
314 }
315 }
316 tree.normalizeRanks();
317 tree.clear();
318 }
319 }
320
321 }