3
\brief Functions that deal with eliminating disconnected partitions
7
\author Copyright 1997-2009, Regents of the University of Minnesota
8
\version $Id: contig.c 10513 2011-07-07 22:06:03Z karypis $
14
/*************************************************************************/
15
/*! This function finds the connected components induced by the
18
\param graph is the graph structure
19
\param where is the partitioning vector. If this is NULL, then the
20
entire graph is treated to belong into a single partition.
21
\param cptr is the ptr structure of the CSR representation of the
22
components. The length of this vector must be graph->nvtxs+1.
23
\param cind is the indices structure of the CSR representation of
24
the components. The length of this vector must be graph->nvtxs.
26
\returns the number of components that it found.
28
\note The cptr and cind parameters can be NULL, in which case only the
29
number of connected components is returned.
31
/*************************************************************************/
32
idx_t FindPartitionInducedComponents(graph_t *graph, idx_t *where,
33
idx_t *cptr, idx_t *cind)
35
idx_t i, ii, j, jj, k, me=0, nvtxs, first, last, nleft, ncmps;
37
idx_t *touched, *perm, *todo;
38
idx_t mustfree_ccsr=0, mustfree_where=0;
42
adjncy = graph->adjncy;
44
/* Deal with NULL supplied cptr/cind vectors */
46
cptr = imalloc(nvtxs+1, "FindPartitionInducedComponents: cptr");
47
cind = imalloc(nvtxs, "FindPartitionInducedComponents: cind");
51
/* Deal with NULL supplied where vector */
53
where = ismalloc(nvtxs, 0, "FindPartitionInducedComponents: where");
57
/* Allocate memory required for the BFS traversal */
58
perm = iincset(nvtxs, 0, imalloc(nvtxs, "FindPartitionInducedComponents: perm"));
59
todo = iincset(nvtxs, 0, imalloc(nvtxs, "FindPartitionInducedComponents: todo"));
60
touched = ismalloc(nvtxs, 0, "FindPartitionInducedComponents: touched");
63
/* Find the connected componends induced by the partition */
68
if (first == last) { /* Find another starting vertex */
69
cptr[++ncmps] = first;
70
ASSERT(touched[todo[0]] == 0);
79
j = todo[k] = todo[--nleft];
82
for (j=xadj[i]; j<xadj[i+1]; j++) {
84
if (where[k] == me && !touched[k]) {
90
cptr[++ncmps] = first;
93
gk_free((void **)&cptr, &cind, LTERM);
95
gk_free((void **)&where, LTERM);
97
gk_free((void **)&perm, &todo, &touched, LTERM);
103
/*************************************************************************/
104
/*! This function computes a permutation of the vertices based on a
105
breadth-first-traversal. It can be used for re-ordering the graph
106
to reduce its bandwidth for better cache locality.
108
\param ctrl is the control structure
109
\param graph is the graph structure
110
\param perm is the array that upon completion, perm[i] will store
111
the ID of the vertex that corresponds to the ith vertex in the
114
/*************************************************************************/
115
void ComputeBFSOrdering(ctrl_t *ctrl, graph_t *graph, idx_t *bfsperm)
117
idx_t i, j, k, nvtxs, first, last;
118
idx_t *xadj, *adjncy, *perm;
122
nvtxs = graph->nvtxs;
124
adjncy = graph->adjncy;
126
/* Allocate memory required for the BFS traversal */
127
perm = iincset(nvtxs, 0, iwspacemalloc(ctrl, nvtxs));
129
iincset(nvtxs, 0, bfsperm); /* this array will also store the vertices
130
still to be processed */
132
/* Find the connected componends induced by the partition */
134
while (first < nvtxs) {
135
if (first == last) { /* Find another starting vertex */
137
ASSERT(perm[k] != -1);
138
perm[k] = -1; /* mark node as being visited */
142
i = bfsperm[first++];
143
for (j=xadj[i]; j<xadj[i+1]; j++) {
145
/* if a node has been already been visited, its perm[] will be -1 */
147
/* perm[k] is the location within bfsperm of where k resides;
148
put in that location bfsperm[last] that we are about to
149
overwrite and update perm[bfsperm[last]] to reflect that. */
150
bfsperm[perm[k]] = bfsperm[last];
151
perm[bfsperm[last]] = perm[k];
153
bfsperm[last++] = k; /* put node at the end of the "queue" */
154
perm[k] = -1; /* mark node as being visited */
163
/*************************************************************************/
164
/*! This function checks whether a graph is contiguous or not.
166
/**************************************************************************/
167
idx_t IsConnected(graph_t *graph, idx_t report)
171
ncmps = FindPartitionInducedComponents(graph, NULL, NULL, NULL);
173
if (ncmps != 1 && report)
174
printf("The graph is not connected. It has %"PRIDX" connected components.\n", ncmps);
180
/*************************************************************************/
181
/*! This function checks whether or not partition pid is contigous
183
/*************************************************************************/
184
idx_t IsConnectedSubdomain(ctrl_t *ctrl, graph_t *graph, idx_t pid, idx_t report)
186
idx_t i, j, k, nvtxs, first, last, nleft, ncmps, wgt;
187
idx_t *xadj, *adjncy, *where, *touched, *queue;
190
nvtxs = graph->nvtxs;
192
adjncy = graph->adjncy;
193
where = graph->where;
195
touched = ismalloc(nvtxs, 0, "IsConnected: touched");
196
queue = imalloc(nvtxs, "IsConnected: queue");
197
cptr = imalloc(nvtxs+1, "IsConnected: cptr");
200
for (i=0; i<nvtxs; i++) {
205
for (i=0; i<nvtxs; i++) {
214
cptr[0] = 0; /* This actually points to queue */
216
while (first != nleft) {
217
if (first == last) { /* Find another starting vertex */
218
cptr[++ncmps] = first;
219
for (i=0; i<nvtxs; i++) {
220
if (where[i] == pid && !touched[i])
228
for (j=xadj[i]; j<xadj[i+1]; j++) {
230
if (where[k] == pid && !touched[k]) {
236
cptr[++ncmps] = first;
238
if (ncmps > 1 && report) {
239
printf("The graph has %"PRIDX" connected components in partition %"PRIDX":\t", ncmps, pid);
240
for (i=0; i<ncmps; i++) {
242
for (j=cptr[i]; j<cptr[i+1]; j++)
243
wgt += graph->vwgt[queue[j]];
244
printf("[%5"PRIDX" %5"PRIDX"] ", cptr[i+1]-cptr[i], wgt);
246
if (cptr[i+1]-cptr[i] == 1)
247
printf("[%"PRIDX" %"PRIDX"] ", queue[cptr[i]], xadj[queue[cptr[i]]+1]-xadj[queue[cptr[i]]]);
253
gk_free((void **)&touched, &queue, &cptr, LTERM);
255
return (ncmps == 1 ? 1 : 0);
259
/*************************************************************************/
260
/*! This function identifies the number of connected components in a graph
261
that result after removing the vertices that belong to the vertex
262
separator (i.e., graph->where[i] == 2).
263
The connected component memberships are returned in the CSR-style
264
pair of arrays cptr, cind.
266
/**************************************************************************/
267
idx_t FindSepInducedComponents(ctrl_t *ctrl, graph_t *graph, idx_t *cptr,
270
idx_t i, j, k, nvtxs, first, last, nleft, ncmps, wgt;
271
idx_t *xadj, *adjncy, *where, *touched, *queue;
273
nvtxs = graph->nvtxs;
275
adjncy = graph->adjncy;
276
where = graph->where;
278
touched = ismalloc(nvtxs, 0, "IsConnected: queue");
280
for (i=0; i<graph->nbnd; i++)
281
touched[graph->bndind[i]] = 1;
286
for (i=0; i<nvtxs; i++) {
291
for (i=0; i<nvtxs; i++) {
300
cptr[0] = 0; /* This actually points to queue */
303
while (first != nleft) {
304
if (first == last) { /* Find another starting vertex */
305
cptr[++ncmps] = first;
306
for (i=0; i<nvtxs; i++) {
315
for (j=xadj[i]; j<xadj[i+1]; j++) {
323
cptr[++ncmps] = first;
325
gk_free((void **)&touched, LTERM);
331
/*************************************************************************/
332
/*! This function finds all the connected components induced by the
333
partitioning vector in graph->where and tries to push them around to
334
remove some of them. */
335
/*************************************************************************/
336
void EliminateComponents(ctrl_t *ctrl, graph_t *graph)
338
idx_t i, ii, j, jj, k, me, nparts, nvtxs, ncon, ncmps, other,
340
idx_t *xadj, *adjncy, *vwgt, *adjwgt, *where, *pwgts;
341
idx_t *cptr, *cind, *cpvec, *pcptr, *pcind, *cwhere;
342
idx_t cid, bestcid, *cwgt, *bestcwgt;
343
idx_t ntodo, oldntodo, *todo;
346
idx_t *vmarker=NULL, *pmarker=NULL, *modind=NULL; /* volume specific work arrays */
350
nvtxs = graph->nvtxs;
353
adjncy = graph->adjncy;
355
adjwgt = (ctrl->objtype == METIS_OBJTYPE_VOL ? NULL : graph->adjwgt);
357
where = graph->where;
358
pwgts = graph->pwgts;
360
nparts = ctrl->nparts;
361
tpwgts = ctrl->tpwgts;
363
cptr = iwspacemalloc(ctrl, nvtxs+1);
364
cind = iwspacemalloc(ctrl, nvtxs);
366
ncmps = FindPartitionInducedComponents(graph, where, cptr, cind);
368
IFSET(ctrl->dbglvl, METIS_DBG_CONTIGINFO,
369
printf("I found %"PRIDX" components, for this %"PRIDX"-way partition\n",
372
/* There are more components than partitions */
373
if (ncmps > nparts) {
374
cwgt = iwspacemalloc(ctrl, ncon);
375
bestcwgt = iwspacemalloc(ctrl, ncon);
376
cpvec = iwspacemalloc(ctrl, nparts);
377
pcptr = iset(nparts+1, 0, iwspacemalloc(ctrl, nparts+1));
378
pcind = iwspacemalloc(ctrl, ncmps);
379
cwhere = iset(nvtxs, -1, iwspacemalloc(ctrl, nvtxs));
380
todo = iwspacemalloc(ctrl, ncmps);
381
cand = (rkv_t *)wspacemalloc(ctrl, nparts*sizeof(rkv_t));
383
if (ctrl->objtype == METIS_OBJTYPE_VOL) {
384
/* Vol-refinement specific working arrays */
385
modind = iwspacemalloc(ctrl, nvtxs);
386
vmarker = iset(nvtxs, 0, iwspacemalloc(ctrl, nvtxs));
387
pmarker = iset(nparts, -1, iwspacemalloc(ctrl, nparts));
391
/* Get a CSR representation of the components-2-partitions mapping */
392
for (i=0; i<ncmps; i++)
393
pcptr[where[cind[cptr[i]]]]++;
394
MAKECSR(i, nparts, pcptr);
395
for (i=0; i<ncmps; i++)
396
pcind[pcptr[where[cind[cptr[i]]]]++] = i;
397
SHIFTCSR(i, nparts, pcptr);
399
/* Assign the heaviest component of each partition to its original partition */
400
for (ntodo=0, i=0; i<nparts; i++) {
401
if (pcptr[i+1]-pcptr[i] == 1)
402
bestcid = pcind[pcptr[i]];
404
for (bestcid=-1, j=pcptr[i]; j<pcptr[i+1]; j++) {
407
for (ii=cptr[cid]; ii<cptr[cid+1]; ii++)
408
iaxpy(ncon, 1, vwgt+cind[ii]*ncon, 1, cwgt, 1);
409
if (bestcid == -1 || isum(ncon, bestcwgt, 1) < isum(ncon, cwgt, 1)) {
411
icopy(ncon, cwgt, bestcwgt);
414
/* Keep track of those that need to be dealt with */
415
for (j=pcptr[i]; j<pcptr[i+1]; j++) {
416
if (pcind[j] != bestcid)
417
todo[ntodo++] = pcind[j];
421
for (j=cptr[bestcid]; j<cptr[bestcid+1]; j++) {
422
ASSERT(where[cind[j]] == i);
430
for (i=0; i<ntodo; i++) {
432
me = where[cind[cptr[cid]]]; /* Get the domain of this component */
434
/* Determine the weight of the block to be moved */
436
for (j=cptr[cid]; j<cptr[cid+1]; j++)
437
iaxpy(ncon, 1, vwgt+cind[j]*ncon, 1, cwgt, 1);
439
IFSET(ctrl->dbglvl, METIS_DBG_CONTIGINFO,
440
printf("Trying to move %"PRIDX" [%"PRIDX"] from %"PRIDX"\n",
441
cid, isum(ncon, cwgt, 1), me));
443
/* Determine the connectivity */
444
iset(nparts, 0, cpvec);
445
for (j=cptr[cid]; j<cptr[cid+1]; j++) {
447
for (jj=xadj[ii]; jj<xadj[ii+1]; jj++)
448
if (cwhere[adjncy[jj]] != -1)
449
cpvec[cwhere[adjncy[jj]]] += (adjwgt ? adjwgt[jj] : 1);
452
/* Put the neighbors into a cand[] array for sorting */
453
for (ncand=0, j=0; j<nparts; j++) {
455
cand[ncand].key = cpvec[j];
456
cand[ncand++].val = j;
462
rkvsortd(ncand, cand);
464
/* Limit the moves to only the top candidates, which are defined as
465
those with connectivity at least 50% of the best.
466
This applies only when ncon=1, as for multi-constraint, balancing
469
for (j=1; j<ncand; j++) {
470
if (cand[j].key < .5*cand[0].key)
476
/* Now among those, select the one with the best balance */
477
target = cand[0].val;
478
for (j=1; j<ncand; j++) {
479
if (BetterBalanceKWay(ncon, cwgt, ctrl->ubfactors,
480
1, pwgts+target*ncon, ctrl->pijbm+target*ncon,
481
1, pwgts+cand[j].val*ncon, ctrl->pijbm+cand[j].val*ncon))
482
target = cand[j].val;
485
IFSET(ctrl->dbglvl, METIS_DBG_CONTIGINFO,
486
printf("\tMoving it to %"PRIDX" [%"PRIDX"] [%"PRIDX"]\n", target, cpvec[target], ncand));
488
/* Note that as a result of a previous movement, a connected component may
489
now will like to stay to its original partition */
491
switch (ctrl->objtype) {
492
case METIS_OBJTYPE_CUT:
493
MoveGroupContigForCut(ctrl, graph, target, cid, cptr, cind);
496
case METIS_OBJTYPE_VOL:
497
MoveGroupContigForVol(ctrl, graph, target, cid, cptr, cind,
498
vmarker, pmarker, modind);
502
gk_errexit(SIGERR, "Unknown objtype %d\n", ctrl->objtype);
506
/* Update the cwhere vector */
507
for (j=cptr[cid]; j<cptr[cid+1]; j++)
508
cwhere[cind[j]] = target;
510
todo[i] = todo[--ntodo];
512
if (oldntodo == ntodo) {
513
IFSET(ctrl->dbglvl, METIS_DBG_CONTIGINFO, printf("Stopped at ntodo: %"PRIDX"\n", ntodo));
518
for (i=0; i<nvtxs; i++)
519
ASSERT(where[i] == cwhere[i]);
527
/*************************************************************************/
528
/*! This function moves a collection of vertices and updates their rinfo
530
/*************************************************************************/
531
void MoveGroupContigForCut(ctrl_t *ctrl, graph_t *graph, idx_t to, idx_t gid,
532
idx_t *ptr, idx_t *ind)
534
idx_t i, ii, iii, j, jj, k, l, nvtxs, nbnd, from, me;
535
idx_t *xadj, *adjncy, *adjwgt, *where, *bndptr, *bndind;
539
nvtxs = graph->nvtxs;
541
adjncy = graph->adjncy;
542
adjwgt = graph->adjwgt;
544
where = graph->where;
545
bndptr = graph->bndptr;
546
bndind = graph->bndind;
550
for (iii=ptr[gid]; iii<ptr[gid+1]; iii++) {
554
myrinfo = graph->ckrinfo+i;
555
if (myrinfo->inbr == -1) {
556
myrinfo->inbr = cnbrpoolGetNext(ctrl, xadj[i+1]-xadj[i]+1);
559
mynbrs = ctrl->cnbrpool + myrinfo->inbr;
561
/* find the location of 'to' in myrinfo or create it if it is not there */
562
for (k=0; k<myrinfo->nnbrs; k++) {
563
if (mynbrs[k].pid == to)
566
if (k == myrinfo->nnbrs) {
572
graph->mincut -= mynbrs[k].ed-myrinfo->id;
574
/* Update ID/ED and BND related information for the moved vertex */
575
iaxpy(graph->ncon, 1, graph->vwgt+i*graph->ncon, 1, graph->pwgts+to*graph->ncon, 1);
576
iaxpy(graph->ncon, -1, graph->vwgt+i*graph->ncon, 1, graph->pwgts+from*graph->ncon, 1);
577
UpdateMovedVertexInfoAndBND(i, from, k, to, myrinfo, mynbrs, where, nbnd,
578
bndptr, bndind, BNDTYPE_REFINE);
580
/* Update the degrees of adjacent vertices */
581
for (j=xadj[i]; j<xadj[i+1]; j++) {
584
myrinfo = graph->ckrinfo+ii;
586
UpdateAdjacentVertexInfoAndBND(ctrl, ii, xadj[ii+1]-xadj[ii], me,
587
from, to, myrinfo, adjwgt[j], nbnd, bndptr, bndind, BNDTYPE_REFINE);
590
ASSERT(CheckRInfo(ctrl, graph->ckrinfo+i));
597
/*************************************************************************/
598
/*! This function moves a collection of vertices and updates their rinfo
600
/*************************************************************************/
601
void MoveGroupContigForVol(ctrl_t *ctrl, graph_t *graph, idx_t to, idx_t gid,
602
idx_t *ptr, idx_t *ind, idx_t *vmarker, idx_t *pmarker,
605
idx_t i, ii, iii, j, jj, k, l, nvtxs, from, me, other, xgain;
606
idx_t *xadj, *vsize, *adjncy, *where;
607
vkrinfo_t *myrinfo, *orinfo;
608
vnbr_t *mynbrs, *onbrs;
610
nvtxs = graph->nvtxs;
612
vsize = graph->vsize;
613
adjncy = graph->adjncy;
614
where = graph->where;
616
for (iii=ptr[gid]; iii<ptr[gid+1]; iii++) {
620
myrinfo = graph->vkrinfo+i;
621
if (myrinfo->inbr == -1) {
622
myrinfo->inbr = vnbrpoolGetNext(ctrl, xadj[i+1]-xadj[i]+1);
625
mynbrs = ctrl->vnbrpool + myrinfo->inbr;
627
xgain = (myrinfo->nid == 0 && myrinfo->ned > 0 ? vsize[i] : 0);
629
/* find the location of 'to' in myrinfo or create it if it is not there */
630
for (k=0; k<myrinfo->nnbrs; k++) {
631
if (mynbrs[k].pid == to)
634
if (k == myrinfo->nnbrs) {
635
if (myrinfo->nid > 0)
638
/* determine the volume gain resulting from that move */
639
for (j=xadj[i]; j<xadj[i+1]; j++) {
642
orinfo = graph->vkrinfo+ii;
643
onbrs = ctrl->vnbrpool + orinfo->inbr;
647
/* Same subdomain vertex: Decrease the gain if 'to' is a new neighbor. */
648
for (l=0; l<orinfo->nnbrs; l++) {
649
if (onbrs[l].pid == to)
652
if (l == orinfo->nnbrs)
656
/* Remote vertex: increase if 'to' is a new subdomain */
657
for (l=0; l<orinfo->nnbrs; l++) {
658
if (onbrs[l].pid == to)
661
if (l == orinfo->nnbrs)
664
/* Remote vertex: decrease if i is the only connection to 'from' */
665
for (l=0; l<orinfo->nnbrs; l++) {
666
if (onbrs[l].pid == from && onbrs[l].ned == 1) {
673
graph->minvol -= xgain;
674
graph->mincut -= -myrinfo->nid;
677
graph->minvol -= (xgain + mynbrs[k].gv);
678
graph->mincut -= mynbrs[k].ned-myrinfo->nid;
682
/* Update where and pwgts */
684
iaxpy(graph->ncon, 1, graph->vwgt+i*graph->ncon, 1, graph->pwgts+to*graph->ncon, 1);
685
iaxpy(graph->ncon, -1, graph->vwgt+i*graph->ncon, 1, graph->pwgts+from*graph->ncon, 1);
687
/* Update the id/ed/gains/bnd of potentially affected nodes */
688
KWayVolUpdate(ctrl, graph, i, from, to, NULL, NULL, NULL, NULL,
689
NULL, BNDTYPE_REFINE, vmarker, pmarker, modind);
691
/*CheckKWayVolPartitionParams(ctrl, graph);*/
694
ASSERT(ComputeCut(graph, where) == graph->mincut);
695
ASSERTP(ComputeVolume(graph, where) == graph->minvol,
696
("%"PRIDX" %"PRIDX"\n", ComputeVolume(graph, where), graph->minvol));
added
removed
elmergrid/src/metis-5.1.0/libmetis/contig.c
