summaryrefslogtreecommitdiff
path: root/benchmarks/CUDA/DG/3rdParty/ParMetis-3.1/METISLib/match.c
diff options
context:
space:
mode:
Diffstat (limited to 'benchmarks/CUDA/DG/3rdParty/ParMetis-3.1/METISLib/match.c')
-rw-r--r--benchmarks/CUDA/DG/3rdParty/ParMetis-3.1/METISLib/match.c267
1 files changed, 0 insertions, 267 deletions
diff --git a/benchmarks/CUDA/DG/3rdParty/ParMetis-3.1/METISLib/match.c b/benchmarks/CUDA/DG/3rdParty/ParMetis-3.1/METISLib/match.c
deleted file mode 100644
index 509f457..0000000
--- a/benchmarks/CUDA/DG/3rdParty/ParMetis-3.1/METISLib/match.c
+++ /dev/null
@@ -1,267 +0,0 @@
-/*
- * 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/07/16 15:55:06 karypis 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 *xadj, *vwgt, *adjncy, *adjwgt;
- idxtype *match, *cmap, *perm;
-
- IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->MatchTmr));
-
- nvtxs = graph->nvtxs;
- xadj = graph->xadj;
- vwgt = graph->vwgt;
- adjncy = graph->adjncy;
- adjwgt = graph->adjwgt;
-
- 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 */
- for (j=xadj[i]; j<xadj[i+1]; j++) {
- if (match[adjncy[j]] == UNMATCHED && vwgt[i]+vwgt[adjncy[j]] <= ctrl->maxvwgt) {
- maxidx = adjncy[j];
- 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 *xadj, *adjncy;
- idxtype *match, *cmap, *perm;
-
- IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->MatchTmr));
-
- nvtxs = graph->nvtxs;
- xadj = graph->xadj;
- adjncy = graph->adjncy;
-
- 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 */
- for (j=xadj[i]; j<xadj[i+1]; j++) {
- if (match[adjncy[j]] == UNMATCHED) {
- maxidx = adjncy[j];
- 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 *xadj, *vwgt, *adjncy, *adjwgt;
- idxtype *match, *cmap, *perm;
-
- IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->MatchTmr));
-
- nvtxs = graph->nvtxs;
- xadj = graph->xadj;
- vwgt = graph->vwgt;
- adjncy = graph->adjncy;
- adjwgt = graph->adjwgt;
-
- 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 */
- for (j=xadj[i]; j<xadj[i+1]; j++) {
- k = adjncy[j];
- if (match[k] == UNMATCHED && maxwgt < adjwgt[j] && vwgt[i]+vwgt[k] <= ctrl->maxvwgt) {
- maxwgt = adjwgt[j];
- maxidx = adjncy[j];
- }
- }
-
- 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 *xadj, *vwgt, *adjncy, *adjwgt;
- idxtype *match, *cmap, *degrees, *perm, *tperm;
-
- IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->MatchTmr));
-
- nvtxs = graph->nvtxs;
- xadj = graph->xadj;
- vwgt = graph->vwgt;
- adjncy = graph->adjncy;
- adjwgt = graph->adjwgt;
-
- 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);
- avgdegree = 0.7*(xadj[nvtxs]/nvtxs);
- for (i=0; i<nvtxs; i++)
- degrees[i] = (xadj[i+1]-xadj[i] > avgdegree ? avgdegree : xadj[i+1]-xadj[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 */
- if (xadj[i] < xadj[i+1])
- 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 */
- for (j=xadj[i]; j<xadj[i+1]; j++) {
- if (match[adjncy[j]] == UNMATCHED && maxwgt < adjwgt[j] && vwgt[i]+vwgt[adjncy[j]] <= ctrl->maxvwgt) {
- maxwgt = adjwgt[j];
- maxidx = adjncy[j];
- }
- }
-
- 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);
-}
-
generated by cgit v1.3 (git 2.53.0) at 2026-07-10 22:37:04 +0000