23 idxtype *adjwgt,
int *wgtflag,
int *numflag,
int *nparts,
24 int *options,
int *edgecut,
idxtype *part)
29 tpwgts =
fmalloc(*nparts,
"KMETIS: tpwgts");
30 for (i=0; i<*nparts; i++)
31 tpwgts[i] = 1.0/(1.0*(*nparts));
34 tpwgts, options, edgecut, part);
46 idxtype *adjwgt,
int *wgtflag,
int *numflag,
int *nparts,
47 float *tpwgts,
int *options,
int *edgecut,
idxtype *part)
59 if (options[0] == 0) {
75 mytpwgts =
fmalloc(*nparts,
"PWMETIS: mytpwgts");
76 for (i=0; i<*nparts; i++)
77 mytpwgts[i] = tpwgts[i];
105 int i, j, nvtxs, cut, tvwgt, tpwgts2[2];
110 nvtxs = graph->
nvtxs;
112 printf(
"\t***Cannot bisect a graph with 0 vertices!\n\t***You are trying to partition a graph into too many parts!\n");
118 tpwgts2[0] = tvwgt*
ssum(nparts/2, tpwgts);
119 tpwgts2[1] = tvwgt-tpwgts2[0];
126 label = graph->
label;
127 where = graph->
where;
128 for (i=0; i<nvtxs; i++)
129 part[label[i]] = where[i] + fpart;
141 wsum =
ssum(nparts/2, tpwgts);
142 sscale(nparts/2, 1.0/wsum, tpwgts);
143 sscale(nparts-nparts/2, 1.0/(1.0-wsum), tpwgts+nparts/2);
155 else if (nparts == 3) {
176 Refine2Way(ctrl, graph, cgraph, tpwgts, ubfactor);
192 int i, j, k, kk, l, istart, iend, mypart, nvtxs, ncon, snvtxs[2], snedges[2], sum;
193 idxtype *xadj, *vwgt, *adjncy, *adjwgt, *adjwgtsum, *label, *where, *bndptr;
194 idxtype *sxadj[2], *svwgt[2], *sadjncy[2], *sadjwgt[2], *sadjwgtsum[2], *slabel[2];
196 idxtype *auxadjncy, *auxadjwgt;
197 float *nvwgt, *snvwgt[2], *npwgts;
202 nvtxs = graph->
nvtxs;
206 nvwgt = graph->
nvwgt;
210 label = graph->
label;
211 where = graph->
where;
219 snvtxs[0] = snvtxs[1] = snedges[0] = snedges[1] = 0;
220 for (i=0; i<nvtxs; i++) {
222 rename[i] = snvtxs[k]++;
223 snedges[k] += xadj[i+1]-xadj[i];
227 sxadj[0] = lgraph->
xadj;
228 svwgt[0] = lgraph->
vwgt;
229 snvwgt[0] = lgraph->
nvwgt;
231 sadjncy[0] = lgraph->
adjncy;
232 sadjwgt[0] = lgraph->
adjwgt;
233 slabel[0] = lgraph->
label;
236 sxadj[1] = rgraph->
xadj;
237 svwgt[1] = rgraph->
vwgt;
238 snvwgt[1] = rgraph->
nvwgt;
240 sadjncy[1] = rgraph->
adjncy;
241 sadjwgt[1] = rgraph->
adjwgt;
242 slabel[1] = rgraph->
label;
244 snvtxs[0] = snvtxs[1] = snedges[0] = snedges[1] = 0;
245 sxadj[0][0] = sxadj[1][0] = 0;
246 for (i=0; i<nvtxs; i++) {
252 if (bndptr[i] == -1) {
253 auxadjncy = sadjncy[mypart] + snedges[mypart] - istart;
254 auxadjwgt = sadjwgt[mypart] + snedges[mypart] - istart;
255 for(j=istart; j<iend; j++) {
256 auxadjncy[j] = adjncy[j];
257 auxadjwgt[j] = adjwgt[j];
259 snedges[mypart] += iend-istart;
262 auxadjncy = sadjncy[mypart];
263 auxadjwgt = sadjwgt[mypart];
265 for (j=istart; j<iend; j++) {
267 if (where[k] == mypart) {
269 auxadjwgt[l++] = adjwgt[j];
279 svwgt[mypart][snvtxs[mypart]] = vwgt[i];
281 for (kk=0; kk<ncon; kk++)
282 snvwgt[mypart][snvtxs[mypart]*ncon+kk] = nvwgt[i*ncon+kk]/npwgts[mypart*ncon+kk];
285 sadjwgtsum[mypart][snvtxs[mypart]] = sum;
286 slabel[mypart][snvtxs[mypart]] = label[i];
287 sxadj[mypart][++snvtxs[mypart]] = snedges[mypart];
290 for (mypart=0; mypart<2; mypart++) {
291 iend = sxadj[mypart][snvtxs[mypart]];
292 auxadjncy = sadjncy[mypart];
293 for (i=0; i<iend; i++)
294 auxadjncy[i] = rename[auxadjncy[i]];
297 lgraph->
nedges = snedges[0];
298 rgraph->
nedges = snedges[1];
312 sgraph->
nvtxs = snvtxs;
317 if (graph->
ncon == 1) {
318 sgraph->
gdata =
idxmalloc(4*snvtxs+1 + 2*snedges,
"SetUpSplitGraph: gdata");
323 sgraph->
cmap = sgraph->
gdata + 3*snvtxs+1;
325 sgraph->
adjwgt = sgraph->
gdata + 4*snvtxs+1 + snedges;
328 sgraph->
gdata =
idxmalloc(3*snvtxs+1 + 2*snedges,
"SetUpSplitGraph: gdata");
332 sgraph->
cmap = sgraph->
gdata + 2*snvtxs+1;
334 sgraph->
adjwgt = sgraph->
gdata + 3*snvtxs+1 + snedges;
339 sgraph->
label =
idxmalloc(snvtxs,
"SetUpSplitGraph: sgraph->label");
#define MlevelRecursiveBisection
#define AllocateWorkSpace
#define IFSET(a, flag, cmd)
void METIS_WPartGraphRecursive(int *nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *vwgt, idxtype *adjwgt, int *wgtflag, int *numflag, int *nparts, float *tpwgts, int *options, int *edgecut, idxtype *part)
#define Change2CNumbering
void METIS_PartGraphRecursive(int *nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *vwgt, idxtype *adjwgt, int *wgtflag, int *numflag, int *nparts, int *options, int *edgecut, idxtype *part)
void GKfree(void **ptr1,...)
#define MlevelEdgeBisection
#define Change2FNumbering
#define Init2WayPartition