31 switch (ctrl->
IType) {
40 errexit(
"Unknown initial partition type: %d\n", ctrl->
IType);
59 int i, j, k, nvtxs, ncon, from, bestcut, mincut, nbfs;
67 bestwhere =
idxmalloc(nvtxs,
"BisectGraph: bestwhere");
71 for (; nbfs>0; nbfs--) {
84 if (bestcut > graph->
mincut) {
86 idxcopy(nvtxs, where, bestwhere);
93 idxcopy(nvtxs, bestwhere, where);
110 int i, j, k, nvtxs, ncon, from, bestcut, mincut, nbfs;
113 nvtxs = graph->
nvtxs;
116 where = graph->
where;
118 bestwhere =
idxmalloc(nvtxs,
"BisectGraph: bestwhere");
122 for (; nbfs>0; nbfs--) {
132 if (bestcut > graph->
mincut) {
134 idxcopy(nvtxs, where, bestwhere);
141 idxcopy(nvtxs, bestwhere, where);
158 int i, ii, j, k, l, kwgt, nvtxs, nbnd, ncon, nswaps, from, to, pass, me, cnum, tmp, imin;
159 idxtype *xadj, *adjncy, *adjwgt, *where, *id, *ed, *bndptr, *bndind;
161 float *nvwgt, *npwgts, minwgt;
163 int higain, oldgain, mincut;
165 nvtxs = graph->
nvtxs;
169 nvwgt = graph->
nvwgt;
171 where = graph->
where;
188 for (l=0; l<ncon; l++)
189 printf(
"(%.3f, %.3f) ", npwgts[l], npwgts[ncon+l]);
190 printf(
"] T[%.3f %.3f], Nv-Nb[%5d, %5d]. ICut: %6d, LB: %.3f [B]\n", tpwgts[0], tpwgts[1], graph->
nvtxs, graph->
nbnd, graph->
mincut,
ComputeLoadImbalance(ncon, 2, npwgts, tpwgts));
193 for (i=0; i<ncon; i++) {
205 for (i=0; i<nvtxs; i++)
206 qnum[i] =
samax(ncon, nvwgt+i*ncon);
210 for (ii=0; ii<nvtxs; ii++) {
212 if (where[i] == from) {
227 for (i=1; i<ncon; i++)
228 imin = (ubvec[i] < ubvec[imin] ? i : imin);
229 minwgt = .5/ubvec[imin];
233 for (nswaps=0; nswaps<nvtxs; nswaps++) {
235 if (npwgts[to*ncon+imin] > minwgt)
244 mincut -= (ed[higain]-
id[higain]);
245 saxpy(ncon, 1.0, nvwgt+higain*ncon, 1, npwgts+to*ncon, 1);
246 saxpy(ncon, -1.0, nvwgt+higain*ncon, 1, npwgts+from*ncon, 1);
249 moved[higain] = nswaps;
252 printf(
"Moved %6d from %d(%d). [%5d] %5d, NPwgts: ", higain, from, cnum, ed[higain]-
id[higain], mincut);
253 for (l=0; l<ncon; l++)
254 printf(
"(%.3f, %.3f) ", npwgts[l], npwgts[ncon+l]);
256 if (ed[higain] == 0 &&
id[higain] > 0)
257 printf(
"\t Pulled from the interior!\n");
264 SWAP(
id[higain], ed[higain], tmp);
265 if (ed[higain] == 0 && bndptr[higain] != -1 && xadj[higain] < xadj[higain+1])
267 if (ed[higain] > 0 && bndptr[higain] == -1)
270 for (j=xadj[higain]; j<xadj[higain+1]; j++) {
272 oldgain = ed[k]-
id[k];
274 kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
278 if (moved[k] == -1 && where[k] == from) {
279 if (ed[k] > 0 && bndptr[k] == -1) {
285 printf(
"What you thought was wrong!\n");
286 PQueueUpdate(&parts[qnum[k]][0], k, oldgain, ed[k]-
id[k]);
291 if (ed[k] == 0 && bndptr[k] != -1)
293 else if (ed[k] > 0 && bndptr[k] == -1)
302 printf(
"\tMincut: %6d, NBND: %6d, NPwgts: ", mincut, nbnd);
303 for (l=0; l<ncon; l++)
304 printf(
"(%.3f, %.3f) ", npwgts[l], npwgts[ncon+l]);
311 for (i=0; i<ncon; i++) {
332 int i, cnum=-1, imax, maxgain;
336 for (i=0; i<ncon; i++) {
342 for (i=0; i<ncon; i++)
343 twgt[i] = (max/(ubvec[imax]*ubvec[i]))/pto[i];
347 for (i=0; i<ncon; i++) {
358 for (i=0; i<ncon; i++) {
#define MocInit2WayPartition2
#define BNDInsert(nbnd, bndind, bndptr, vtx)
#define ComputeLoadImbalance
#define MocFM_2WayEdgeRefine2
#define MocGrowBisectionNew2
#define MocGrowBisection2
#define IFSET(a, flag, cmd)
#define MocCompute2WayPartitionParams
int PQueueGetSize(PQueueType *queue)
#define MocInit2WayBalance2
#define SelectQueueOneWay2
void GKfree(void **ptr1,...)
#define ASSERTP(expr, msg)
#define BNDDelete(nbnd, bndind, bndptr, vtx)
int PQueueGetKey(PQueueType *queue)
#define INC_DEC(a, b, val)
int CheckGraph(GraphType *)
#define MocAllocate2WayPartitionMemory