Debian Codegraph @

packages/seacas/libraries/chaco/internal/improve_internal.c

raw
1 /*
2 * Copyright(C) 1999-2020 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"
10 #include "internal.h"
11 #include "structs.h"
12 #include <stdio.h>
13
14 int improve_internal(struct vtx_data **graph, /* graph data structure */
15 int nvtxs, /* number of vertices in graph */
16 int *assign, /* current assignment */
17 double *goal, /* desired set sizes */
18 struct bidint *int_list, /* sorted list of internal vtx values */
19 struct bidint *set_list, /* headers of vtx_elems lists */
20 struct bidint *vtx_elems, /* lists of vtxs in each set */
21 int set1, /* set to try to improve */
22 int *locked, /* indicates vertices not allowed to move */
23 int *nlocked, /* number of vertices that can't move */
24 int using_ewgts, /* are edge weights being used? */
25 int vwgt_max, /* largest vertex weight */
26 int *total_vwgt /* total vertex weight in each set */
27 )
28 {
29 struct bidint *move_list; /* list of vertices changing sets */
30 struct bidint *ptr, *ptr2; /* loop through bidints */
31 struct bidint *changed_sets; /* list of sets that were modified */
32 double vwgt_avg = 0.0; /* average vertex weight in current set */
33 double degree_avg = 0.0; /* average vertex degree in current set */
34 double frac = .4; /* fraction of neighbors acceptable to move. */
35 double cost, min_cost; /* cost of making a vertex internal */
36 double min_cost_start; /* larger than any possible cost */
37 double cost_limit; /* acceptable cost of internalization */
38 double ratio; /* possible wgt / desired wgt */
39 float ewgt; /* weight of an edge */
40 int set2, set3; /* sets of two vertices */
41 int vtx, best_vtx = -1; /* vertex to make internal */
42 int move_vtx = -1; /* vertex to move between sets */
43 int neighbor; /* neighbor of a vertex */
44 int nguys = 0; /* number of vertices in current set */
45 int internal; /* is a vertex internal or not? */
46 int balanced; /* are two sets balanced? */
47 int flag; /* did I improve things: return code */
48 int size; /* array spacing */
49 int i, j; /* loop counters */
50
51 /* First find best candidate vertex to internalize. */
52 /* This is vertex which is already most nearly internal. */
53 min_cost_start = 2.0 * vwgt_max * nvtxs;
54 min_cost = min_cost_start;
55 size = (int)(&(vtx_elems[1]) - &(vtx_elems[0]));
56 for (ptr = set_list[set1].next; ptr != NULL; ptr = ptr->next) {
57 ++nguys;
58 vtx = ((int)(ptr - vtx_elems)) / size;
59 vwgt_avg += graph[vtx]->vwgt;
60 degree_avg += (graph[vtx]->nedges - 1);
61 cost = 0;
62 for (i = 1; i < graph[vtx]->nedges; i++) {
63 neighbor = graph[vtx]->edges[i];
64 set2 = assign[neighbor];
65 if (set2 != set1) {
66 if (locked[neighbor]) {
67 cost = min_cost_start;
68 }
69 else {
70 cost += graph[neighbor]->vwgt;
71 }
72 }
73 }
74 if (cost == 0) { /* Lock vertex and all it's neighbors. */
75 for (i = 1; i < graph[vtx]->nedges; i++) {
76 neighbor = graph[vtx]->edges[i];
77 if (!locked[neighbor]) {
78 locked[neighbor] = TRUE;
79 ++(*nlocked);
80 }
81 }
82 }
83
84 if (cost < min_cost && cost != 0) {
85 min_cost = cost;
86 best_vtx = vtx;
87 }
88 }
89
90 if (nguys > 0) {
91 vwgt_avg /= nguys;
92 degree_avg /= nguys;
93 }
94 cost_limit = frac * vwgt_avg * degree_avg;
95
96 if (min_cost > cost_limit) {
97 return (FALSE);
98 }
99
100 /* Lock the candidate vertex in current set */
101 if (!locked[best_vtx]) {
102 locked[best_vtx] = TRUE;
103 ++(*nlocked);
104 }
105
106 /* Also lock all his neighbors in set. */
107 for (i = 1; i < graph[best_vtx]->nedges; i++) {
108 neighbor = graph[best_vtx]->edges[i];
109 set2 = assign[neighbor];
110 if (set1 == set2 && !locked[neighbor]) {
111 locked[neighbor] = TRUE;
112 ++(*nlocked);
113 }
114 vtx_elems[neighbor].val = set1;
115 }
116
117 ewgt = 1;
118 move_list = NULL;
119
120 /* Now move neighbors of best_vtx to set1. */
121 for (i = 1; i < graph[best_vtx]->nedges; i++) {
122 neighbor = graph[best_vtx]->edges[i];
123 set2 = assign[neighbor];
124 if (set2 != set1) {
125 /* Add vertex to list of guys to move to set1. */
126 /* Don't move it yet in case I get stuck later. */
127 /* But change his assignment so that swapping vertex has current info. */
128 /* Note: This will require me to undo changes if I fail. */
129
130 locked[neighbor] = TRUE;
131 ++(*nlocked);
132
133 /* Remove him from his set list. */
134 if (vtx_elems[neighbor].next != NULL) {
135 vtx_elems[neighbor].next->prev = vtx_elems[neighbor].prev;
136 }
137 if (vtx_elems[neighbor].prev != NULL) {
138 vtx_elems[neighbor].prev->next = vtx_elems[neighbor].next;
139 }
140
141 /* Put him in list of moved vertices */
142 vtx_elems[neighbor].next = move_list;
143 vtx_elems[neighbor].val = set2;
144 move_list = &(vtx_elems[neighbor]);
145 assign[neighbor] = set1;
146
147 total_vwgt[set2] -= graph[neighbor]->vwgt;
148 total_vwgt[set1] += graph[neighbor]->vwgt;
149 }
150 }
151
152 /* Now check if vertices need to be handed back to restore balance. */
153 flag = TRUE;
154 for (i = 1; i < graph[best_vtx]->nedges && flag; i++) {
155 neighbor = graph[best_vtx]->edges[i];
156 set2 = vtx_elems[neighbor].val;
157 if (set2 != set1) {
158 ratio = (total_vwgt[set1] + total_vwgt[set2]) / (goal[set1] + goal[set2]);
159 balanced = (total_vwgt[set1] - goal[set1] * ratio + goal[set2] * ratio - total_vwgt[set2]) <=
160 vwgt_max;
161 while (!balanced && flag) {
162 /* Find a vertex to move back to set2. Use a KL metric. */
163 min_cost = min_cost_start;
164
165 for (ptr = set_list[set1].next; ptr != NULL; ptr = ptr->next) {
166 vtx = ((int)(ptr - vtx_elems)) / size;
167 if (!locked[vtx]) {
168 cost = 0;
169 for (j = 1; j < graph[vtx]->nedges; j++) {
170 neighbor = graph[vtx]->edges[j];
171 if (using_ewgts) {
172 ewgt = graph[vtx]->ewgts[j];
173 }
174 set3 = assign[neighbor];
175 if (set3 == set1) {
176 cost += ewgt;
177 }
178 else if (set3 == set2) {
179 cost -= ewgt;
180 }
181 }
182 if (cost < min_cost) {
183 min_cost = cost;
184 move_vtx = vtx;
185 }
186 }
187 }
188 if (min_cost >= min_cost_start) {
189 flag = FALSE;
190 }
191 else {
192 /* Add move_vtx to list of guys to move to set2. */
193 /* Don't move it yet in case I get stuck later. */
194 /* But change assign so later decisions have up-to-date info. */
195 if (vtx_elems[move_vtx].next != NULL) {
196 vtx_elems[move_vtx].next->prev = vtx_elems[move_vtx].prev;
197 }
198 if (vtx_elems[move_vtx].prev != NULL) {
199 vtx_elems[move_vtx].prev->next = vtx_elems[move_vtx].next;
200 }
201 vtx_elems[move_vtx].next = move_list;
202 vtx_elems[move_vtx].val = -(set2 + 1);
203 move_list = &(vtx_elems[move_vtx]);
204 assign[move_vtx] = set2;
205
206 total_vwgt[set2] += graph[move_vtx]->vwgt;
207 total_vwgt[set1] -= graph[move_vtx]->vwgt;
208 }
209 balanced = total_vwgt[set1] - goal[set1] + goal[set2] - total_vwgt[set2] <= vwgt_max;
210 }
211 }
212 }
213
214 if (!flag) {
215 /* Can't rebalance sets. Give up, but first restore the data structures. */
216 /* These include vtx_lists, total_vwgts and assign. */
217
218 for (ptr = move_list; ptr != NULL;) {
219 ptr2 = ptr->next;
220 vtx = ((int)(ptr - vtx_elems)) / size;
221 if (ptr->val >= 0) { /* Almost moved from set2 to set1. */
222 set2 = ptr->val;
223 assign[vtx] = set2;
224 total_vwgt[set2] += graph[vtx]->vwgt;
225 total_vwgt[set1] -= graph[vtx]->vwgt;
226 locked[vtx] = FALSE;
227 --(*nlocked);
228 }
229 else { /* Almost moved from set1 to set2. */
230 set2 = -(ptr->val + 1);
231 assign[vtx] = set1;
232 total_vwgt[set2] -= graph[vtx]->vwgt;
233 total_vwgt[set1] += graph[vtx]->vwgt;
234 set2 = set1;
235 }
236
237 /* Now add vertex back into its old vtx_list (now indicated by set2) */
238 ptr->next = set_list[set2].next;
239 if (ptr->next != NULL) {
240 ptr->next->prev = ptr;
241 }
242 ptr->prev = &(set_list[set2]);
243 set_list[set2].next = ptr;
244
245 ptr = ptr2;
246 }
247 return (FALSE);
248 }
249
250 /* Now perform actual moves. */
251 /* First, update assignment and place vertices into their new sets. */
252 changed_sets = NULL;
253 for (ptr = move_list; ptr != NULL;) {
254 ptr2 = ptr->next;
255 vtx = ((int)(ptr - vtx_elems)) / size;
256 if (ptr->val >= 0) {
257 set2 = set1;
258 }
259 else {
260 set2 = -(ptr->val + 1);
261 }
262
263 ptr->next = set_list[set2].next;
264 if (ptr->next != NULL) {
265 ptr->next->prev = ptr;
266 }
267 ptr->prev = &(set_list[set2]);
268 set_list[set2].next = ptr;
269
270 /* Pull int_list[set2] out of its list to be used later. */
271 if (ptr->val >= 0) {
272 set2 = ptr->val;
273 }
274 if (int_list[set2].val >= 0) {
275 int_list[set2].val = -(int_list[set2].val + 1);
276 if (int_list[set2].next != NULL) {
277 int_list[set2].next->prev = int_list[set2].prev;
278 }
279 if (int_list[set2].prev != NULL) {
280 int_list[set2].prev->next = int_list[set2].next;
281 }
282
283 int_list[set2].next = changed_sets;
284 changed_sets = &(int_list[set2]);
285 }
286 ptr = ptr2;
287 }
288 if (int_list[set1].val >= 0) {
289 if (int_list[set1].next != NULL) {
290 int_list[set1].next->prev = int_list[set1].prev;
291 }
292 if (int_list[set1].prev != NULL) {
293 int_list[set1].prev->next = int_list[set1].next;
294 }
295
296 int_list[set1].next = changed_sets;
297 changed_sets = &(int_list[set1]);
298 }
299
300 /* Finally, update internal node calculations for all modified sets. */
301 while (changed_sets != NULL) {
302 set2 = ((int)(changed_sets - int_list)) / size;
303 changed_sets = changed_sets->next;
304
305 /* Next line uses fact that list has dummy header so prev isn't NULL. */
306 int_list[set2].next = int_list[set2].prev->next;
307 int_list[set2].val = 0;
308 /* Recompute internal nodes for this set */
309 for (ptr = set_list[set2].next; ptr != NULL; ptr = ptr->next) {
310 vtx = ((int)(ptr - vtx_elems)) / size;
311 internal = TRUE;
312 for (j = 1; j < graph[vtx]->nedges && internal; j++) {
313 set3 = assign[graph[vtx]->edges[j]];
314 internal = (set3 == set2);
315 }
316 if (internal) {
317 int_list[set2].val += graph[vtx]->vwgt;
318 }
319 }
320
321 /* Now move internal value in doubly linked list. */
322 /* Move higher in list? */
323 while (int_list[set2].next != NULL && int_list[set2].val >= int_list[set2].next->val) {
324 int_list[set2].prev = int_list[set2].next;
325 int_list[set2].next = int_list[set2].next->next;
326 }
327 /* Move lower in list? */
328 while (int_list[set2].prev != NULL && int_list[set2].val < int_list[set2].prev->val) {
329 int_list[set2].next = int_list[set2].prev;
330 int_list[set2].prev = int_list[set2].prev->prev;
331 }
332
333 if (int_list[set2].next != NULL) {
334 int_list[set2].next->prev = &(int_list[set2]);
335 }
336 if (int_list[set2].prev != NULL) {
337 int_list[set2].prev->next = &(int_list[set2]);
338 }
339 }
340 return (TRUE);
341 }