← Back to branch summary

~ubuntu-branches/debian/squeeze/gmsh/squeeze

« back to all changes in this revision

Viewing changes to contrib/Chaco/internal/improve_internal.c

  • Committer: Bazaar Package Importer
  • Author(s): Christophe Prud'homme
  • Date: 2009-01-07 16:02:08 UTC
  • mfrom: (5.1.2 sid)
  • Revision ID: james.westby@ubuntu.com-20090107160208-vklhtj69br5yw5bh
Tags: 2.2.6.dfsg-2
* debian/control: fixed lintian warning "debhelper-but-no-misc-depends"
* debian/watch: fixed lintian warning
  "debian-watch-file-should-mangle-version"

Show diffs side-by-side

added added

removed removed

Lines of Context:
contrib/Chaco/internal/improve_internal.c
 
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
 
 
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
}