24 int i, j, k, sum, gsize;
28 if (OpType ==
OP_KMETIS && ncon == 1 && (wgtflag&2) == 0 && (wgtflag&1) == 0) {
36 graph->
nedges = xadj[nvtxs];
54 if ((wgtflag&2) == 0) {
61 if ((wgtflag&1) == 0) {
73 for (i=0; i<nvtxs; i++) {
75 for (j=xadj[i]; j<xadj[i+1]; j++)
94 for (i=0; i<ncon; i++)
97 nvwgt = graph->
nvwgt =
fmalloc(ncon*nvtxs,
"SetUpGraph: nvwgt");
99 for (i=0; i<nvtxs; i++) {
100 for (j=0; j<ncon; j++)
101 nvwgt[i*ncon+j] = (1.0*vwgt[i*ncon+j])/(1.0*tvwgt[j]);
106 if ((wgtflag&1) == 0) {
117 for (i=0; i<nvtxs; i++) {
119 for (j=xadj[i]; j<xadj[i+1]; j++)
132 for (i=0; i<nvtxs; i++)
148 graph->
nvtxs = nvtxs;
149 graph->
nedges = xadj[nvtxs];
161 for (i=0; i<nvtxs; i++)
178 graph->
nvtxs = nvtxs;
179 graph->
nedges = xadj[nvtxs];
185 graph->
nvwgt =
fmalloc(nvtxs*ncon,
"SetUpGraph2: graph->nvwgt");
192 for (i=0; i<nvtxs; i++) {
194 for (j=xadj[i]; j<xadj[i+1]; j++)
202 for (i=0; i<nvtxs; i++)
214 int i, j, k, sum, gsize;
221 graph->
nvtxs = nvtxs;
222 graph->
nedges = xadj[nvtxs];
229 if ((wgtflag&2) == 0)
231 if ((wgtflag&1) == 0)
240 if ((wgtflag&2) == 0) {
247 if ((wgtflag&1) == 0) {
252 graph->
vsize = vsize;
258 for (i=0; i<nvtxs; i++) {
259 for (j=xadj[i]; j<xadj[i+1]; j++)
260 adjwgt[j] = 1+vsize[i]+vsize[adjncy[j]];
268 for (i=0; i<nvtxs; i++) {
270 for (j=xadj[i]; j<xadj[i+1]; j++)
281 if ((wgtflag&1) == 0)
290 if ((wgtflag&2) == 0)
291 vwgt =
idxsmalloc(nvtxs, 1,
"SetUpGraph: vwgt");
293 for (i=0; i<ncon; i++)
296 nvwgt = graph->
nvwgt =
fmalloc(ncon*nvtxs,
"SetUpGraph: nvwgt");
298 for (i=0; i<nvtxs; i++) {
299 for (j=0; j<ncon; j++)
300 nvwgt[i*ncon+j] = (1.0*vwgt[i*ncon+j])/(1.0*tvwgt[j]);
302 if ((wgtflag&2) == 0)
307 if ((wgtflag&1) == 0) {
312 graph->
vsize = vsize;
318 for (i=0; i<nvtxs; i++) {
319 for (j=xadj[i]; j<xadj[i+1]; j++)
320 adjwgt[j] = 1+vsize[i]+vsize[adjncy[j]];
327 for (i=0; i<nvtxs; i++) {
329 for (j=xadj[i]; j<xadj[i+1]; j++)
342 for (i=0; i<nvtxs; i++)
354 int i, j, k, l, tmp, nvtxs;
355 idxtype *xadj, *adjncy, *adjwgt;
357 nvtxs = graph->
nvtxs;
362 for (i=0; i<nvtxs; i++) {
363 l = xadj[i+1]-xadj[i];
364 for (j=xadj[i]; j<xadj[i+1]; j++) {
366 SWAP(adjncy[j], adjncy[k], tmp);
367 SWAP(adjwgt[j], adjwgt[k], tmp);
378 int i, j, k, nvtxs, first, last, nleft, ncmps, wgt;
379 idxtype *xadj, *adjncy, *where, *touched, *queue;
382 nvtxs = graph->
nvtxs;
385 where = graph->
where;
387 touched =
idxsmalloc(nvtxs, 0,
"IsConnected: touched");
388 queue =
idxmalloc(nvtxs,
"IsConnected: queue");
389 cptr =
idxmalloc(nvtxs,
"IsConnected: cptr");
392 for (i=0; i<nvtxs; i++) {
397 for (i=0; i<nvtxs; i++) {
408 while (first != nleft) {
410 cptr[++ncmps] = first;
411 for (i=0; i<nvtxs; i++) {
412 if (where[i] == pid && !touched[i])
420 for (j=xadj[i]; j<xadj[i+1]; j++) {
422 if (where[k] == pid && !touched[k]) {
428 cptr[++ncmps] = first;
430 if (ncmps > 1 && report) {
431 printf(
"The graph has %d connected components in partition %d:\t", ncmps, pid);
432 for (i=0; i<ncmps; i++) {
434 for (j=cptr[i]; j<cptr[i+1]; j++)
435 wgt += graph->
vwgt[queue[j]];
436 printf(
"[%5d %5d] ", cptr[i+1]-cptr[i], wgt);
447 return (ncmps == 1 ? 1 : 0);
456 int i, j, k, nvtxs, first, last;
457 idxtype *xadj, *adjncy, *touched, *queue;
459 nvtxs = graph->
nvtxs;
463 touched =
idxsmalloc(nvtxs, 0,
"IsConnected: touched");
464 queue =
idxmalloc(nvtxs,
"IsConnected: queue");
470 while (first < last) {
472 for (j=xadj[i]; j<xadj[i+1]; j++) {
481 if (first != nvtxs && report)
482 printf(
"The graph is not connected. It has %d disconnected vertices!\n", nvtxs-first);
484 return (first == nvtxs ? 1 : 0);
493 int i, j, k, nvtxs, first, last, nleft, ncmps, wgt;
494 idxtype *xadj, *adjncy, *where, *touched, *queue;
497 nvtxs = graph->
nvtxs;
500 where = graph->
where;
502 touched =
idxsmalloc(nvtxs, 0,
"IsConnected: touched");
503 queue =
idxmalloc(nvtxs,
"IsConnected: queue");
504 cptr =
idxmalloc(nvtxs,
"IsConnected: cptr");
513 while (first != nleft) {
515 cptr[++ncmps] = first;
516 for (i=0; i<nvtxs; i++) {
525 for (j=xadj[i]; j<xadj[i+1]; j++) {
533 cptr[++ncmps] = first;
535 if (ncmps > 1 && report) {
536 printf(
"%d connected components:\t", ncmps);
537 for (i=0; i<ncmps; i++) {
538 if (cptr[i+1]-cptr[i] > 200)
539 printf(
"[%5d] ", cptr[i+1]-cptr[i]);
546 return (ncmps == 1 ? 1 : 0);
556 int i, j, k, nvtxs, first, last, nleft, ncmps, wgt;
557 idxtype *xadj, *adjncy, *where, *touched, *queue;
559 nvtxs = graph->
nvtxs;
562 where = graph->
where;
564 touched =
idxsmalloc(nvtxs, 0,
"IsConnected: queue");
566 for (i=0; i<graph->
nbnd; i++)
567 touched[graph->
bndind[i]] = 1;
572 for (i=0; i<nvtxs; i++) {
577 for (i=0; i<nvtxs; i++) {
588 while (first != nleft) {
590 cptr[++ncmps] = first;
591 for (i=0; i<nvtxs; i++) {
600 for (j=xadj[i]; j<xadj[i+1]; j++) {
608 cptr[++ncmps] = first;
#define IsConnectedSubdomain
void GKfree(void **ptr1,...)