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