# SCM Repository

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

# View of /pkg/src/Metis/match.c

Revision 10 - (download) (as text) (annotate)
Mon Mar 22 20:20:05 2004 UTC (16 years ago) by bates
File size: 6903 byte(s)
`Initial import`
```/*
* Copyright 1997, Regents of the University of Minnesota
*
* match.c
*
* This file contains the code that computes matchings and creates the next
* level coarse graph.
*
* Started 7/23/97
* George
*
* \$Id: match.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 Match_RM(CtrlType *ctrl, GraphType *graph)
{
int i, ii, j, nvtxs, cnvtxs, maxidx;
idxtype *match, *cmap, *perm;

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

nvtxs = graph->nvtxs;
vwgt = graph->vwgt;

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[adjncy[j]] == UNMATCHED && vwgt[i]+vwgt[adjncy[j]] <= ctrl->maxvwgt) {
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 Match_RM_NVW(CtrlType *ctrl, GraphType *graph)
{
int i, ii, j, nvtxs, cnvtxs, maxidx;
idxtype *match, *cmap, *perm;

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

nvtxs = graph->nvtxs;

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[adjncy[j]] == UNMATCHED) {
break;
}
}

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

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

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

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

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

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

nvtxs = graph->nvtxs;
vwgt = graph->vwgt;

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] && vwgt[i]+vwgt[k] <= ctrl->maxvwgt) {
}
}

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 Match_SHEM(CtrlType *ctrl, GraphType *graph)
{
int i, ii, j, k, nvtxs, cnvtxs, maxidx, maxwgt, avgdegree;
idxtype *match, *cmap, *degrees, *perm, *tperm;

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

nvtxs = graph->nvtxs;
vwgt = graph->vwgt;

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];
if (match[k] == UNMATCHED && xadj[k] < xadj[k+1]) {
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[adjncy[j]] == UNMATCHED && maxwgt < adjwgt[j] && vwgt[i]+vwgt[adjncy[j]] <= ctrl->maxvwgt) {
}
}

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);
}

```

 root@r-forge.r-project.org ViewVC Help Powered by ViewVC 1.0.0
Thanks to: