source: inundation/pymetis/metis-4.0/Lib/match.c @ 3381

Last change on this file since 3381 was 2051, checked in by jack, 19 years ago

Python interface to metis. Currently provides only the
METIS_PartMeshNodal function, since that is what is currently needed for partitioning.
Module name is metis.
File size: 6.7 KB
RevLine 
[2051]1/*
2 * Copyright 1997, Regents of the University of Minnesota
3 *
4 * match.c
5 *
6 * This file contains the code that computes matchings and creates the next
7 * level coarse graph.
8 *
9 * Started 7/23/97
10 * George
11 *
12 * $Id: match.c,v 1.1 1998/11/27 17:59:18 karypis Exp $
13 *
14 */
15
16#include <metis.h>
17
18
19/*************************************************************************
20* This function finds a matching using the HEM heuristic
21**************************************************************************/
22void Match_RM(CtrlType *ctrl, GraphType *graph)
23{
24  int i, ii, j, nvtxs, cnvtxs, maxidx;
25  idxtype *xadj, *vwgt, *adjncy, *adjwgt;
26  idxtype *match, *cmap, *perm;
27
28  IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->MatchTmr));
29
30  nvtxs = graph->nvtxs;
31  xadj = graph->xadj;
32  vwgt = graph->vwgt;
33  adjncy = graph->adjncy;
34  adjwgt = graph->adjwgt;
35
36  cmap = graph->cmap;
37  match = idxset(nvtxs, UNMATCHED, idxwspacemalloc(ctrl, nvtxs));
38
39  perm = idxwspacemalloc(ctrl, nvtxs);
40  RandomPermute(nvtxs, perm, 1);
41
42  cnvtxs = 0;
43  for (ii=0; ii<nvtxs; ii++) {
44    i = perm[ii];
45
46    if (match[i] == UNMATCHED) {  /* Unmatched */
47      maxidx = i;
48
49      /* Find a random matching, subject to maxvwgt constraints */
50      for (j=xadj[i]; j<xadj[i+1]; j++) {
51        if (match[adjncy[j]] == UNMATCHED && vwgt[i]+vwgt[adjncy[j]] <= ctrl->maxvwgt) {
52          maxidx = adjncy[j];
53          break;
54        }
55      }
56
57      cmap[i] = cmap[maxidx] = cnvtxs++;
58      match[i] = maxidx;
59      match[maxidx] = i;
60    }
61  }
62
63  IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->MatchTmr));
64
65  CreateCoarseGraph(ctrl, graph, cnvtxs, match, perm);
66
67  idxwspacefree(ctrl, nvtxs);
68  idxwspacefree(ctrl, nvtxs);
69}
70
71
72/*************************************************************************
73* This function finds a matching using the HEM heuristic
74**************************************************************************/
75void Match_RM_NVW(CtrlType *ctrl, GraphType *graph)
76{
77  int i, ii, j, nvtxs, cnvtxs, maxidx;
78  idxtype *xadj, *adjncy;
79  idxtype *match, *cmap, *perm;
80
81  IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->MatchTmr));
82
83  nvtxs = graph->nvtxs;
84  xadj = graph->xadj;
85  adjncy = graph->adjncy;
86
87  cmap = graph->cmap;
88  match = idxset(nvtxs, UNMATCHED, idxwspacemalloc(ctrl, nvtxs));
89
90  perm = idxwspacemalloc(ctrl, nvtxs);
91  RandomPermute(nvtxs, perm, 1);
92
93  cnvtxs = 0;
94  for (ii=0; ii<nvtxs; ii++) {
95    i = perm[ii];
96
97    if (match[i] == UNMATCHED) {  /* Unmatched */
98      maxidx = i;
99
100      /* Find a random matching, subject to maxvwgt constraints */
101      for (j=xadj[i]; j<xadj[i+1]; j++) {
102        if (match[adjncy[j]] == UNMATCHED) {
103          maxidx = adjncy[j];
104          break;
105        }
106      }
107
108      cmap[i] = cmap[maxidx] = cnvtxs++;
109      match[i] = maxidx;
110      match[maxidx] = i;
111    }
112  }
113
114  IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->MatchTmr));
115
116  CreateCoarseGraph_NVW(ctrl, graph, cnvtxs, match, perm);
117
118  idxwspacefree(ctrl, nvtxs);
119  idxwspacefree(ctrl, nvtxs);
120}
121
122
123
124/*************************************************************************
125* This function finds a matching using the HEM heuristic
126**************************************************************************/
127void Match_HEM(CtrlType *ctrl, GraphType *graph)
128{
129  int i, ii, j, k, nvtxs, cnvtxs, maxidx, maxwgt;
130  idxtype *xadj, *vwgt, *adjncy, *adjwgt;
131  idxtype *match, *cmap, *perm;
132
133  IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->MatchTmr));
134
135  nvtxs = graph->nvtxs;
136  xadj = graph->xadj;
137  vwgt = graph->vwgt;
138  adjncy = graph->adjncy;
139  adjwgt = graph->adjwgt;
140
141  cmap = graph->cmap;
142  match = idxset(nvtxs, UNMATCHED, idxwspacemalloc(ctrl, nvtxs));
143
144  perm = idxwspacemalloc(ctrl, nvtxs);
145  RandomPermute(nvtxs, perm, 1);
146
147  cnvtxs = 0;
148  for (ii=0; ii<nvtxs; ii++) {
149    i = perm[ii];
150
151    if (match[i] == UNMATCHED) {  /* Unmatched */
152      maxidx = i;
153      maxwgt = 0;
154
155      /* Find a heavy-edge matching, subject to maxvwgt constraints */
156      for (j=xadj[i]; j<xadj[i+1]; j++) {
157        k = adjncy[j];
158        if (match[k] == UNMATCHED && maxwgt < adjwgt[j] && vwgt[i]+vwgt[k] <= ctrl->maxvwgt) {
159          maxwgt = adjwgt[j];
160          maxidx = adjncy[j];
161        }
162      }
163
164      cmap[i] = cmap[maxidx] = cnvtxs++;
165      match[i] = maxidx;
166      match[maxidx] = i;
167    }
168  }
169
170  IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->MatchTmr));
171
172  CreateCoarseGraph(ctrl, graph, cnvtxs, match, perm);
173
174  idxwspacefree(ctrl, nvtxs);
175  idxwspacefree(ctrl, nvtxs);
176}
177
178
179
180/*************************************************************************
181* This function finds a matching using the HEM heuristic
182**************************************************************************/
183void Match_SHEM(CtrlType *ctrl, GraphType *graph)
184{
185  int i, ii, j, k, nvtxs, cnvtxs, maxidx, maxwgt, avgdegree;
186  idxtype *xadj, *vwgt, *adjncy, *adjwgt;
187  idxtype *match, *cmap, *degrees, *perm, *tperm;
188
189  IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->MatchTmr));
190
191  nvtxs = graph->nvtxs;
192  xadj = graph->xadj;
193  vwgt = graph->vwgt;
194  adjncy = graph->adjncy;
195  adjwgt = graph->adjwgt;
196
197  cmap = graph->cmap;
198  match = idxset(nvtxs, UNMATCHED, idxwspacemalloc(ctrl, nvtxs));
199
200  perm = idxwspacemalloc(ctrl, nvtxs);
201  tperm = idxwspacemalloc(ctrl, nvtxs);
202  degrees = idxwspacemalloc(ctrl, nvtxs);
203
204  RandomPermute(nvtxs, tperm, 1);
205  avgdegree = 0.7*(xadj[nvtxs]/nvtxs);
206  for (i=0; i<nvtxs; i++) 
207    degrees[i] = (xadj[i+1]-xadj[i] > avgdegree ? avgdegree : xadj[i+1]-xadj[i]);
208  BucketSortKeysInc(nvtxs, avgdegree, degrees, tperm, perm);
209
210  cnvtxs = 0;
211
212  /* Take care any islands. Islands are matched with non-islands due to coarsening */
213  for (ii=0; ii<nvtxs; ii++) {
214    i = perm[ii];
215
216    if (match[i] == UNMATCHED) {  /* Unmatched */
217      if (xadj[i] < xadj[i+1])
218        break;
219
220      maxidx = i;
221      for (j=nvtxs-1; j>ii; j--) {
222        k = perm[j];
223        if (match[k] == UNMATCHED && xadj[k] < xadj[k+1]) {
224          maxidx = k;
225          break;
226        }
227      }
228
229      cmap[i] = cmap[maxidx] = cnvtxs++;
230      match[i] = maxidx;
231      match[maxidx] = i;
232    }
233  }
234
235  /* Continue with normal matching */
236  for (; ii<nvtxs; ii++) {
237    i = perm[ii];
238
239    if (match[i] == UNMATCHED) {  /* Unmatched */
240      maxidx = i;
241      maxwgt = 0;
242
243      /* Find a heavy-edge matching, subject to maxvwgt constraints */
244      for (j=xadj[i]; j<xadj[i+1]; j++) {
245        if (match[adjncy[j]] == UNMATCHED && maxwgt < adjwgt[j] && vwgt[i]+vwgt[adjncy[j]] <= ctrl->maxvwgt) {
246          maxwgt = adjwgt[j];
247          maxidx = adjncy[j];
248        }
249      }
250
251      cmap[i] = cmap[maxidx] = cnvtxs++;
252      match[i] = maxidx;
253      match[maxidx] = i;
254    }
255  }
256
257  IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->MatchTmr));
258
259  idxwspacefree(ctrl, nvtxs);  /* degrees */
260  idxwspacefree(ctrl, nvtxs);  /* tperm */
261
262  CreateCoarseGraph(ctrl, graph, cnvtxs, match, perm);
263
264  idxwspacefree(ctrl, nvtxs);
265  idxwspacefree(ctrl, nvtxs);
266}
267
Note: See TracBrowser for help on using the repository browser.