loop inside METIS took too long to exit


I noticed that METIS-5.0pre2 can not get exit out of the following loop in match.c (line 213):

for (ii=0; iiii; j--) {
k = perm[j];
if (match[k] == UNMATCHED && xadj[k] < xadj[k+1]) {
maxidx = k;

cmap[i] = cmap[maxidx] = cnvtxs++;
match[i] = maxidx;
match[maxidx] = i;

In my case, nvtxs = 207M. This loop seems N^2 operation, and may take forever to exit if there is no break. I also noticed the same problem in METIS 4.0, file match.c, line 214. The function the loop is present is Match_SHEM. So I guess this has something to do with coarsening.

Does someone have the same problem before or know what is going on here?



RE: The above will not be N^2,

The above will not be N^2, unless of-course all the vertices in your graph have no edges (or a large fraction of them have no edges) (i.e., they are zero-degree vertices).