1 /*
2 * Copyright (C) 2007 Bill Cox
3 *
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; either version 2 of the License, or
7 * (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111 USA
17 */
18
19 /*--------------------------------------------------------------------------------------------------
20 This module places classes into rows in the schema. The algorithm is basically:
21
22 - Assign classes to rows, starting with classes without parents, and assigning their children
23 to the next row, and so on
24 - Assign relative positions within rows to reduce crossings as much as possible
25 - Assign exact position to minimize total length of horizontal routing
26 --------------------------------------------------------------------------------------------------*/
27
28 #include "dw.h"
29
30 static dwClassArray dwGrid = dwClassArrayNull;
31 static uint32 dwNumCols = UINT32_MAX;
32 static dwClassArray dwClasses = dwClassArrayNull;
33 static uint32 dwCost;
34 static uint32 dwUndoX1 = UINT32_MAX;
35 static uint32 dwUndoX2 = UINT32_MAX;
36 static uint32 dwUndoY1 = UINT32_MAX;
37 static uint32 dwUndoY2 = UINT32_MAX;
38
39 /*--------------------------------------------------------------------------------------------------
40 Initialize globals.
41 --------------------------------------------------------------------------------------------------*/
init(dvSchema schema)42 static void init(
43 dvSchema schema)
44 {
45 dvClass class;
46 uint32 size;
47 uint32 x;
48
49 dwCost=0;
50 dwClasses = dwClassArrayAlloc();
51 dvForeachSchemaClass(schema, class) {
52 dwClassArrayAppendClass(dwClasses, class);
53 } dvEndSchemaClass;
54 size = dwClassArrayGetUsedClass(dwClasses);
55 size = size*size;
56 dwNumCols = dwClassArrayGetUsedClass(dwClasses);;
57 dwGrid = dwClassArrayAlloc();
58 for(x = 0; x < size; x++) {
59 dwClassArrayAppendClass(dwGrid, dvClassNull);
60 }
61 dwUndoX1 = UINT32_MAX;
62 dwUndoX2 = UINT32_MAX;
63 dwUndoY1 = UINT32_MAX;
64 dwUndoY2 = UINT32_MAX;
65 }
66
67 /*--------------------------------------------------------------------------------------------------
68 Free Globals.
69 --------------------------------------------------------------------------------------------------*/
close(void)70 static void close(void)
71 {
72 dwClassArrayFree(dwClasses);
73 dwClasses = dwClassArrayNull;
74 dwClassArrayFree(dwGrid);
75 dwGrid = dwClassArrayNull;
76 dwNumCols = UINT32_MAX;
77 dwUndoX1 = UINT32_MAX;
78 dwUndoX2 = UINT32_MAX;
79 dwUndoY1 = UINT32_MAX;
80 dwUndoY2 = UINT32_MAX;
81 }
82
83 /*--------------------------------------------------------------------------------------------------
84 Find the cost of relationships for classes within a schema
85 --------------------------------------------------------------------------------------------------*/
findRelationshipCost(dvRelationship relationship)86 uint32 findRelationshipCost(
87 dvRelationship relationship)
88 {
89 dvClass parentClass = dvRelationshipGetParentClass(relationship);
90 dvClass childClass = dvRelationshipGetChildClass(relationship);
91 int32 parentX = dwClassGetX(parentClass);
92 int32 parentY = dwClassGetY(parentClass);
93 int32 childX = dwClassGetX(childClass);
94 int32 childY = dwClassGetY(childClass);
95 uint32 relationshipCost = utAbs(parentX - childX) + utAbs(parentY - childY);
96
97 if(!dwClassAdded(parentClass)) {
98 return 0;
99 }
100 if(!dwClassAdded(childClass)) {
101 return 0;
102 }
103 return relationshipCost;
104 }
105
106 /*--------------------------------------------------------------------------------------------------
107 Find the cost of all the classes in relationship with a class
108 --------------------------------------------------------------------------------------------------*/
findClassCost(dvClass class)109 uint32 findClassCost(
110 dvClass class)
111 {
112 uint32 cost = 0;
113 dvRelationship relationship;
114
115 dvForeachClassParentRelationship(class,relationship) {
116 cost += findRelationshipCost(relationship);
117 } dvEndClassParentRelationship;
118 dvForeachClassChildRelationship(class,relationship) {
119 cost += findRelationshipCost(relationship);
120 } dvEndClassChildRelationship;
121 return cost;
122 }
123
124 /*--------------------------------------------------------------------------------------------------
125 Find the class at location X and Y
126 --------------------------------------------------------------------------------------------------*/
getGridXYClass(uint32 x,uint32 y)127 dvClass getGridXYClass(
128 uint32 x,
129 uint32 y)
130 {
131 uint32 index = y*dwNumCols + x;
132 dvClass class = dwClassArrayGetiClass(dwGrid, index);
133
134 return class;
135 }
136
137 /*--------------------------------------------------------------------------------------------------
138 Set the class at location X and Y
139 --------------------------------------------------------------------------------------------------*/
setGridXYClass(uint32 x,uint32 y,dvClass class)140 void setGridXYClass(
141 uint32 x,
142 uint32 y,
143 dvClass class)
144 {
145 uint32 index = y*dwNumCols + x;
146
147 dwClassArraySetiClass(dwGrid, index, class);
148 }
149
150 /*--------------------------------------------------------------------------------------------------
151 Updating cost while removing Class from a Grid
152 --------------------------------------------------------------------------------------------------*/
153
removeGridClass(dvClass class)154 void removeGridClass(
155 dvClass class)
156 {
157 uint32 classCost = findClassCost(class);
158 uint32 x = dwClassGetX(class);
159 uint32 y = dwClassGetY(class);
160
161 utAssert(getGridXYClass(x, y) == class);
162 utAssert(classCost <= dwCost);
163 utAssert(dwClassAdded(class));
164 setGridXYClass(x, y, dvClassNull);
165 dwClassSetAdded(class, false);
166 dwCost -= classCost;
167
168 }
169
170 /*--------------------------------------------------------------------------------------------------
171 Updating cost while adding Class to a Grid
172 --------------------------------------------------------------------------------------------------*/
addGridClass(dvClass class,uint32 x,uint32 y)173 void addGridClass(
174 dvClass class,
175 uint32 x,
176 uint32 y)
177 {
178 utAssert(dwClassAdded(class) == false);
179 utAssert(getGridXYClass(x,y) == dvClassNull);
180 setGridXYClass(x, y, class);
181 dwClassSetX(class, x);
182 dwClassSetY(class, y);
183 dwClassSetAdded(class, true);
184 dwCost += findClassCost(class);
185 }
186
187 /*--------------------------------------------------------------------------------------------------
188 Swapping classes between coordinates X1,Y1 and X2,Y2
189 --------------------------------------------------------------------------------------------------*/
190
SwapGridXY(uint32 x1,uint32 y1,uint32 x2,uint32 y2)191 void SwapGridXY(
192 uint32 x1,
193 uint32 y1,
194 uint32 x2,
195 uint32 y2)
196 {
197 dvClass temp1 = getGridXYClass(x1,y1);
198 dvClass temp2 = getGridXYClass(x2,y1);
199
200 if(temp1!=dvClassNull && temp2 == dvClassNull) {
201 removeGridClass(temp1);
202 addGridClass(temp1,x2,y2);
203 } else if(temp1==dvClassNull && temp2 != dvClassNull) {
204 removeGridClass(temp2);
205 addGridClass(temp2,x1,y1);
206 } else if(temp1!=dvClassNull && temp2 != dvClassNull) {
207 removeGridClass(temp1);
208 removeGridClass(temp2);
209 addGridClass(temp1,x2,y2);
210 addGridClass(temp2,x1,y1);
211 } else if (temp1==dvClassNull && temp2 == dvClassNull) {
212 }
213 }
214 /*--------------------------------------------------------------------------------------------------
215 Picking a Random Class
216 --------------------------------------------------------------------------------------------------*/
pickRandomClass(void)217 dvClass pickRandomClass(void)
218 {
219 uint32 classnum=dwClassArrayGetUsedClass(dwClasses);
220 dvClass class=getGridXYClass(utRandN(classnum),utRandN(classnum));
221
222 return class;
223 }
224
225
226 /*--------------------------------------------------------------------------------------------------
227 Function to make a Random Move
228 --------------------------------------------------------------------------------------------------*/
makeRandomMoveWithClass(dvClass class1)229 int32 makeRandomMoveWithClass(
230 dvClass class1)
231 {
232 uint32 x1 = dwClassGetX(class1);
233 uint32 y1 = dwClassGetY(class1);
234 uint32 x2 = utRandN(dwNumCols);
235 uint32 y2 = utRandN(dwNumCols);
236 int32 initialTemp=dwCost;
237 int32 deltaTemp = 0;
238
239 dwUndoX1 = x1;
240 dwUndoX2 = x2;
241 dwUndoY1 = y1;
242 dwUndoY2 = y2;
243 if ((x1 == x2) && (y1 == y2)) {
244 } else {
245 SwapGridXY(x1,y1,x2,y2);
246 deltaTemp = dwCost - initialTemp;
247 }
248 return deltaTemp;
249 }
250
251 /*--------------------------------------------------------------------------------------------------
252 Function to make a Random Move
253 --------------------------------------------------------------------------------------------------*/
anMakeRandomMove(void)254 int32 anMakeRandomMove(void)
255 {
256 dvClass class = pickRandomClass();
257
258 return makeRandomMoveWithClass(class);
259 }
260
261 /*--------------------------------------------------------------------------------------------------
262 Undoing a Move
263 --------------------------------------------------------------------------------------------------*/
264
anUndoMove(void)265 void anUndoMove(void)
266 {
267
268 if (dwUndoX1 == UINT32_MAX || dwUndoX2 == UINT32_MAX || dwUndoY1==UINT32_MAX || dwUndoY2==UINT32_MAX) {
269 }
270 else{
271 SwapGridXY(dwUndoX2,dwUndoX1,dwUndoY1,dwUndoY2);
272 dwUndoX1 = UINT32_MAX;
273 dwUndoX2 = UINT32_MAX;
274 dwUndoY1 = UINT32_MAX;
275 dwUndoY2 = UINT32_MAX; }
276 }
277
278 /*--------------------------------------------------------------------------------------------------
279 Initialize Systems
280 --------------------------------------------------------------------------------------------------*/
281
anInitializeSystem(uint32 * numElements)282 int32 anInitializeSystem(uint32 *numElements)
283 {
284 uint32 i=0;
285 dvClass class;
286
287 for (i=0; i<dwNumCols; i++) {
288 setGridXYClass(i,0,class);
289 }
290 *numElements=i;
291 return dwCost;
292 }
293 /*--------------------------------------------------------------------------------------------------
294 Function to randomize system
295 --------------------------------------------------------------------------------------------------*/
anRandomizeSystem(void)296 int32 anRandomizeSystem(void)
297 {
298 dvClass class;
299 uint32 i;
300
301 for(i = 0;i < dwNumCols;i++) {
302 class = dwClassArrayGetiClass(dwGrid, i);
303 makeRandomMoveWithClass(class);
304 }
305 return dwCost;
306 }
307
308 /*--------------------------------------------------------------------------------------------------
309 Simulated Annealing Function
310 --------------------------------------------------------------------------------------------------*/
311
312
313 /*--------------------------------------------------------------------------------------------------
314 Place classes on the schema.
315 --------------------------------------------------------------------------------------------------*/
316
dwPlaceSchema(dvSchema schema)317 void dwPlaceSchema(
318 dvSchema schema)
319 {
320 dvClass class;
321
322 init(schema);
323 anAnneal(0.9);
324 close();
325 }
326