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