← Back to branch summary

~chaffra/+junk/trilinos

« back to all changes in this revision

Viewing changes to packages/zoltan/src/util/converters_for_JPDC_adaptive_mesh_experiments/exo2chaco/chaco/connect/connect_enforce.c

  • Committer: Bazaar Package Importer
  • Author(s): Christophe Prud'homme, Christophe Prud'homme, Johannes Ring
  • Date: 2009-12-13 12:53:22 UTC
  • mfrom: (5.1.2 sid)
  • Revision ID: james.westby@ubuntu.com-20091213125322-in0nrdjc55deqsw9
Tags: 10.0.3.dfsg-1
[Christophe Prud'homme]
* New upstream release

[Johannes Ring]
* debian/patches/libname.patch: Add prefix 'libtrilinos_' to all
  libraries. 
* debian/patches/soname.patch: Add soversion to libraries.
* debian/watch: Update download URL.
* debian/control:
  - Remove python-numeric from Build-Depends (virtual package).
  - Remove automake and autotools from Build-Depends and add cmake to
    reflect switch to CMake.
  - Add python-support to Build-Depends.
* debian/rules: 
  - Cleanup and updates for switch to CMake.

Show diffs side-by-side

added added

removed removed

Lines of Context:
packages/zoltan/src/util/converters_for_JPDC_adaptive_mesh_experiments/exo2chaco/chaco/connect/connect_enforce.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 <stdlib.h>
 
7
#include "defs.h"
 
8
#include "structs.h"
 
9
#include "smalloc.h"
 
10
 
 
11
/* Move vertices between domains to ensure each domain is connected. */
 
12
/* Note: This will likely result in load imbalance. */
 
13
 
 
14
void      connect_enforce(graph, nvtxs, using_ewgts, assignment, goal, nsets_tot,
 
15
                          total_move, max_move)
 
16
struct vtx_data **graph;        /* data structure for graph */
 
17
int       nvtxs;                /* number of vertices in full graph */
 
18
int       using_ewgts;          /* are edge weights being used? */
 
19
short    *assignment;           /* set number of each vtx (length n) */
 
20
double   *goal;                 /* desired sizes for each set */
 
21
int       nsets_tot;            /* total number sets created */
 
22
int      *total_move;           /* total number of vertices moved */
 
23
int      *max_move;             /* largest connected component moved */
 
24
{
 
25
    struct vtx_data **subgraph; /* data structure for domain graph */
 
26
    int       subnvtxs;         /* number of vertices in a domain */
 
27
    int       subnedges;        /* number of edges in a domain */
 
28
    struct heap *heap;          /* data structure for sorting set sizes */
 
29
    int      *heap_map;         /* pointers from sets to heap locations */
 
30
    int      *list_ptrs;        /* header of vtx list for each domain */
 
31
    int      *setlists;         /* linked list of vtxs for each domain */
 
32
    int      *vtxlist;          /* space for breadth first search list */
 
33
    int      *comp_lists;       /* list of vtxs in each connected comp */
 
34
    int      *clist_ptrs;       /* pointers to heads of comp_lists */
 
35
    short    *subsets;          /* list of active domains (all of them) */
 
36
    short    *subsets2;         /* list of active domains (all of them) */
 
37
    double   *set_size;         /* weighted sizes of different partitions */
 
38
    double    size;             /* size of subset being moved to new domain */
 
39
    int      *bndy_list;        /* list of domains adjacent to component */
 
40
    double   *bndy_size;        /* size of these boundaries */
 
41
    double   *comp_size;        /* sizes of different connected components */
 
42
    double    comp_size_max;    /* size of largest connected component */
 
43
    int       comp_max_index;   /* which component is largest? */
 
44
    int      *glob2loc;         /* global to domain renumbering */
 
45
    int      *loc2glob;         /* domain to global renumbering */
 
46
    short    *degree;           /* number of neighbors of a vertex */
 
47
    short    *comp_flag;        /* component number for each vtx */
 
48
    double    ewgt;             /* edge weight */
 
49
    int       nbndy;            /* number of sets adjecent to component */
 
50
    int       domain;           /* which subdomain I'm working on */
 
51
    int       new_domain;       /* subdomain to move some vertices to */
 
52
    double    max_bndy;         /* max connectivity to other domain */
 
53
    int       ncomps;           /* number of connected components */
 
54
    int       change;           /* how many vertices change set? */
 
55
    int       max_change;       /* largest subset moved together */
 
56
    int       vtx;              /* vertex in a connected component */
 
57
    int       set;              /* set a neighboring vertex is in */
 
58
    int       i, j, k, l;       /* loop counters */
 
59
    double    heap_extract_max();
 
60
    int       make_maps(), find_comps();
 
61
    void      make_setlists(), make_subgraph(), remake_graph();
 
62
    void      heap_build(), heap_update_val();
 
63
 
 
64
    change = 0;
 
65
    max_change = 0;
 
66
 
 
67
    /* Allocate space & initialize some values. */
 
68
 
 
69
    set_size = smalloc(nsets_tot * sizeof(double));
 
70
    bndy_size = smalloc(nsets_tot * sizeof(double));
 
71
    bndy_list = smalloc(nsets_tot * sizeof(int));
 
72
 
 
73
    setlists = smalloc((nvtxs + 1) * sizeof(int));
 
74
    list_ptrs = smalloc(nsets_tot * sizeof(int));
 
75
 
 
76
    glob2loc = smalloc((nvtxs + 1) * sizeof(int));
 
77
    loc2glob = smalloc((nvtxs + 1) * sizeof(int));
 
78
    subsets = smalloc(nsets_tot * sizeof(short));
 
79
    heap = (struct heap *)
 
80
        smalloc((nsets_tot + 1) * sizeof(struct heap));
 
81
    heap_map = smalloc(nsets_tot * sizeof(int));
 
82
 
 
83
    for (i = 0; i < nsets_tot; i++) {
 
84
        set_size[i] = 0;
 
85
        bndy_list[i] = 0;
 
86
        bndy_size[i] = 0;
 
87
        subsets[i] = i;
 
88
    }
 
89
 
 
90
    for (i = 1; i <= nvtxs; i++) {
 
91
        set_size[assignment[i]] += graph[i]->vwgt;
 
92
    }
 
93
 
 
94
    for (i = 0; i < nsets_tot; i++) {
 
95
        heap[i+1].tag = i;
 
96
        heap[i+1].val = set_size[i] - goal[i];
 
97
    }
 
98
 
 
99
    make_setlists(setlists, list_ptrs, nsets_tot, subsets, assignment,
 
100
                  NULL, nvtxs, TRUE);
 
101
 
 
102
   heap_build(heap, nsets_tot, heap_map);
 
103
 
 
104
    for (i = 0; i < nsets_tot; i++) {
 
105
        /* Find largest remaining set to work on next */
 
106
        size = heap_extract_max(heap, nsets_tot - i, &domain, heap_map);
 
107
 
 
108
        /* Construct subdomain graph. */
 
109
        subnvtxs = make_maps(setlists, list_ptrs, domain, glob2loc,
 
110
                             loc2glob);
 
111
        if (subnvtxs > 1) {
 
112
 
 
113
            subgraph = (struct vtx_data **)
 
114
               smalloc((subnvtxs + 1) * sizeof(struct vtx_data *));
 
115
            degree = smalloc((subnvtxs + 1) * sizeof(short));
 
116
 
 
117
            make_subgraph(graph, subgraph, subnvtxs, &subnedges, assignment,
 
118
                          domain, glob2loc, loc2glob, degree, using_ewgts);
 
119
 
 
120
            /* Find connected components. */
 
121
            comp_flag = smalloc((subnvtxs + 1) * sizeof(short));
 
122
            vtxlist = smalloc(subnvtxs * sizeof(int));
 
123
            ncomps = find_comps(subgraph, subnvtxs, comp_flag, vtxlist);
 
124
            sfree(vtxlist);
 
125
 
 
126
            /* Restore original graph */
 
127
            remake_graph(subgraph, subnvtxs, loc2glob, degree, using_ewgts);
 
128
            sfree(degree);
 
129
            sfree(subgraph);
 
130
 
 
131
            if (ncomps > 1) {
 
132
 
 
133
                /* Figure out sizes of components */
 
134
                comp_size = smalloc(ncomps * sizeof(double));
 
135
                for (j = 0; j < ncomps; j++) {
 
136
                    comp_size[j] = 0;
 
137
                }
 
138
                for (j = 1; j <= subnvtxs; j++) {
 
139
                    comp_size[comp_flag[j]] += graph[loc2glob[j]]->vwgt;
 
140
                }
 
141
                comp_size_max = 0;
 
142
                for (j = 0; j < ncomps; j++) {
 
143
                    if (comp_size[j] > comp_size_max) {
 
144
                        comp_size_max = comp_size[j];
 
145
                        comp_max_index = j;
 
146
                    }
 
147
                }
 
148
                for (j = 0; j < ncomps; j++) {
 
149
                    if (j != comp_max_index) {
 
150
                        change += comp_size[j];
 
151
                        if (comp_size[j] > max_change) max_change = comp_size[j];
 
152
                    }
 
153
                }
 
154
                sfree(comp_size);
 
155
 
 
156
                /* Make data structures for traversing components */
 
157
                comp_lists = smalloc((subnvtxs + 1) * sizeof(int));
 
158
                clist_ptrs = smalloc(ncomps * sizeof(int));
 
159
                if (ncomps > nsets_tot) {
 
160
                    subsets2 = smalloc(ncomps * sizeof(short));
 
161
                    for (j = 0; j < ncomps; j++) subsets2[j] = j;
 
162
                }
 
163
                else subsets2 = subsets;
 
164
                make_setlists(comp_lists, clist_ptrs, ncomps, subsets2, comp_flag,
 
165
                              NULL, subnvtxs, TRUE);
 
166
                if (ncomps > nsets_tot) {
 
167
                    sfree(subsets2);
 
168
                }
 
169
 
 
170
                /* Move all but the largest component. */
 
171
                ewgt = 1;
 
172
                for (j = 0; j < ncomps; j++)
 
173
                    if (j != comp_max_index) {
 
174
 
 
175
                        /* Figure out to which other domain it is most connected. */
 
176
                        nbndy = 0;
 
177
                        k = clist_ptrs[j];
 
178
                        while (k != 0) {
 
179
                            vtx = loc2glob[k];
 
180
                            for (l = 1; l <= graph[vtx]->nedges; l++) {
 
181
                                set = assignment[graph[vtx]->edges[l]];
 
182
                                if (set != domain) {
 
183
                                    if (bndy_size[set] == 0)
 
184
                                        bndy_list[nbndy++] = set;
 
185
                                    if (using_ewgts)
 
186
                                        ewgt = graph[vtx]->ewgts[l];
 
187
                                    bndy_size[set] += ewgt;
 
188
                                }
 
189
                            }
 
190
 
 
191
                            k = comp_lists[k];
 
192
                        }
 
193
 
 
194
                        /* Select a new domain. */
 
195
                        /* Instead of just big boundary, penalize too-large sets. */
 
196
                        /* Could be more aggressive to improve balance. */
 
197
                        max_bndy = 0;
 
198
                        new_domain = -1;
 
199
                        for (k = 0; k < nbndy; k++) {
 
200
                            l = bndy_list[k];
 
201
                            if (bndy_size[l] * goal[l] / (set_size[l] + 1) > max_bndy) {
 
202
                                new_domain = bndy_list[k];
 
203
                                max_bndy = bndy_size[l] * goal[l] / (set_size[l] + 1);
 
204
                            }
 
205
                        }
 
206
                        if (new_domain == -1) {
 
207
                            printf("Error in connect_enforce: new_domain = -1.  Disconnected graph?\n");
 
208
                            new_domain = domain;
 
209
                        }
 
210
 
 
211
                        /* Clear bndy_size array */
 
212
                        for (k = 0; k < nbndy; k++)
 
213
                            bndy_size[bndy_list[k]] = 0;
 
214
 
 
215
                        k = clist_ptrs[j];
 
216
 
 
217
                        size = 0;
 
218
 
 
219
                        while (k != 0) {
 
220
                            vtx = loc2glob[k];
 
221
                            assignment[vtx] = new_domain;
 
222
                            size += graph[vtx]->vwgt;
 
223
 
 
224
                            /* Finally, update setlists and list_ptrs */
 
225
                            /* Note: current domain setlist now bad, but not used
 
226
                               again */
 
227
                            setlists[vtx] = list_ptrs[new_domain];
 
228
                            list_ptrs[new_domain] = vtx;
 
229
 
 
230
                            k = comp_lists[k];
 
231
                        }
 
232
/*
 
233
printf("Updating set %d (from %d) to size %g\n", new_domain, domain,
 
234
set_size[new_domain] + size - goal[new_domain]);
 
235
*/
 
236
                        if (heap_map[new_domain] > 0) {
 
237
                            set_size[new_domain] += size;
 
238
                            heap_update_val(heap, heap_map[new_domain],
 
239
                                set_size[new_domain] - goal[new_domain], heap_map);
 
240
                        }
 
241
                    }
 
242
 
 
243
                sfree(clist_ptrs);
 
244
                sfree(comp_lists);
 
245
            }
 
246
            sfree(comp_flag);
 
247
        }
 
248
    }
 
249
 
 
250
    sfree(heap_map);
 
251
    sfree(heap);
 
252
    sfree(subsets);
 
253
    sfree(loc2glob);
 
254
    sfree(glob2loc);
 
255
    sfree(list_ptrs);
 
256
    sfree(setlists);
 
257
    sfree(bndy_list);
 
258
    sfree(bndy_size);
 
259
    sfree(set_size);
 
260
 
 
261
    *total_move = change;
 
262
    *max_move = max_change;
 
263
}