31 switch (ctrl->
IType) {
39 errexit(
"Unknown initial partition type: %d\n", ctrl->
IType);
84 int i, j, k, nvtxs, drain, nleft, first, last, pwgts[2], minpwgt[2], maxpwgt[2], from, bestcut, icut, mincut, me, pass, nbfs;
85 idxtype *xadj, *vwgt, *adjncy, *adjwgt, *where;
86 idxtype *queue, *touched, *gain, *bestwhere;
98 bestwhere =
idxmalloc(nvtxs,
"BisectGraph: bestwhere");
99 queue =
idxmalloc(nvtxs,
"BisectGraph: queue");
100 touched =
idxmalloc(nvtxs,
"BisectGraph: touched");
102 ASSERTP(tpwgts[0]+tpwgts[1] ==
idxsum(nvtxs, vwgt), (
"%d %d\n", tpwgts[0]+tpwgts[1],
idxsum(nvtxs, vwgt)));
104 maxpwgt[0] = ubfactor*tpwgts[0];
105 maxpwgt[1] = ubfactor*tpwgts[1];
106 minpwgt[0] = (1.0/ubfactor)*tpwgts[0];
107 minpwgt[1] = (1.0/ubfactor)*tpwgts[1];
111 for (; nbfs>0; nbfs--) {
112 idxset(nvtxs, 0, touched);
114 pwgts[1] = tpwgts[0]+tpwgts[1];
120 touched[queue[0]] = 1;
128 if (nleft == 0 || drain)
132 for (i=0; i<nvtxs; i++) {
133 if (touched[i] == 0) {
143 first = 0; last = 1;;
148 if (pwgts[0] > 0 && pwgts[1]-vwgt[i] < minpwgt[1]) {
154 INC_DEC(pwgts[0], pwgts[1], vwgt[i]);
155 if (pwgts[1] <= maxpwgt[1])
159 for (j=xadj[i]; j<xadj[i+1]; j++) {
161 if (touched[k] == 0) {
173 INC_DEC(pwgts[1], pwgts[0], vwgt[i]);
188 if (bestcut > graph->
mincut) {
190 idxcopy(nvtxs, where, bestwhere);
197 idxcopy(nvtxs, bestwhere, where);
212 int i, j, k, nvtxs, drain, nleft, first, last, pwgts[2], tpwgts[2], minpwgt[2], maxpwgt[2], from, bestcut, icut, mincut, me, pass, nbfs;
213 idxtype *xadj, *vwgt, *adjncy, *adjwgt, *where, *bndind;
214 idxtype *queue, *touched, *gain, *bestwhere;
216 nvtxs = graph->
nvtxs;
222 bestwhere =
idxmalloc(nvtxs,
"BisectGraph: bestwhere");
223 queue =
idxmalloc(nvtxs,
"BisectGraph: queue");
224 touched =
idxmalloc(nvtxs,
"BisectGraph: touched");
226 tpwgts[0] =
idxsum(nvtxs, vwgt);
227 tpwgts[1] = tpwgts[0]/2;
228 tpwgts[0] -= tpwgts[1];
230 maxpwgt[0] = ubfactor*tpwgts[0];
231 maxpwgt[1] = ubfactor*tpwgts[1];
232 minpwgt[0] = (1.0/ubfactor)*tpwgts[0];
233 minpwgt[1] = (1.0/ubfactor)*tpwgts[1];
236 graph->
rdata =
idxmalloc(5*nvtxs+3,
"GrowBisectionNode: graph->rdata");
242 graph->
id = graph->
rdata + 3*nvtxs + 3;
243 graph->
ed = graph->
rdata + 4*nvtxs + 3;
245 where = graph->
where;
249 bestcut = tpwgts[0]+tpwgts[1];
250 for (nbfs++; nbfs>0; nbfs--) {
251 idxset(nvtxs, 0, touched);
253 pwgts[1] = tpwgts[0]+tpwgts[1];
259 touched[queue[0]] = 1;
268 if (nleft == 0 || drain)
272 for (i=0; i<nvtxs; i++) {
273 if (touched[i] == 0) {
283 first = 0; last = 1;;
288 if (pwgts[1]-vwgt[i] < minpwgt[1]) {
294 INC_DEC(pwgts[0], pwgts[1], vwgt[i]);
295 if (pwgts[1] <= maxpwgt[1])
299 for (j=xadj[i]; j<xadj[i+1]; j++) {
301 if (touched[k] == 0) {
318 for (i=0; i<graph->
nbnd; i++)
319 where[bndind[i]] = 2;
326 if (bestcut > graph->
mincut) {
328 idxcopy(nvtxs, where, bestwhere);
333 idxcopy(nvtxs, bestwhere, where);
348 int i, ii, j, k, nvtxs, pwgts[2], minpwgt[2], maxpwgt[2], from, bestcut, icut, mincut, me, pass, nbfs;
349 idxtype *xadj, *vwgt, *adjncy, *adjwgt, *where;
352 nvtxs = graph->
nvtxs;
359 where = graph->
where;
361 bestwhere =
idxmalloc(nvtxs,
"BisectGraph: bestwhere");
362 perm =
idxmalloc(nvtxs,
"BisectGraph: queue");
364 ASSERTP(tpwgts[0]+tpwgts[1] ==
idxsum(nvtxs, vwgt), (
"%d %d\n", tpwgts[0]+tpwgts[1],
idxsum(nvtxs, vwgt)));
366 maxpwgt[0] = ubfactor*tpwgts[0];
367 maxpwgt[1] = ubfactor*tpwgts[1];
368 minpwgt[0] = (1.0/ubfactor)*tpwgts[0];
369 minpwgt[1] = (1.0/ubfactor)*tpwgts[1];
373 for (; nbfs>0; nbfs--) {
377 pwgts[1] = tpwgts[0]+tpwgts[1];
382 for (ii=0; ii<nvtxs; ii++) {
384 if (pwgts[0]+vwgt[i] < maxpwgt[0]) {
388 if (pwgts[0] > minpwgt[0])
406 if (bestcut > graph->
mincut) {
408 idxcopy(nvtxs, where, bestwhere);
415 idxcopy(nvtxs, bestwhere, where);
#define Compute2WayNodePartitionParams
#define Compute2WayPartitionParams
#define IFSET(a, flag, cmd)
#define GrowBisectionNode
void GKfree(void **ptr1,...)
#define ASSERTP(expr, msg)
#define FM_2WayEdgeRefine
#define FM_2WayNodeRefine
#define INC_DEC(a, b, val)
#define Allocate2WayPartitionMemory
#define Init2WayPartition