14 #define UNMATCHEDFOR2HOP 0.10
29 for (eqewgts=1,
i=1;
i<
graph->nedges;
i++) {
49 switch (ctrl->
ctype) {
54 if (eqewgts ||
graph->nedges == 0)
69 }
while (
graph->nvtxs > ctrl->CoarsenTo &&
92 for (eqewgts=1,
i=1;
i<
graph->nedges;
i++) {
112 switch (ctrl->
ctype) {
117 if (eqewgts ||
graph->nedges == 0)
151 idx_t i, pi, ii,
j, jj, jjinc, k, nvtxs,
ncon, cnvtxs, maxidx, last_unmatched;
160 nvtxs =
graph->nvtxs;
175 for (cnvtxs=0, last_unmatched=0, pi=0; pi<nvtxs; pi++) {
185 last_unmatched =
gk_max(pi, last_unmatched)+1;
186 for (; last_unmatched<nvtxs; last_unmatched++) {
187 j =
perm[last_unmatched];
207 if (maxidx ==
i && 3*
vwgt[
i] < maxvwgt[0]) {
233 cmap[
i] = cmap[maxidx] = cnvtxs++;
249 for (cnvtxs=0,
i=0;
i<nvtxs;
i++) {
256 cmap[
i] = cmap[
match[
i]] = cnvtxs++;
278 idx_t i, pi, ii,
j, jj, jjinc, k, nvtxs,
ncon, cnvtxs, maxidx, maxwgt,
279 last_unmatched, avgdegree;
288 nvtxs =
graph->nvtxs;
305 avgdegree = 0.7*(
xadj[nvtxs]/nvtxs);
306 for (
i=0;
i<nvtxs;
i++)
310 for (cnvtxs=0, last_unmatched=0, pi=0; pi<nvtxs; pi++) {
321 last_unmatched =
gk_max(pi, last_unmatched)+1;
322 for (; last_unmatched<nvtxs; last_unmatched++) {
323 j =
perm[last_unmatched];
344 if (maxidx ==
i && 3*
vwgt[
i] < maxvwgt[0]) {
374 cmap[
i] = cmap[maxidx] = cnvtxs++;
390 for (cnvtxs=0,
i=0;
i<nvtxs;
i++) {
397 cmap[
i] = cmap[
match[
i]] = cnvtxs++;
416 idx_t cnvtxs,
size_t nunmatched)
438 idx_t cnvtxs,
size_t *r_nunmatched,
size_t maxdegree)
440 idx_t i, pi, ii,
j, jj, k, nvtxs;
447 nvtxs =
graph->nvtxs;
452 nunmatched = *r_nunmatched;
459 for (
i=0;
i<nvtxs;
i++) {
468 for (pi=0; pi<nvtxs; pi++) {
478 for (pi=0; pi<nvtxs; pi++) {
480 if (colptr[
i+1]-colptr[
i] < 2)
483 for (jj=colptr[
i+1],
j=colptr[
i];
j<jj;
j++) {
485 for (jj--; jj>
j; jj--) {
487 cmap[rowind[
j]] = cmap[rowind[jj]] = cnvtxs++;
488 match[rowind[
j]] = rowind[jj];
489 match[rowind[jj]] = rowind[
j];
503 *r_nunmatched = nunmatched;
517 idx_t cnvtxs,
size_t *r_nunmatched,
size_t maxdegree)
519 idx_t i, pi, pk, ii,
j, jj, k, nvtxs, mask, idegree;
523 size_t nunmatched, ncand;
527 nvtxs =
graph->nvtxs;
532 nunmatched = *r_nunmatched;
541 for (ncand=0, pi=0; pi<nvtxs; pi++) {
548 keys[ncand].key = (k%mask)*maxdegree + idegree;
555 for (pi=0; pi<ncand; pi++) {
563 for (pk=pi+1; pk<ncand; pk++) {
573 for (jj=
xadj[k]; jj<
xadj[k+1]; jj++) {
577 if (jj ==
xadj[k+1]) {
578 cmap[
i] = cmap[k] = cnvtxs++;
592 *r_nunmatched = nunmatched;
624 idx_t j, jj, k, kk,
l,
m, istart, iend, nvtxs, nedges,
ncon, cnedges,
627 idx_t *cmap, *htable;
628 idx_t *cxadj, *cvwgt, *cvsize, *cadjncy, *cadjwgt;
635 if (cnvtxs < 2*mask || graph->nedges/
graph->nvtxs > mask/20) {
640 nvtxs =
graph->nvtxs;
642 for (
v=0;
v<nvtxs;
v++) {
663 cxadj = cgraph->
xadj;
664 cvwgt = cgraph->
vwgt;
665 cvsize = cgraph->
vsize;
671 cxadj[0] = cnvtxs = cnedges = 0;
672 for (
v=0;
v<nvtxs;
v++) {
680 cvwgt[cnvtxs] =
vwgt[
v];
685 cvsize[cnvtxs] =
vsize[
v];
691 for (
j=istart;
j<iend;
j++) {
694 if ((
m = htable[kk]) == -1) {
697 htable[kk] = nedges++;
699 else if (cadjncy[
m] == k) {
703 for (jj=0; jj<nedges; jj++) {
704 if (cadjncy[jj] == k) {
718 cvwgt[cnvtxs] +=
vwgt[u];
723 cvsize[cnvtxs] +=
vsize[u];
727 for (
j=istart;
j<iend;
j++) {
730 if ((
m = htable[kk]) == -1) {
733 htable[kk] = nedges++;
735 else if (cadjncy[
m] == k) {
739 for (jj=0; jj<nedges; jj++) {
740 if (cadjncy[jj] == k) {
753 jj = htable[cnvtxs&mask];
754 if (jj >= 0 && cadjncy[jj] != cnvtxs) {
755 for (jj=0; jj<nedges; jj++) {
756 if (cadjncy[jj] == cnvtxs)
761 if (jj >= 0 && jj < nedges && cadjncy[jj] == cnvtxs) {
762 cadjncy[jj] = cadjncy[--nedges];
763 cadjwgt[jj] = cadjwgt[nedges];
768 for (
j=0;
j<nedges;
j++)
769 htable[cadjncy[
j]&mask] = -1;
770 htable[cnvtxs&mask] = -1;
773 cxadj[++cnvtxs] = cnedges;
803 idx_t j, k,
m, istart, iend, nvtxs, nedges,
ncon, cnedges,
v, u, dovsize;
805 idx_t *cmap, *htable;
806 idx_t *cxadj, *cvwgt, *cvsize, *cadjncy, *cadjwgt;
815 nvtxs =
graph->nvtxs;
827 cxadj = cgraph->
xadj;
828 cvwgt = cgraph->
vwgt;
829 cvsize = cgraph->
vsize;
835 cxadj[0] = cnvtxs = cnedges = 0;
836 for (
v=0;
v<nvtxs;
v++) {
844 cvwgt[cnvtxs] =
vwgt[
v];
849 cvsize[cnvtxs] =
vsize[
v];
855 for (
j=istart;
j<iend;
j++) {
857 if ((
m = htable[k]) == -1) {
860 htable[k] = nedges++;
869 cvwgt[cnvtxs] +=
vwgt[u];
874 cvsize[cnvtxs] +=
vsize[u];
878 for (
j=istart;
j<iend;
j++) {
880 if ((
m = htable[k]) == -1) {
883 htable[k] = nedges++;
891 if ((
j = htable[cnvtxs]) != -1) {
893 cadjncy[
j] = cadjncy[--nedges];
894 cadjwgt[
j] = cadjwgt[nedges];
900 for (
j=0;
j<nedges;
j++)
901 htable[cadjncy[
j]] = -1;
904 cxadj[++cnvtxs] = cnedges;
935 idx_t i,
j, jj, k, kk,
l,
m, istart, iend, nvtxs, nedges,
ncon, cnedges,
938 idx_t *cmap, *htable;
939 idx_t *cxadj, *cvwgt, *cvsize, *cadjncy, *cadjwgt;
950 nvtxs =
graph->nvtxs;
961 cxadj = cgraph->
xadj;
962 cvwgt = cgraph->
vwgt;
963 cvsize = cgraph->
vsize;
969 cxadj[0] = cnvtxs = cnedges = 0;
970 for (
i=0;
i<nvtxs;
i++) {
972 if (cmap[
v] != cnvtxs)
977 cvwgt[cnvtxs] =
vwgt[
v];
982 cvsize[cnvtxs] =
vsize[
v];
988 for (
j=istart;
j<iend;
j++) {
991 if ((
m = htable[kk]) == -1) {
994 htable[kk] = nedges++;
996 else if (cadjncy[
m] == k) {
1000 for (jj=0; jj<nedges; jj++) {
1001 if (cadjncy[jj] == k) {
1007 cadjncy[nedges] = k;
1008 cadjwgt[nedges++] =
adjwgt[
j];
1015 cvwgt[cnvtxs] +=
vwgt[u];
1020 cvsize[cnvtxs] +=
vsize[u];
1024 for (
j=istart;
j<iend;
j++) {
1027 if ((
m = htable[kk]) == -1) {
1028 cadjncy[nedges] = k;
1030 htable[kk] = nedges++;
1032 else if (cadjncy[
m] == k) {
1036 for (jj=0; jj<nedges; jj++) {
1037 if (cadjncy[jj] == k) {
1043 cadjncy[nedges] = k;
1044 cadjwgt[nedges++] =
adjwgt[
j];
1050 jj = htable[cnvtxs&mask];
1051 if (jj >= 0 && cadjncy[jj] != cnvtxs) {
1052 for (jj=0; jj<nedges; jj++) {
1053 if (cadjncy[jj] == cnvtxs)
1057 if (jj >= 0 && cadjncy[jj] == cnvtxs) {
1058 cadjncy[jj] = cadjncy[--nedges];
1059 cadjwgt[jj] = cadjwgt[nedges];
1063 for (
j=0;
j<nedges;
j++)
1064 htable[cadjncy[
j]&mask] = -1;
1065 htable[cnvtxs&mask] = -1;
1068 cxadj[++cnvtxs] = cnedges;
1073 cgraph->
nedges = cnedges;
1099 cgraph->
nvtxs = cnvtxs;
1103 graph->coarser = cgraph;
1107 cgraph->
xadj =
imalloc(cnvtxs+1,
"SetupCoarseGraph: xadj");
1110 cgraph->
vwgt =
imalloc(cgraph->
ncon*cnvtxs,
"SetupCoarseGraph: vwgt");
1115 cgraph->
vsize =
imalloc(cnvtxs,
"SetupCoarseGraph: vsize");