41 if (
graph->nedges == 0)
69 real_t ntpwgts[2] = {0.5, 0.5};
83 if (
graph->nedges == 0)
117 idx_t i, ii,
j, k, nvtxs, pwgts[2], zeromaxpwgt, from, me,
118 bestcut=0, icut, mincut, inbfs;
124 nvtxs =
graph->nvtxs;
138 for (inbfs=0; inbfs<niparts; inbfs++) {
143 pwgts[1] =
graph->tvwgt[0];
146 for (ii=0; ii<nvtxs; ii++) {
148 if (pwgts[0]+
vwgt[
i] < zeromaxpwgt) {
152 if (pwgts[0] > zeromaxpwgt)
168 if (inbfs==0 || bestcut >
graph->mincut) {
169 bestcut =
graph->mincut;
176 graph->mincut = bestcut;
193 pwgts[2], oneminpwgt, onemaxpwgt,
194 from, me, bestcut=0, icut, mincut, inbfs;
196 idx_t *queue, *touched, *gain, *bestwhere;
200 nvtxs =
graph->nvtxs;
216 for (inbfs=0; inbfs<niparts; inbfs++) {
219 iset(nvtxs, 0, touched);
221 pwgts[1] =
graph->tvwgt[0];
226 touched[queue[0]] = 1;
235 if (nleft == 0 || drain)
239 for (
i=0;
i<nvtxs;
i++) {
240 if (touched[
i] == 0) {
256 if (pwgts[0] > 0 && pwgts[1]-
vwgt[
i] < oneminpwgt) {
263 if (pwgts[1] <= onemaxpwgt)
269 if (touched[k] == 0) {
304 if (inbfs == 0 || bestcut >
graph->mincut) {
305 bestcut =
graph->mincut;
312 graph->mincut = bestcut;
328 idx_t i, ii,
j, k, nvtxs,
ncon, from, bestcut=0, mincut, inbfs, qnum;
334 nvtxs =
graph->nvtxs;
345 for (inbfs=0; inbfs<2*niparts; inbfs++) {
350 for (ii=0; ii<nvtxs; ii++) {
353 where[
i] = (counts[qnum]++)%2;
364 if (inbfs == 0 || bestcut >=
graph->mincut) {
365 bestcut =
graph->mincut;
372 graph->mincut = bestcut;
388 idx_t i,
j, k, nvtxs,
ncon, from, bestcut=0, mincut, inbfs;
393 nvtxs =
graph->nvtxs;
400 for (inbfs=0; inbfs<2*niparts; inbfs++) {
411 if (inbfs == 0 || bestcut >=
graph->mincut) {
412 bestcut =
graph->mincut;
419 graph->mincut = bestcut;
436 idx_t i,
j, k, nvtxs, drain, nleft,
first,
last, pwgts[2], oneminpwgt,
437 onemaxpwgt, from, me, bestcut=0, icut, mincut, inbfs;
439 idx_t *queue, *touched, *gain, *bestwhere;
443 nvtxs =
graph->nvtxs;
459 graph->where =
imalloc(nvtxs,
"GrowBisectionNode: where");
460 graph->bndptr =
imalloc(nvtxs,
"GrowBisectionNode: bndptr");
461 graph->bndind =
imalloc(nvtxs,
"GrowBisectionNode: bndind");
467 bndind =
graph->bndind;
469 for (inbfs=0; inbfs<niparts; inbfs++) {
471 iset(nvtxs, 0, touched);
473 pwgts[1] =
graph->tvwgt[0];
477 touched[queue[0]] = 1;
485 if (nleft == 0 || drain)
489 for (
i=0;
i<nvtxs;
i++) {
490 if (touched[
i] == 0) {
506 if (pwgts[1]-
vwgt[
i] < oneminpwgt) {
513 if (pwgts[1] <= onemaxpwgt)
519 if (touched[k] == 0) {
550 if (inbfs == 0 || bestcut >
graph->mincut) {
551 bestcut =
graph->mincut;
556 graph->mincut = bestcut;
573 idx_t i,
j, k, nvtxs, bestcut=0, mincut, inbfs;
578 nvtxs =
graph->nvtxs;
583 graph->where =
imalloc(nvtxs,
"GrowBisectionNode: where");
584 graph->bndptr =
imalloc(nvtxs,
"GrowBisectionNode: bndptr");
585 graph->bndind =
imalloc(nvtxs,
"GrowBisectionNode: bndind");
593 bndind =
graph->bndind;
595 for (inbfs=0; inbfs<niparts; inbfs++) {
619 if (inbfs == 0 || bestcut >
graph->mincut) {
620 bestcut =
graph->mincut;
625 graph->mincut = bestcut;