Hitmap 1.3
 All Data Structures Namespaces Files Functions Variables Typedefs Friends Macros Groups Pages
match.c
Go to the documentation of this file.
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 **************************************************************************/
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 **************************************************************************/
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 **************************************************************************/
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 **************************************************************************/
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 
#define idxwspacefree
Definition: rename.h:165
#define Match_RM
Definition: rename.h:139
#define CreateCoarseGraph_NVW
Definition: rename.h:28
#define BucketSortKeysInc
Definition: rename.h:22
idxtype * cmap
Definition: struct.h:172
#define idxwspacemalloc
Definition: rename.h:164
#define stoptimer(tmr)
Definition: macros.h:54
#define Match_HEM
Definition: rename.h:141
HitTile_Vector graph
int idxtype
Definition: struct.h:19
#define IFSET(a, flag, cmd)
Definition: macros.h:61
int dbglvl
Definition: struct.h:216
#define idxset
Definition: rename.h:390
idxtype * adjwgt
Definition: struct.h:166
timer MatchTmr
Definition: struct.h:230
#define Match_SHEM
Definition: rename.h:142
idxtype * vwgt
Definition: struct.h:163
#define DBG_TIME
Definition: defs.h:154
int maxvwgt
Definition: struct.h:220
int nvtxs
Definition: struct.h:161
#define RandomPermute
Definition: rename.h:410
#define Match_RM_NVW
Definition: rename.h:140
#define CreateCoarseGraph
Definition: rename.h:26
idxtype * adjncy
Definition: struct.h:165
idxtype * xadj
Definition: struct.h:162
#define starttimer(tmr)
Definition: macros.h:53
#define UNMATCHED
Definition: defs.h:131