SCM Repository

[matrix] View of /pkg/src/Metis/mmatch.c
 [matrix] / pkg / src / Metis / mmatch.c

View of /pkg/src/Metis/mmatch.c

Mon Mar 22 20:20:05 2004 UTC (15 years, 11 months ago) by bates
File size: 13323 byte(s)
`Initial import`
```/*
* Copyright 1997, Regents of the University of Minnesota
*
* mmatch.c
*
* This file contains the code that computes matchings and creates the next
* level coarse graph.
*
* Started 7/23/97
* George
*
* \$Id: mmatch.c,v 1.1 2003/12/31 21:32:30 bates Exp \$
*
*/

#include <metis.h>

/*************************************************************************
* This function finds a matching using the HEM heuristic
**************************************************************************/
void MCMatch_RM(CtrlType *ctrl, GraphType *graph)
{
int i, ii, j, k, nvtxs, ncon, cnvtxs, maxidx;
idxtype *match, *cmap, *perm;
float *nvwgt;

IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->MatchTmr));

nvtxs = graph->nvtxs;
ncon = graph->ncon;
nvwgt = graph->nvwgt;

cmap = graph->cmap;
match = idxset(nvtxs, UNMATCHED, idxwspacemalloc(ctrl, nvtxs));

perm = idxwspacemalloc(ctrl, nvtxs);
RandomPermute(nvtxs, perm, 1);

cnvtxs = 0;
for (ii=0; ii<nvtxs; ii++) {
i = perm[ii];

if (match[i] == UNMATCHED) {  /* Unmatched */
maxidx = i;

/* Find a random matching, subject to maxvwgt constraints */
if (match[k] == UNMATCHED && AreAllVwgtsBelowFast(ncon, nvwgt+i*ncon, nvwgt+k*ncon, ctrl->nmaxvwgt)) {
maxidx = k;
break;
}
}

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

IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->MatchTmr));

CreateCoarseGraph(ctrl, graph, cnvtxs, match, perm);

idxwspacefree(ctrl, nvtxs);
idxwspacefree(ctrl, nvtxs);
}

/*************************************************************************
* This function finds a matching using the HEM heuristic
**************************************************************************/
void MCMatch_HEM(CtrlType *ctrl, GraphType *graph)
{
int i, ii, j, k, l, nvtxs, cnvtxs, ncon, maxidx, maxwgt;
idxtype *match, *cmap, *perm;
float *nvwgt;

IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->MatchTmr));

nvtxs = graph->nvtxs;
ncon = graph->ncon;
nvwgt = graph->nvwgt;

cmap = graph->cmap;
match = idxset(nvtxs, UNMATCHED, idxwspacemalloc(ctrl, nvtxs));

perm = idxwspacemalloc(ctrl, nvtxs);
RandomPermute(nvtxs, perm, 1);

cnvtxs = 0;
for (ii=0; ii<nvtxs; ii++) {
i = perm[ii];

if (match[i] == UNMATCHED) {  /* Unmatched */
maxidx = i;
maxwgt = 0;

/* Find a heavy-edge matching, subject to maxvwgt constraints */
if (match[k] == UNMATCHED && maxwgt <= adjwgt[j] &&
AreAllVwgtsBelowFast(ncon, nvwgt+i*ncon, nvwgt+k*ncon, ctrl->nmaxvwgt)) {
}
}

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

IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->MatchTmr));

CreateCoarseGraph(ctrl, graph, cnvtxs, match, perm);

idxwspacefree(ctrl, nvtxs);
idxwspacefree(ctrl, nvtxs);
}

/*************************************************************************
* This function finds a matching using the HEM heuristic
**************************************************************************/
void MCMatch_SHEM(CtrlType *ctrl, GraphType *graph)
{
int i, ii, j, k, nvtxs, cnvtxs, ncon, maxidx, maxwgt, avgdegree;
idxtype *match, *cmap, *degrees, *perm, *tperm;
float *nvwgt;

IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->MatchTmr));

nvtxs = graph->nvtxs;
ncon = graph->ncon;
nvwgt = graph->nvwgt;

cmap = graph->cmap;
match = idxset(nvtxs, UNMATCHED, idxwspacemalloc(ctrl, nvtxs));

perm = idxwspacemalloc(ctrl, nvtxs);
tperm = idxwspacemalloc(ctrl, nvtxs);
degrees = idxwspacemalloc(ctrl, nvtxs);

RandomPermute(nvtxs, tperm, 1);
for (i=0; i<nvtxs; i++)
BucketSortKeysInc(nvtxs, avgdegree, degrees, tperm, perm);

cnvtxs = 0;

/* Take care any islands. Islands are matched with non-islands due to coarsening */
for (ii=0; ii<nvtxs; ii++) {
i = perm[ii];

if (match[i] == UNMATCHED) {  /* Unmatched */
break;

maxidx = i;
for (j=nvtxs-1; j>ii; j--) {
k = perm[j];
maxidx = k;
break;
}
}

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

/* Continue with normal matching */
for (; ii<nvtxs; ii++) {
i = perm[ii];

if (match[i] == UNMATCHED) {  /* Unmatched */
maxidx = i;
maxwgt = 0;

/* Find a heavy-edge matching, subject to maxvwgt constraints */
if (match[k] == UNMATCHED && maxwgt <= adjwgt[j] &&
AreAllVwgtsBelowFast(ncon, nvwgt+i*ncon, nvwgt+k*ncon, ctrl->nmaxvwgt)) {
}
}

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

IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->MatchTmr));

idxwspacefree(ctrl, nvtxs);  /* degrees */
idxwspacefree(ctrl, nvtxs);  /* tperm */

CreateCoarseGraph(ctrl, graph, cnvtxs, match, perm);

idxwspacefree(ctrl, nvtxs);
idxwspacefree(ctrl, nvtxs);
}

/*************************************************************************
* This function finds a matching using the HEM heuristic
**************************************************************************/
void MCMatch_SHEBM(CtrlType *ctrl, GraphType *graph, int norm)
{
int i, ii, j, k, nvtxs, cnvtxs, ncon, maxidx, maxwgt, avgdegree;
idxtype *match, *cmap, *degrees, *perm, *tperm;
float *nvwgt;

IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->MatchTmr));

nvtxs = graph->nvtxs;
ncon = graph->ncon;
nvwgt = graph->nvwgt;

cmap = graph->cmap;
match = idxset(nvtxs, UNMATCHED, idxwspacemalloc(ctrl, nvtxs));

perm = idxwspacemalloc(ctrl, nvtxs);
tperm = idxwspacemalloc(ctrl, nvtxs);
degrees = idxwspacemalloc(ctrl, nvtxs);

RandomPermute(nvtxs, tperm, 1);
for (i=0; i<nvtxs; i++)
BucketSortKeysInc(nvtxs, avgdegree, degrees, tperm, perm);

cnvtxs = 0;

/* Take care any islands. Islands are matched with non-islands due to coarsening */
for (ii=0; ii<nvtxs; ii++) {
i = perm[ii];

if (match[i] == UNMATCHED) {  /* Unmatched */
break;

maxidx = i;
for (j=nvtxs-1; j>ii; j--) {
k = perm[j];
maxidx = k;
break;
}
}

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

/* Continue with normal matching */
for (; ii<nvtxs; ii++) {
i = perm[ii];

if (match[i] == UNMATCHED) {  /* Unmatched */
maxidx = i;
maxwgt = -1;

/* Find a heavy-edge matching, subject to maxvwgt constraints */

if (match[k] == UNMATCHED &&
AreAllVwgtsBelowFast(ncon, nvwgt+i*ncon, nvwgt+k*ncon, ctrl->nmaxvwgt) &&
BetterVBalance(ncon, norm, nvwgt+i*ncon, nvwgt+maxidx*ncon, nvwgt+k*ncon) >= 0
)
)
) {
maxidx = k;
}
}

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

IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->MatchTmr));

idxwspacefree(ctrl, nvtxs);  /* degrees */
idxwspacefree(ctrl, nvtxs);  /* tperm */

CreateCoarseGraph(ctrl, graph, cnvtxs, match, perm);

idxwspacefree(ctrl, nvtxs);
idxwspacefree(ctrl, nvtxs);
}

/*************************************************************************
* This function finds a matching using the HEM heuristic
**************************************************************************/
void MCMatch_SBHEM(CtrlType *ctrl, GraphType *graph, int norm)
{
int i, ii, j, k, nvtxs, cnvtxs, ncon, maxidx, maxwgt, avgdegree;
idxtype *match, *cmap, *degrees, *perm, *tperm;
float *nvwgt, vbal;

IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->MatchTmr));

nvtxs = graph->nvtxs;
ncon = graph->ncon;
nvwgt = graph->nvwgt;

cmap = graph->cmap;
match = idxset(nvtxs, UNMATCHED, idxwspacemalloc(ctrl, nvtxs));

perm = idxwspacemalloc(ctrl, nvtxs);
tperm = idxwspacemalloc(ctrl, nvtxs);
degrees = idxwspacemalloc(ctrl, nvtxs);

RandomPermute(nvtxs, tperm, 1);
for (i=0; i<nvtxs; i++)
BucketSortKeysInc(nvtxs, avgdegree, degrees, tperm, perm);

cnvtxs = 0;

/* Take care any islands. Islands are matched with non-islands due to coarsening */
for (ii=0; ii<nvtxs; ii++) {
i = perm[ii];

if (match[i] == UNMATCHED) {  /* Unmatched */
break;

maxidx = i;
for (j=nvtxs-1; j>ii; j--) {
k = perm[j];
maxidx = k;
break;
}
}

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

/* Continue with normal matching */
for (; ii<nvtxs; ii++) {
i = perm[ii];

if (match[i] == UNMATCHED) {  /* Unmatched */
maxidx = i;
maxwgt = -1;
vbal = 0.0;

/* Find a heavy-edge matching, subject to maxvwgt constraints */
if (match[k] == UNMATCHED && AreAllVwgtsBelowFast(ncon, nvwgt+i*ncon, nvwgt+k*ncon, ctrl->nmaxvwgt)) {
if (maxidx != i)
vbal = BetterVBalance(ncon, norm, nvwgt+i*ncon, nvwgt+maxidx*ncon, nvwgt+k*ncon);

if (vbal > 0 || (vbal > -.01 && maxwgt < adjwgt[j])) {
maxidx = k;
}
}
}

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

IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->MatchTmr));

idxwspacefree(ctrl, nvtxs);  /* degrees */
idxwspacefree(ctrl, nvtxs);  /* tperm */

CreateCoarseGraph(ctrl, graph, cnvtxs, match, perm);

idxwspacefree(ctrl, nvtxs);
idxwspacefree(ctrl, nvtxs);
}

/*************************************************************************
* This function checks if v+u2 provides a better balance in the weight
* vector that v+u1
**************************************************************************/
float BetterVBalance(int ncon, int norm, float *vwgt, float *u1wgt, float *u2wgt)
{
int i;
float sum1, sum2, max1, max2, min1, min2, diff1, diff2;

if (norm == -1) {
max1 = min1 = vwgt[0]+u1wgt[0];
max2 = min2 = vwgt[0]+u2wgt[0];
sum1 = vwgt[0]+u1wgt[0];
sum2 = vwgt[0]+u2wgt[0];

for (i=1; i<ncon; i++) {
if (max1 < vwgt[i]+u1wgt[i])
max1 = vwgt[i]+u1wgt[i];
if (min1 > vwgt[i]+u1wgt[i])
min1 = vwgt[i]+u1wgt[i];

if (max2 < vwgt[i]+u2wgt[i])
max2 = vwgt[i]+u2wgt[i];
if (min2 > vwgt[i]+u2wgt[i])
min2 = vwgt[i]+u2wgt[i];

sum1 += vwgt[i]+u1wgt[i];
sum2 += vwgt[i]+u2wgt[i];
}

if (sum1 == 0.0)
return 1;
else if (sum2 == 0.0)
return -1;
else
return ((max1-min1)/sum1) - ((max2-min2)/sum2);
}
else if (norm == 1) {
sum1 = sum2 = 0.0;
for (i=0; i<ncon; i++) {
sum1 += vwgt[i]+u1wgt[i];
sum2 += vwgt[i]+u2wgt[i];
}
sum1 = sum1/(1.0*ncon);
sum2 = sum2/(1.0*ncon);

diff1 = diff2 = 0.0;
for (i=0; i<ncon; i++) {
diff1 += fabs(sum1 - (vwgt[i]+u1wgt[i]));
diff2 += fabs(sum2 - (vwgt[i]+u2wgt[i]));
}

return diff1 - diff2;
}
else {
errexit("Unknown norm: %d\n", norm);
}
return 0.0;
}

/*************************************************************************
* This function checks if the vertex weights of two vertices are below
* a given set of values
**************************************************************************/
int AreAllVwgtsBelowFast(int ncon, float *vwgt1, float *vwgt2, float limit)
{
int i;

for (i=0; i<ncon; i++)
if (vwgt1[i] + vwgt2[i] > limit)
return 0;

return 1;
}

```