23 int i, j, k, nvtxs, nbnd;
34 for (i=0; i<nbnd; i++) {
36 if (xadj[j+1]-xadj[j] > 0)
65 int i, ii, j, jj, k, l, nvtxs, nbnd, bnvtxs[3], bnedges[2], csize;
66 idxtype *xadj, *adjncy, *bxadj, *badjncy;
67 idxtype *where, *bndind, *bndptr, *vmap, *ivmap, *cover;
85 bnvtxs[0] = bnvtxs[1] = bnedges[0] = bnedges[1] = 0;
86 for (i=0; i<nbnd; i++) {
89 if (xadj[j+1]-xadj[j] > 0) {
91 bnedges[k] += xadj[j+1]-xadj[j];
95 bnvtxs[2] = bnvtxs[0]+bnvtxs[1];
96 bnvtxs[1] = bnvtxs[0];
99 bxadj =
idxmalloc(bnvtxs[2]+1,
"ConstructMinCoverSeparator: bxadj");
100 badjncy =
idxmalloc(bnedges[0]+bnedges[1]+1,
"ConstructMinCoverSeparator: badjncy");
104 for (i=0; i<nbnd; i++) {
107 if (xadj[j+1]-xadj[j] > 0) {
109 ivmap[bnvtxs[k]++] = j;
114 bnvtxs[1] = bnvtxs[0];
117 for (k=0; k<2; k++) {
118 for (ii=0; ii<nbnd; ii++) {
120 if (where[i] == k && xadj[i] < xadj[i+1]) {
121 for (j=xadj[i]; j<xadj[i+1]; j++) {
123 if (where[jj] != k) {
125 ASSERTP(vmap[jj] != -1, (
"%d %d %d\n", jj, vmap[jj], graph->
bndptr[jj]));
126 badjncy[l++] = vmap[jj];
129 bxadj[++bnvtxs[k]] = l;
134 ASSERT(l <= bnedges[0]+bnedges[1]);
136 MinCover(bxadj, badjncy, bnvtxs[0], bnvtxs[1], cover, &csize);
139 printf(
"Nvtxs: %6d, [%5d %5d], Cut: %6d, SS: [%6d %6d], Cover: %6d\n", nvtxs, graph->
pwgts[0], graph->
pwgts[1], graph->
mincut, bnvtxs[0], bnvtxs[1]-bnvtxs[0], csize));
141 for (i=0; i<csize; i++) {
148 for (i=0; i<nbnd; i++)
149 bndptr[bndind[i]] = -1;
150 for (nbnd=i=0; i<nvtxs; i++) {
159 printf(
"Nvtxs: %6d, [%5d %5d], Cut: %6d, SS: [%6d %6d], Cover: %6d\n", nvtxs, graph->
pwgts[0], graph->
pwgts[1], graph->
mincut, 0, 0, 0));
180 int i, ii, j, jj, k, l, nvtxs, nbnd, bnvtxs[3], bnedges[2], csize;
181 idxtype *xadj, *adjncy, *bxadj, *badjncy;
182 idxtype *where, *bndind, *bndptr, *vmap, *ivmap, *cover;
185 nvtxs = graph->
nvtxs;
192 where = graph->
where;
200 bnvtxs[0] = bnvtxs[1] = bnedges[0] = bnedges[1] = 0;
201 for (i=0; i<nbnd; i++) {
204 if (xadj[j+1]-xadj[j] > 0) {
206 bnedges[k] += xadj[j+1]-xadj[j];
210 bnvtxs[2] = bnvtxs[0]+bnvtxs[1];
211 bnvtxs[1] = bnvtxs[0];
214 bxadj =
idxmalloc(bnvtxs[2]+1,
"ConstructMinCoverSeparator: bxadj");
215 badjncy =
idxmalloc(bnedges[0]+bnedges[1]+1,
"ConstructMinCoverSeparator: badjncy");
219 for (i=0; i<nbnd; i++) {
222 if (xadj[j+1]-xadj[j] > 0) {
224 ivmap[bnvtxs[k]++] = j;
229 bnvtxs[1] = bnvtxs[0];
232 for (k=0; k<2; k++) {
233 for (ii=0; ii<nbnd; ii++) {
235 if (where[i] == k && xadj[i] < xadj[i+1]) {
236 for (j=xadj[i]; j<xadj[i+1]; j++) {
238 if (where[jj] != k) {
240 ASSERTP(vmap[jj] != -1, (
"%d %d %d\n", jj, vmap[jj], graph->
bndptr[jj]));
241 badjncy[l++] = vmap[jj];
244 bxadj[++bnvtxs[k]] = l;
249 ASSERT(l <= bnedges[0]+bnedges[1]);
251 MinCover(bxadj, badjncy, bnvtxs[0], bnvtxs[1], cover, &csize);
254 printf(
"Nvtxs: %6d, [%5d %5d], Cut: %6d, SS: [%6d %6d], Cover: %6d\n", nvtxs, graph->
pwgts[0], graph->
pwgts[1], graph->
mincut, bnvtxs[0], bnvtxs[1]-bnvtxs[0], csize));
256 for (i=0; i<csize; i++) {
265 printf(
"Nvtxs: %6d, [%5d %5d], Cut: %6d, SS: [%6d %6d], Cover: %6d\n", nvtxs, graph->
pwgts[0], graph->
pwgts[1], graph->
mincut, 0, 0, 0));
#define Compute2WayNodePartitionParams
#define ConstructMinCoverSeparator
#define CheckNodePartitionParams
#define Allocate2WayNodePartitionMemory
#define IFSET(a, flag, cmd)
#define ConstructSeparator
void GKfree(void **ptr1,...)
#define ASSERTP(expr, msg)
#define FM_2WayNodeRefine_OneSided
#define FM_2WayNodeRefine
#define ConstructMinCoverSeparator0