Debian Codegraph @

packages/seacas/libraries/chaco/bpmatch/movevtxs.c

raw
1 /*
2 * Copyright(C) 1999-2020, 2022, 2023 National Technology & Engineering Solutions
3 * of Sandia, LLC (NTESS). Under the terms of Contract DE-NA0003525 with
4 * NTESS, the U.S. Government retains certain rights in this software.
5 *
6 * See packages/seacas/LICENSE for details
7 */
8
9 #include "defs.h" // for TRUE, FALSE, max, min
10 #include "params.h" // for MAXSETS
11 #include "structs.h" // for vtx_data
12
13 /* Enact a single move from largest (smallest) set in such a way
14 that some small (large) set gets bigger. */
15
16 int N_VTX_CHECKS; /* number of considered moves */
17 int N_VTX_MOVES; /* number of actual moves */
18 static void nextmove(int nvtxs, /* number of vertices in graph */
19 int nsets, /* how many sets am I dividing into? */
20 double *vals[][MAXSETS], /* values in sorted lists */
21 int *indices[][MAXSETS], /* indices that define order in sorted lists */
22 int startvtx[][MAXSETS], /* index values corresponding to splitter */
23 double *dist, /* distances defining splitter */
24 int *sets, /* set assignment for each vertex */
25 int toobig, /* is bad set too big or too small? */
26 int *active, /* flags sets trying to change size */
27 int *next_vtx, /* vertex selected to move next */
28 int *next_to, /* set vertex should be moved to */
29 double *next_delta /* size of change in distances */
30 );
31
32 static void undo_coupling(struct vtx_data **graph, /* data structure with vertex weights */
33 int *sets, /* sets each vertex is in */
34 int nsets, /* number of sets being divided into */
35 int from, int to, /* set final vertex moved from and to */
36 int toobig, /* are we shrinking or enlarging a set? */
37 int badset, /* the set number being shrunk or enlarged */
38 double *size /* sizes of the different sets */
39 );
40
41 static void couple(int nsets, /* number of sets being divided into */
42 int from, int to, /* sets to be coupled */
43 int vtx /* vertex that they share */
44 );
45
46 void movevtxs(struct vtx_data **graph, /* data structure with vertex weights */
47 int nvtxs, /* number of vertices in graph */
48 int nsets, /* how many sets am I dividing into? */
49 double *dist, /* distances defining splitter */
50 int *indices[][MAXSETS], /* indices that define order in sorted lists */
51 double *vals[][MAXSETS], /* values in sorted lists */
52 int startvtx[][MAXSETS], /* index values corresponding to splitter */
53 int *sets, /* set assignment for each vertex */
54 double *size, /* sizes of the different sets */
55 double *goal, /* desired set sizes */
56 int vwgt_max /* largest vertex weight */
57 )
58 {
59 double largest; /* largest overshoot from desired size */
60 double smallest; /* largest undershoot from desired size */
61 int active[MAXSETS]; /* flags sets trying to change size */
62 double delta; /* amount distances must change */
63 int vtx; /* vertex being moved */
64 int to, from; /* set vertex is being moved to/from */
65 int weight; /* weight of vertex being moved */
66 int done; /* have I successfully move a vertex? */
67
68 /* int npass=0; */ /* counts passes through main loop */
69 int badset = -1; /* most unbalanced set */
70 int toobig = 0; /* badset too large or too small? */
71 int balanced; /* is balance attained? */
72 double imbalance; /* amount of imbalance in badset */
73 int i; /* loop counter */
74
75 /* Find most unbalanced set. */
76
77 imbalance = largest = smallest = 0;
78 for (i = 0; i < nsets; i++) {
79 if (size[i] - goal[i] > largest) {
80 largest = size[i] - goal[i];
81 if (largest > imbalance) {
82 imbalance = largest;
83 badset = i;
84 toobig = 1;
85 }
86 }
87 else if (goal[i] - size[i] > smallest) {
88 smallest = goal[i] - size[i];
89 if (smallest > imbalance) {
90 imbalance = smallest;
91 badset = i;
92 toobig = -1;
93 }
94 }
95 }
96 if (largest + smallest <= vwgt_max) {
97 balanced = TRUE;
98 }
99 else {
100 balanced = FALSE;
101 }
102
103 /* If not balanced, change distances to move vertices between sets. */
104 while (!balanced) {
105 /* npass++; */
106 for (i = 0; i < nsets; i++) {
107 active[i] = FALSE;
108 }
109 active[badset] = TRUE;
110
111 done = FALSE;
112 while (!done) {
113 nextmove(nvtxs, nsets, vals, indices, startvtx, dist, sets, toobig, active, &vtx, &to,
114 &delta);
115 from = sets[vtx];
116 weight = graph[vtx]->vwgt;
117
118 /* Now adjust all active dists to reflect this move so far. */
119 for (i = 0; i < nsets; i++) {
120 if (active[i]) {
121 dist[i] -= toobig * delta;
122 }
123 }
124 if (toobig > 0) {
125 if (size[to] + weight - goal[to] < largest) {
126 done = TRUE;
127 size[from] -= graph[vtx]->vwgt;
128 size[to] += graph[vtx]->vwgt;
129 sets[vtx] = to;
130 undo_coupling(graph, sets, nsets, from, to, toobig, badset, size);
131 }
132 else {
133 couple(nsets, from, to, vtx);
134 active[to] = TRUE;
135 }
136 }
137 else {
138 if (goal[from] - (size[from] - weight) < smallest) {
139 done = TRUE;
140 size[from] -= graph[vtx]->vwgt;
141 size[to] += graph[vtx]->vwgt;
142 sets[vtx] = to;
143 undo_coupling(graph, sets, nsets, from, to, toobig, badset, size);
144 }
145 else {
146 couple(nsets, from, to, vtx);
147 active[from] = TRUE;
148 }
149 }
150 }
151
152 /* Find most unbalanced set. */
153 imbalance = largest = smallest = 0;
154 for (i = 0; i < nsets; i++) {
155 if (size[i] - goal[i] > largest) {
156 largest = size[i] - goal[i];
157 if (largest > imbalance) {
158 imbalance = largest;
159 badset = i;
160 toobig = 1;
161 }
162 }
163 else if (goal[i] - size[i] > smallest) {
164 smallest = goal[i] - size[i];
165 if (smallest > imbalance) {
166 imbalance = smallest;
167 badset = i;
168 toobig = -1;
169 }
170 }
171 }
172 if (largest + smallest <= vwgt_max) {
173 balanced = TRUE;
174 }
175 else {
176 balanced = FALSE;
177 }
178 }
179 }
180
181 /* Find the next move from an active to an inactive set, returning */
182 /* next_vtx, next_to, and distance. */
183 static void nextmove(int nvtxs, /* number of vertices in graph */
184 int nsets, /* how many sets am I dividing into? */
185 double *vals[][MAXSETS], /* values in sorted lists */
186 int *indices[][MAXSETS], /* indices that define order in sorted lists */
187 int startvtx[][MAXSETS], /* index values corresponding to splitter */
188 double *dist, /* distances defining splitter */
189 int *sets, /* set assignment for each vertex */
190 int toobig, /* is bad set too big or too small? */
191 int *active, /* flags sets trying to change size */
192 int *next_vtx, /* vertex selected to move next */
193 int *next_to, /* set vertex should be moved to */
194 double *next_delta /* size of change in distances */
195 )
196 {
197 double delta; /* amount distance must change */
198 double bestdelta; /* best value see so far */
199 int good; /* is this the delta OK? */
200 int first; /* is this the first OK delta I've seen? */
201 int maxset, minset; /* larger/smaller of two sets */
202 int bestfrom = 0, bestto = 0; /* sets best move comes from and goes to */
203 int bestdir = 0; /* direction to step in list for best move */
204 int bestvtx = 0; /* vertex being moved between sets */
205 int from, to; /* sets vertex wants to move from and to */
206 int index; /* offset into indices array */
207 int dir = 0; /* direction to step through list */
208 int i, j; /* loop counter */
209
210 bestdelta = 0;
211 first = TRUE;
212 while (first) {
213 for (i = 0; i < nsets; i++) {
214 if (active[i]) {
215 for (j = 0; j < nsets; j++) {
216 if (!active[j]) {
217 /* Look for next move from active set i to inactive set j. */
218 if (toobig > 0) {
219 from = i;
220 to = j;
221 }
222 else {
223 from = j;
224 to = i;
225 }
226 minset = min(to, from);
227 maxset = max(to, from);
228
229 index = startvtx[minset][maxset];
230 if (index >= nvtxs || index < 0) {
231 good = FALSE;
232 }
233 else {
234 if (j > i) {
235 dir = -1;
236 }
237 else {
238 dir = 1;
239 }
240 good = TRUE;
241 delta = -toobig * dir * vals[minset][maxset][indices[minset][maxset][index]] -
242 (dist[to] - dist[from]);
243 }
244
245 if (good && (first || delta < bestdelta)) {
246 /* Is this the best so far? */
247 first = FALSE;
248 bestdelta = delta;
249 bestfrom = from;
250 bestto = to;
251 bestdir = dir;
252 bestvtx = indices[minset][maxset][index] + 1;
253 }
254 }
255 }
256 }
257 }
258
259 /* Only accept a vertex if it's from the right set. */
260 if (sets[bestvtx] != bestfrom || (toobig > 0 && !active[bestfrom]) ||
261 (toobig < 0 && !active[bestto])) {
262 /* Set rejection flag, and increment startvtx pointer. */
263 first = TRUE;
264 minset = min(bestto, bestfrom);
265 maxset = max(bestto, bestfrom);
266 startvtx[minset][maxset] -= toobig * bestdir;
267 }
268 ++N_VTX_CHECKS;
269 }
270 *next_vtx = bestvtx;
271 *next_to = bestto;
272 *next_delta = bestdelta;
273 ++N_VTX_MOVES;
274 }
275
276 static int ncoupled = 0;
277 static int coupled_vtxs[MAXSETS];
278 static int coupled_sets[MAXSETS][MAXSETS];
279
280 static void couple(int nsets, /* number of sets being divided into */
281 int from, int to, /* sets to be coupled */
282 int vtx /* vertex that they share */
283 )
284 {
285 int i; /* loop counter */
286
287 /* Check for degenerate case of vertex shared by more than two sets. */
288 for (i = 0; i < ncoupled; i++) {
289 if (coupled_vtxs[i] == vtx) {
290 coupled_sets[i][from] = -1;
291 coupled_sets[i][to] = 1;
292 return;
293 }
294 }
295
296 coupled_vtxs[ncoupled] = vtx;
297 for (i = 0; i < nsets; i++) {
298 coupled_sets[ncoupled][i] = 0;
299 }
300 coupled_sets[ncoupled][from] = -1;
301 coupled_sets[ncoupled][to] = 1;
302 ++ncoupled;
303 }
304
305 static void undo_coupling(struct vtx_data **graph, /* data structure with vertex weights */
306 int *sets, /* sets each vertex is in */
307 int nsets, /* number of sets being divided into */
308 int from, int to, /* set final vertex moved from and to */
309 int toobig, /* are we shrinking or enlarging a set? */
310 int badset, /* the set number being shrunk or enlarged */
311 double *size /* sizes of the different sets */
312 )
313 {
314 int done; /* have enough vertices been moved? */
315 int found; /* have I found the right set? */
316 int vtx; /* vertex being moved between sets */
317 int i, j; /* loop counter */
318
319 if (ncoupled == 0) {
320 return;
321 }
322
323 if (toobig > 0) {
324 done = FALSE;
325 if (from == badset) {
326 done = TRUE;
327 }
328 while (!done) {
329 found = FALSE;
330 to = from;
331 for (i = 0; i < ncoupled && !found; i++) {
332 if (coupled_sets[i][from] == 1) { /* Found an edge into set. */
333 found = TRUE;
334 /* And find other end of edge. */
335 for (j = 0; j < nsets; j++) {
336 if (coupled_sets[i][j] == -1) {
337 from = j;
338 }
339 }
340
341 /* Switch the set for this vertex. */
342 vtx = coupled_vtxs[i];
343 size[from] -= graph[vtx]->vwgt;
344 size[to] += graph[vtx]->vwgt;
345 sets[vtx] = to;
346 coupled_sets[i][from] = 0;
347
348 if (from == badset) {
349 done = TRUE;
350 }
351 }
352 }
353 }
354 }
355 else {
356 done = FALSE;
357 if (to == badset) {
358 done = TRUE;
359 }
360 while (!done) {
361 found = FALSE;
362 from = to;
363 for (i = 0; i < ncoupled && !found; i++) {
364 if (coupled_sets[i][from] == -1) { /* Found an edge from set. */
365 found = TRUE;
366 /* And find other end of edge. */
367 for (j = 0; j < nsets; j++) {
368 if (coupled_sets[i][j] == 1) {
369 to = j;
370 }
371 }
372
373 /* Switch the set for this vertex. */
374 vtx = coupled_vtxs[i];
375 size[from] -= graph[vtx]->vwgt;
376 size[to] += graph[vtx]->vwgt;
377 sets[vtx] = to;
378 coupled_sets[i][to] = 0;
379
380 if (to == badset) {
381 done = TRUE;
382 }
383 }
384 }
385 }
386 }
387
388 ncoupled = 0;
389 }