Mercurial > projects > dwt2
comparison org.eclipse.draw2d/src/org/eclipse/draw2d/graph/RankAssignmentSolver.d @ 12:bc29606a740c
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 } |