46 int sigrval=0, renumber=0;
50 idx_t *cptr, *cind, *piperm;
81 piperm =
imalloc(*nvtxs,
"OMETIS: piperm");
90 nnvtxs = graph->
nvtxs;
98 cptr =
imalloc(*nvtxs+1,
"OMETIS: cptr");
99 cind =
imalloc(*nvtxs,
"OMETIS: cind");
101 graph =
CompressGraph(ctrl, *nvtxs, xadj, adjncy, vwgt, cptr, cind);
108 nnvtxs = graph->
nvtxs;
109 ctrl->
cfactor = 1.0*(*nvtxs)/nnvtxs;
133 icopy(nnvtxs, iperm, perm);
134 for (i=0; i<nnvtxs; i++)
135 iperm[piperm[i]] = perm[i];
136 for (i=nnvtxs; i<*nvtxs; i++)
137 iperm[piperm[i]] = i;
143 for (i=0; i<nnvtxs; i++)
145 for (l=ii=0; ii<nnvtxs; ii++) {
147 for (j=cptr[i]; j<cptr[i+1]; j++)
148 iperm[cind[j]] = l++;
154 for (i=0; i<*nvtxs; i++)
187 idx_t *label, *bndind;
190 nvtxs = graph->
nvtxs;
202 label = graph->
label;
203 for (i=0; i<nbnd; i++)
204 order[label[bndind[i]]] = --lastvtx;
222 MMDOrder(ctrl, rgraph, order, lastvtx);
239 idx_t i,
j, nvtxs, nbnd, ncmps, rnvtxs, snvtxs;
240 idx_t *label, *bndind;
244 nvtxs = graph->
nvtxs;
255 label = graph->
label;
256 for (i=0; i<nbnd; i++)
257 order[label[bndind[i]]] = --lastvtx;
266 printf(
" Bisection resulted in %"PRIDX
" connected components\n", ncmps);
277 for (rnvtxs=i=0; i<ncmps; i++) {
280 snvtxs = sgraphs[
i]->
nvtxs;
282 if (sgraphs[i]->nvtxs >
MMDSWITCH && sgraphs[i]->nedges > 0) {
286 MMDOrder(ctrl, sgraphs[i], order, lastvtx-rnvtxs);
315 mincut = graph->
tvwgt[0];
316 for (i=0; i<ctrl->
nseps; i++) {
319 if (i == 0 || graph->
mincut < mincut) {
321 if (i < ctrl->nseps-1)
328 if (i < ctrl->nseps-1)
332 if (mincut != graph->
mincut) {
352 if (graph->
nvtxs < 5000) {
365 mincut = graph->
tvwgt[0];
366 for (i=0; i<nruns; i++) {
369 if (i == 0 || cgraph->
mincut < mincut) {
382 if (mincut != cgraph->
mincut)
425 idx_t i, ii,
j, k,
l, istart, iend, mypart, nvtxs, snvtxs[3], snedges[3];
427 idx_t *sxadj[2], *svwgt[2], *sadjncy[2], *sadjwgt[2], *slabel[2];
436 nvtxs = graph->
nvtxs;
441 label = graph->
label;
442 where = graph->
where;
449 snvtxs[0] = snvtxs[1] = snvtxs[2] = snedges[0] = snedges[1] = snedges[2] = 0;
450 for (i=0; i<nvtxs; i++) {
452 rename[
i] = snvtxs[k]++;
453 snedges[k] += xadj[i+1]-xadj[
i];
457 sxadj[0] = lgraph->
xadj;
458 svwgt[0] = lgraph->
vwgt;
459 sadjncy[0] = lgraph->
adjncy;
460 sadjwgt[0] = lgraph->
adjwgt;
461 slabel[0] = lgraph->
label;
464 sxadj[1] = rgraph->
xadj;
465 svwgt[1] = rgraph->
vwgt;
466 sadjncy[1] = rgraph->
adjncy;
467 sadjwgt[1] = rgraph->
adjwgt;
468 slabel[1] = rgraph->
label;
471 for (ii=0; ii<graph->
nbnd; ii++) {
473 for (j=xadj[i]; j<xadj[i+1]; j++)
474 bndptr[adjncy[j]] = 1;
477 snvtxs[0] = snvtxs[1] = snedges[0] = snedges[1] = 0;
478 sxadj[0][0] = sxadj[1][0] = 0;
479 for (i=0; i<nvtxs; i++) {
480 if ((mypart = where[i]) == 2)
485 if (bndptr[i] == -1) {
486 auxadjncy = sadjncy[mypart] + snedges[mypart] - istart;
487 for(j=istart; j<iend; j++)
488 auxadjncy[j] = adjncy[j];
489 snedges[mypart] += iend-istart;
492 auxadjncy = sadjncy[mypart];
494 for (j=istart; j<iend; j++) {
496 if (where[k] == mypart)
502 svwgt[mypart][snvtxs[mypart]] = vwgt[
i];
503 slabel[mypart][snvtxs[mypart]] = label[
i];
504 sxadj[mypart][++snvtxs[mypart]] = snedges[mypart];
507 for (mypart=0; mypart<2; mypart++) {
508 iend = snedges[mypart];
509 iset(iend, 1, sadjwgt[mypart]);
511 auxadjncy = sadjncy[mypart];
512 for (i=0; i<iend; i++)
513 auxadjncy[i] = rename[auxadjncy[i]];
516 lgraph->
nvtxs = snvtxs[0];
517 lgraph->
nedges = snedges[0];
518 rgraph->
nvtxs = snvtxs[1];
519 rgraph->
nedges = snedges[1];
555 idx_t i, ii, iii,
j, k,
l, istart, iend, mypart, nvtxs, snvtxs, snedges;
557 idx_t *sxadj, *svwgt, *sadjncy, *sadjwgt, *slabel;
566 nvtxs = graph->
nvtxs;
571 label = graph->
label;
572 where = graph->
where;
578 for (ii=0; ii<graph->
nbnd; ii++) {
580 for (j=xadj[i]; j<xadj[i+1]; j++)
581 bndptr[adjncy[j]] = 1;
589 for (iii=0; iii<ncmps; iii++) {
590 irandArrayPermute(cptr[iii+1]-cptr[iii], cind+cptr[iii], cptr[iii+1]-cptr[iii], 0);
591 snvtxs = snedges = 0;
592 for (j=cptr[iii]; j<cptr[iii+1]; j++) {
594 rename[
i] = snvtxs++;
595 snedges += xadj[i+1]-xadj[
i];
600 sxadj = sgraphs[iii]->
xadj;
601 svwgt = sgraphs[iii]->
vwgt;
602 sadjncy = sgraphs[iii]->
adjncy;
603 sadjwgt = sgraphs[iii]->
adjwgt;
604 slabel = sgraphs[iii]->
label;
606 snvtxs = snedges = sxadj[0] = 0;
607 for (ii=cptr[iii]; ii<cptr[iii+1]; ii++) {
612 if (bndptr[i] == -1) {
613 auxadjncy = sadjncy + snedges - istart;
614 for(j=istart; j<iend; j++)
615 auxadjncy[j] = adjncy[j];
616 snedges += iend-istart;
620 for (j=istart; j<iend; j++) {
628 svwgt[snvtxs] = vwgt[
i];
629 slabel[snvtxs] = label[
i];
630 sxadj[++snvtxs] = snedges;
633 iset(snedges, 1, sadjwgt);
634 for (i=0; i<snedges; i++)
635 sadjncy[i] = rename[sadjncy[i]];
637 sgraphs[iii]->
nvtxs = snvtxs;
638 sgraphs[iii]->
nedges = snedges;
657 idx_t i,
j, k, nvtxs, nofsub, firstvtx;
663 nvtxs = graph->
nvtxs;
671 for (i=0; i<nvtxs+1; i++)
681 genmmd(nvtxs, xadj, adjncy, iperm, perm, 1, head, qsize, list, marker,
IDX_MAX, &nofsub);
683 label = graph->
label;
684 firstvtx = lastvtx-nvtxs;
685 for (i=0; i<nvtxs; i++)
686 order[label[i]] = firstvtx+iperm[i]-1;
689 for (i=0; i<nvtxs+1; i++)
idx_t idx_t idx_t idx_t * vwgt
#define Compute2WayNodePartitionParams
graph_t ** SplitGraphOrderCC(ctrl_t *ctrl, graph_t *graph, idx_t ncmps, idx_t *cptr, idx_t *cind)
#define gk_startcputimer(tmr)
graph_t * CoarsenGraphNlevels(ctrl_t *ctrl, graph_t *graph, idx_t nlevels)
#define irandArrayPermute
void MlevelNestedDissection(ctrl_t *ctrl, graph_t *graph, idx_t *order, idx_t lastvtx)
#define gk_stopcputimer(tmr)
void MlevelNodeBisectionL1(ctrl_t *ctrl, graph_t *graph, idx_t niparts)
idx_t idx_t idx_t idx_t idx_t idx_t * iperm
NonlinearFactorGraph graph
void MlevelNodeBisectionMultiple(ctrl_t *ctrl, graph_t *graph)
#define Change2FNumberingOrder
int METIS_NodeND(idx_t *nvtxs, idx_t *xadj, idx_t *adjncy, idx_t *vwgt, idx_t *options, idx_t *perm, idx_t *iperm)
#define ASSERT(expression)
#define AllocateWorkSpace
static const Line3 l(Rot3(), 1, 1)
#define Change2CNumbering
idx_t idx_t idx_t idx_t idx_t * perm
void MMDOrder(ctrl_t *ctrl, graph_t *graph, idx_t *order, idx_t lastvtx)
void gk_malloc_cleanup(int showstats)
idx_t idx_t idx_t idx_t idx_t * numflag
idx_t idx_t idx_t idx_t idx_t idx_t * adjwgt
#define FindSepInducedComponents
void MlevelNestedDissectionCC(ctrl_t *ctrl, graph_t *graph, idx_t *order, idx_t lastvtx)
void * gk_malloc(size_t nbytes, char *msg)
void gk_free(void **ptr1,...)
idx_t idx_t idx_t idx_t * where
EIGEN_DEVICE_FUNC SegmentReturnType head(Index n)
This is the const version of head(Index).
idx_t idx_t idx_t * adjncy
void MlevelNodeBisectionL2(ctrl_t *ctrl, graph_t *graph, idx_t niparts)
#define IFSET(a, flag, cmd)
void SplitGraphOrder(ctrl_t *ctrl, graph_t *graph, graph_t **r_lgraph, graph_t **r_rgraph)