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. */
6
#include "Gmsh_printf.h"
10
/* Refine a vertex separator by finding a maximum bipartite matching. */
12
static int bpm_improve1();
13
static double sep_cost();
15
void bpm_improve(graph, sets, goal, max_dev, bndy_list, weights, using_vwgts)
16
struct vtx_data **graph; /* list of graph info for each vertex */
17
short *sets; /* local partitioning of vtxs */
18
double *goal; /* desired set sizes */
19
int max_dev; /* largest deviation from balance allowed */
20
int **bndy_list; /* list of vertices on boundary (0 ends) */
21
double *weights; /* vertex weights in each set */
22
int using_vwgts; /* invoke weighted cover routines? */
24
extern int DEBUG_COVER; /* debug flag for min vertex cover */
25
extern int VERTEX_COVER; /* apply improvement once, or repeatedly? */
26
double ratio; /* fraction of non-separator vertices */
27
double deltaplus; /* amount set is too big */
28
double deltaminus; /* amount set is too small */
29
double imbalance; /* current amount of imbalance */
30
int set_big; /* side of graph I'm matching against */
31
int set_small; /* side of graph I'm not matching against */
32
int sep_size; /* separator size */
33
int sep_weight; /* weight of separator */
34
int change; /* does separator get improved? */
35
int i; /* loop counter */
40
while ((*bndy_list)[sep_size] != 0) {
45
for (i = 0; i < sep_size; i++) {
46
sep_weight += graph[(*bndy_list)[i]]->vwgt;
50
sep_weight = sep_size;
53
if (DEBUG_COVER > 1) {
54
printf("Before first matching, sep_size = %d, sep_weight = %d, Sizes = %g/%g\n",
55
sep_size, sep_weight, weights[0], weights[1]);
58
ratio = (weights[0] + weights[1]) / (goal[0] + goal[1]);
59
deltaplus = fabs(weights[0] - goal[0] * ratio);
60
deltaminus = fabs(weights[1] - goal[1] * ratio);
61
imbalance = deltaplus + deltaminus;
62
old_cost = sep_cost(weights[0], weights[1], (double) sep_weight, (double) max_dev);
67
/* First match towards the larger side, then the smaller. */
68
if (goal[0] - weights[0] >= goal[1] - weights[1]) {
77
change = bpm_improve1(graph, sets, bndy_list, weights, set_big, set_small,
78
goal, max_dev, &imbalance, &sep_size, &sep_weight,
79
using_vwgts, &old_cost);
82
printf("After big matching, sep_size = %d, sep_weight = %d, Sizes = %g/%g\n",
83
sep_size, sep_weight, weights[0], weights[1]);
85
if (VERTEX_COVER == 1)
89
/* If balanced, try the other direction. */
90
if (imbalance < max_dev) {
91
change = bpm_improve1(graph, sets, bndy_list, weights, set_small,
92
set_big, goal, max_dev, &imbalance, &sep_size, &sep_weight,
93
using_vwgts, &old_cost);
96
printf("After small matching, sep_size = %d, Sizes = %g/%g\n",
97
sep_size, weights[0], weights[1]);
103
printf("After all matchings, sep_size = %d, sep_weight = %d, Sizes = %g/%g\n\n",
104
sep_size, sep_weight, weights[0], weights[1]);
108
static int bpm_improve1(graph, sets, pbndy_list, weights, set_match, set_other,
109
goal, max_dev, pimbalance, sep_size, sep_weight, using_vwgts,
111
struct vtx_data **graph; /* list of graph info for each vertex */
112
short *sets; /* local partitioning of vtxs */
113
int **pbndy_list; /* list of vertices on boundary (0 ends) */
114
double *weights; /* vertex weights in each set */
115
int set_match; /* side of graph I'm matching against */
116
int set_other; /* side of graph I'm not matching against */
117
double *goal; /* desired set sizes */
118
int max_dev; /* largest deviation from balance allowed */
119
double *pimbalance; /* imbalance of current partition */
120
int *sep_size; /* separator size */
121
int *sep_weight; /* weight of separator */
122
int using_vwgts; /* use weighted model? */
123
double *pcost; /* cost of current separator */
125
extern int DEBUG_COVER; /* debug flag for min vertex cover */
126
double new_weights[2]; /* weights associated with new separator */
127
double ratio; /* fraction of non-separator vertices */
128
double deltaplus; /* amount set is too big */
129
double deltaminus; /* amount set is too small */
130
double new_imbalance; /* imbalance of new partition */
131
double new_cost; /* cost of new separator */
132
int *pointers; /* start/stop indices into adjacencies */
133
int *indices; /* adjacencies for each bipartite vertex */
134
int *vweight; /* vertex weights if needed */
135
int *loc2glob; /* mapping from bp graph to original */
136
int *new_bndy_list; /* new list of boundary vertices */
137
int old_sep_size; /* previous separator size */
138
int old_sep_weight; /* previous separator weight */
139
int vtx; /* vertex in graph */
140
int change; /* does this routine alter separator? */
141
int nleft, nright; /* # vtxs in two sides on bp graph */
142
int i, j; /* loop counter */
143
void make_bpgraph(), bpcover(), wbpcover();
144
double *smalloc(), fabs();
147
make_bpgraph(graph, sets, *pbndy_list, *sep_size, set_match, &pointers,
148
&indices, &vweight, &loc2glob, &nleft, &nright, using_vwgts);
150
old_sep_size = *sep_size;
151
old_sep_weight = *sep_weight;
153
new_bndy_list = (int *) smalloc((unsigned) (*sep_size + 1) * sizeof(int));
154
new_bndy_list[0] = nleft + nright;
155
bpcover(nleft, nright, pointers, indices, sep_size, new_bndy_list);
156
*sep_weight = *sep_size;
159
wbpcover(nleft, nright, pointers, indices, vweight, sep_size,
160
sep_weight, &new_bndy_list);
163
/* Update weights. */
164
new_weights[0] = weights[0];
165
new_weights[1] = weights[1];
166
for (j = 0; j < new_bndy_list[0]; j++) {
167
/* First handle nodes numbered less than separator nodes. */
169
if (sets[vtx] == 2) {
170
new_weights[set_other] += graph[vtx]->vwgt;
173
for (i = 0; i < *sep_size; i++) {
174
vtx = loc2glob[new_bndy_list[i]];
175
if (sets[vtx] == set_match) {
176
new_weights[set_match] -= graph[vtx]->vwgt;
179
for (j = new_bndy_list[i - 1] + 1; j < new_bndy_list[i]; j++) {
181
if (sets[vtx] == 2) {
182
new_weights[set_other] += graph[vtx]->vwgt;
187
if (*sep_size != 0) {
188
i = new_bndy_list[*sep_size - 1] + 1;
193
for (j = i; j < nleft + nright; j++) {
195
if (sets[vtx] == 2) {
196
new_weights[set_other] += graph[vtx]->vwgt;
201
/* Check to see if new partition is acceptably balanced. */
202
ratio = (new_weights[0] + new_weights[1]) / (goal[0] + goal[1]);
203
deltaplus = fabs(new_weights[0] - goal[0] * ratio);
204
deltaminus = fabs(new_weights[1] - goal[1] * ratio);
205
new_imbalance = deltaplus + deltaminus;
207
new_cost = sep_cost(weights[0], weights[1], (double) *sep_weight, (double) max_dev);
209
if (DEBUG_COVER > 1) {
210
printf("Sides %.0f, %.0f: sep %d total %.0f %.0f\n",
211
new_weights[0], new_weights[1], *sep_size,
212
new_weights[0] + new_weights[1],
213
new_weights[0] + new_weights[1] + *sep_size
217
/* if (new_cost < *pcost) { */
218
if ((new_cost < *pcost && new_imbalance <= max_dev) ||
219
(new_cost <= *pcost && new_imbalance < *pimbalance)) {
220
/* Update set values. */
223
for (j = 0; j < new_bndy_list[0]; j++) {
224
/* First handle nodes numbered less than separator nodes. */
226
if (sets[vtx] == 2) {
227
sets[vtx] = (short) set_other;
230
for (i = 0; i < *sep_size; i++) {
231
vtx = loc2glob[new_bndy_list[i]];
232
if (sets[vtx] == set_match) {
236
for (j = new_bndy_list[i - 1] + 1; j < new_bndy_list[i]; j++) {
238
if (sets[vtx] == 2) {
239
sets[vtx] = (short) set_other;
244
if (*sep_size != 0) {
245
i = new_bndy_list[*sep_size - 1] + 1;
250
for (j = i; j < nleft + nright; j++) {
252
if (sets[vtx] == 2) {
253
sets[vtx] = (short) set_other;
257
/* Restore bndy_list to global numbering. */
258
for (i = 0; i < *sep_size; i++) {
259
new_bndy_list[i] = loc2glob[new_bndy_list[i]];
262
new_bndy_list[*sep_size] = 0;
264
sfree((char *) *pbndy_list);
266
*pbndy_list = new_bndy_list;
267
*pimbalance = new_imbalance;
269
weights[0] = new_weights[0];
270
weights[1] = new_weights[1];
275
sfree((char *) new_bndy_list);
276
*sep_size = old_sep_size;
277
*sep_weight = old_sep_weight;
280
sfree((char *) vweight);
281
sfree((char *) loc2glob);
282
sfree((char *) indices);
283
sfree((char *) pointers);
289
/* Routine that can be modified to allow different cost functions. */
291
static double sep_cost(size1, size2, size_sep, max_dev)
292
double size1, size2; /* vertex weight in two partitions */
293
double size_sep; /* vertex weight of separator */
294
double max_dev; /* maximum allowed imbalance */
296
return ((double) size_sep);
added
removed
contrib/Chaco/klvspiff/bpm_improve.c
