22 int i, nlevels, mustfree=0;
40 for (ptr=graph, nlevels=0; ptr!=orggraph; ptr=ptr->
finer, nlevels++);
49 if (2*i >= nlevels && !
IsBalanced(graph->
pwgts, nparts, tpwgts, 1.04*ubfactor)) {
58 switch (ctrl->
RType) {
71 if (graph == orggraph)
79 if (graph->
vwgt == NULL) {
119 nvtxs = graph->
nvtxs;
121 pad64 = (3*nvtxs+nparts)%2;
143 int i, j, k, l, nvtxs, nbnd, mincut, me, other;
144 idxtype *xadj, *vwgt, *adjncy, *adjwgt, *pwgts, *where, *bndind, *bndptr;
148 nvtxs = graph->
nvtxs;
154 where = graph->
where;
158 rinfo = graph->
rinfo;
166 for (i=0; i<nvtxs; i++) {
168 pwgts[me] += vwgt[i];
174 for (j=xadj[i]; j<xadj[i+1]; j++) {
175 if (me != where[adjncy[j]])
176 myrinfo->
ed += adjwgt[j];
181 mincut += myrinfo->
ed;
183 if (myrinfo->
ed-myrinfo->
id >= 0)
187 if (myrinfo->
ed > 0) {
191 for (j=xadj[i]; j<xadj[i+1]; j++) {
192 other = where[adjncy[j]];
194 for (k=0; k<myrinfo->
ndegrees; k++) {
195 if (myedegrees[k].pid == other) {
196 myedegrees[k].
ed += adjwgt[j];
202 myedegrees[myrinfo->
ndegrees++].
ed = adjwgt[j];
224 int i, j, k, nvtxs, nbnd, me, other, istart, iend, ndegrees;
225 idxtype *xadj, *adjncy, *adjwgt, *adjwgtsum;
226 idxtype *cmap, *where, *bndptr, *bndind;
234 cwhere = cgraph->
where;
235 crinfo = cgraph->
rinfo;
237 nvtxs = graph->
nvtxs;
245 where = graph->
where;
246 rinfo = graph->
rinfo;
251 for (i=0; i<nvtxs; i++) {
253 where[i] = cwhere[k];
254 cmap[i] = crinfo[k].
ed;
260 for (nbnd=0, i=0; i<nvtxs; i++) {
267 myrinfo->
id = adjwgtsum[i];
277 for (j=istart; j<iend; j++) {
278 other = where[adjncy[j]];
280 myrinfo->
ed += adjwgt[j];
281 if ((k = htable[other]) == -1) {
282 htable[other] = ndegrees;
283 myedegrees[ndegrees].
pid = other;
284 myedegrees[ndegrees++].
ed = adjwgt[j];
287 myedegrees[k].
ed += adjwgt[j];
291 myrinfo->
id -= myrinfo->
ed;
294 if (myrinfo->
ed == 0) {
299 if (myrinfo->
ed-myrinfo->
id >= 0)
304 for (j=0; j<ndegrees; j++)
305 htable[myedegrees[j].pid] = -1;
333 tvwgt =
idxsum(nparts, pwgts);
334 for (i=0; i<nparts; i++) {
335 if (pwgts[i] > tpwgts[i]*tvwgt*(ubfactor+0.005))
351 nvtxs = graph->
nvtxs;
360 for (i=0; i<nvtxs; i++) {
376 nvtxs = graph->
nvtxs;
385 for (i=0; i<nvtxs; i++) {
#define Greedy_KWayEdgeBalance
#define ComputeKWayBalanceBoundary
#define Random_KWayEdgeRefineMConn
#define Random_KWayEdgeRefine
#define RTYPE_KWAYRANDOM_MCONN
#define EliminateComponents
#define BNDInsert(nbnd, bndind, bndptr, vtx)
#define AllocateKWayPartitionMemory
struct graphdef * coarser
#define Greedy_KWayEdgeRefine
#define IFSET(a, flag, cmd)
#define EliminateSubDomainEdges
void GKfree(void **ptr1,...)
#define ProjectKWayPartition
#define ComputeKWayPartitionParams
#define Greedy_KWayEdgeBalanceMConn
#define ComputeKWayBoundary