21 float *tpwgts,
float ubfactor)
38 for (ptr=graph, nlevels=0; ptr!=orggraph; ptr=ptr->
finer, nlevels++);
48 if (2*i >= nlevels && !
IsBalanced(graph->
pwgts, nparts, tpwgts, 1.04*ubfactor)) {
50 switch (ctrl->
RType) {
61 switch (ctrl->
RType) {
71 if (graph == orggraph)
85 switch (ctrl->
RType) {
111 nvtxs = graph->
nvtxs;
113 pad64 = (3*nvtxs+nparts)%2;
131 int i, ii, j, k, kk, l, nvtxs, nbnd, mincut, minvol, me, other, pid;
132 idxtype *xadj, *vwgt, *adjncy, *adjwgt, *pwgts, *where;
136 nvtxs = graph->
nvtxs;
142 where = graph->
where;
152 for (i=0; i<nvtxs; i++) {
154 pwgts[me] += vwgt[i];
160 for (j=xadj[i]; j<xadj[i+1]; j++) {
161 if (me == where[adjncy[j]]) {
162 myrinfo->
id += adjwgt[j];
168 mincut += myrinfo->
ed;
171 if (myrinfo->
ed > 0) {
175 for (j=xadj[i]; j<xadj[i+1]; j++) {
176 other = where[adjncy[j]];
178 for (k=0; k<myrinfo->
ndegrees; k++) {
179 if (myedegrees[k].pid == other) {
180 myedegrees[k].
ed += adjwgt[j];
211 int i, ii, j, k, kk, l, nvtxs, me, other, pid, myndegrees;
212 idxtype *xadj, *vsize, *adjncy, *adjwgt, *where, *bndind, *bndptr, *ophtable;
216 nvtxs = graph->
nvtxs;
218 vsize = graph->
vsize;
222 where = graph->
where;
233 for (i=0; i<nvtxs; i++) {
242 graph->
minvol += myndegrees*vsize[i];
244 for (j=xadj[i]; j<xadj[i+1]; j++) {
251 ophtable[oedegrees[k].pid] = k;
256 for (k=0; k<myndegrees; k++) {
257 if (ophtable[myedegrees[k].pid] == -1)
258 myedegrees[k].
gv -= vsize[ii];
262 ASSERT(ophtable[me] != -1);
264 if (oedegrees[ophtable[me]].ned == 1) {
266 for (k=0; k<myndegrees; k++) {
267 if (ophtable[myedegrees[k].pid] != -1)
268 myedegrees[k].
gv += vsize[ii];
273 for (k=0; k<myndegrees; k++) {
274 if (ophtable[myedegrees[k].pid] == -1)
275 myedegrees[k].
gv -= vsize[ii];
280 for (kk=0; kk<orinfo->
ndegrees; kk++)
281 ophtable[oedegrees[kk].pid] = -1;
282 ophtable[other] = -1;
286 for (k=0; k<myndegrees; k++) {
287 if (myedegrees[k].gv > myrinfo->
gv)
288 myrinfo->
gv = myedegrees[k].
gv;
292 if (myrinfo->
ed > 0 && myrinfo->
id == 0)
293 myrinfo->
gv += vsize[i];
295 if (myrinfo->
gv >= 0 || myrinfo->
ed-myrinfo->
id >= 0)
311 int i, j, k, nvtxs, me, other, istart, iend, ndegrees;
312 idxtype *xadj, *adjncy, *adjwgt, *adjwgtsum;
321 cwhere = cgraph->
where;
324 nvtxs = graph->
nvtxs;
332 where = graph->
where;
336 for (i=0; i<nvtxs; i++) {
338 where[i] = cwhere[k];
339 cmap[i] = crinfo[k].
ed;
345 for (i=0; i<nvtxs; i++) {
352 myrinfo->
id = adjwgtsum[i];
353 myrinfo->
nid = xadj[i+1]-xadj[i];
363 for (j=istart; j<iend; j++) {
364 other = where[adjncy[j]];
366 myrinfo->
ed += adjwgt[j];
368 if ((k = htable[other]) == -1) {
369 htable[other] = ndegrees;
370 myedegrees[ndegrees].
gv = 0;
371 myedegrees[ndegrees].
pid = other;
372 myedegrees[ndegrees].
ed = adjwgt[j];
373 myedegrees[ndegrees++].
ned = 1;
376 myedegrees[k].
ed += adjwgt[j];
381 myrinfo->
id -= myrinfo->
ed;
384 if (myrinfo->
ed == 0) {
391 for (j=0; j<ndegrees; j++)
392 htable[myedegrees[j].pid] = -1;
419 nvtxs = graph->
nvtxs;
428 for (i=0; i<nvtxs; i++) {
444 nvtxs = graph->
nvtxs;
453 for (i=0; i<nvtxs; i++) {
#define EliminateVolSubDomainEdges
#define ComputeKWayVolGains
#define ProjectVolKWayPartition
#define RTYPE_KWAYRANDOM_MCONN
#define Random_KWayVolRefine
#define BNDInsert(nbnd, bndind, bndptr, vtx)
#define Greedy_KWayVolBalance
struct graphdef * coarser
#define ComputeVolKWayBoundary
#define IFSET(a, flag, cmd)
void EliminateVolComponents(CtrlType *ctrl, GraphType *graph, int nparts, float *tpwgts, float ubfactor)
#define Random_KWayVolRefineMConn
void GKfree(void **ptr1,...)
#define Greedy_KWayVolBalanceMConn
#define MALLOC_CHECK(ptr)
#define AllocateVolKWayPartitionMemory
#define ComputeVolKWayPartitionParams
#define ComputeVolKWayBalanceBoundary