SCM

SCM Repository

[matrix] Annotation of /pkg/src/Metis/kwayrefine.c
ViewVC logotype

Annotation of /pkg/src/Metis/kwayrefine.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 10 - (view) (download) (as text)

1 : bates 10 /*
2 :     * Copyright 1997, Regents of the University of Minnesota
3 :     *
4 :     * kwayrefine.c
5 :     *
6 :     * This file contains the driving routines for multilevel k-way refinement
7 :     *
8 :     * Started 7/28/97
9 :     * George
10 :     *
11 :     * $Id: kwayrefine.c,v 1.1 2003/12/31 21:32:30 bates Exp $
12 :     */
13 :    
14 :     #include <metis.h>
15 :    
16 :    
17 :     /*************************************************************************
18 :     * This function is the entry point of refinement
19 :     **************************************************************************/
20 :     void RefineKWay(CtrlType *ctrl, GraphType *orggraph, GraphType *graph, int nparts, float *tpwgts, float ubfactor)
21 :     {
22 :     int i, nlevels, mustfree=0;
23 :     GraphType *ptr;
24 :    
25 :     IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->UncoarsenTmr));
26 :    
27 :     /* Compute the parameters of the coarsest graph */
28 :     ComputeKWayPartitionParams(ctrl, graph, nparts);
29 :    
30 :     /* Take care any non-contiguity */
31 :     IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->AuxTmr1));
32 :     if (ctrl->RType == RTYPE_KWAYRANDOM_MCONN) {
33 :     EliminateComponents(ctrl, graph, nparts, tpwgts, 1.25);
34 :     EliminateSubDomainEdges(ctrl, graph, nparts, tpwgts);
35 :     EliminateComponents(ctrl, graph, nparts, tpwgts, 1.25);
36 :     }
37 :     IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->AuxTmr1));
38 :    
39 :     /* Determine how many levels are there */
40 :     for (ptr=graph, nlevels=0; ptr!=orggraph; ptr=ptr->finer, nlevels++);
41 :    
42 :     for (i=0; ;i++) {
43 :     /* PrintSubDomainGraph(graph, nparts, graph->where); */
44 :     if (ctrl->RType == RTYPE_KWAYRANDOM_MCONN && (i == nlevels/2 || i == nlevels/2+1))
45 :     EliminateSubDomainEdges(ctrl, graph, nparts, tpwgts);
46 :    
47 :     IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->RefTmr));
48 :    
49 :     if (2*i >= nlevels && !IsBalanced(graph->pwgts, nparts, tpwgts, 1.04*ubfactor)) {
50 :     ComputeKWayBalanceBoundary(ctrl, graph, nparts);
51 :     if (ctrl->RType == RTYPE_KWAYRANDOM_MCONN)
52 :     Greedy_KWayEdgeBalanceMConn(ctrl, graph, nparts, tpwgts, ubfactor, 1);
53 :     else
54 :     Greedy_KWayEdgeBalance(ctrl, graph, nparts, tpwgts, ubfactor, 1);
55 :     ComputeKWayBoundary(ctrl, graph, nparts);
56 :     }
57 :    
58 :     switch (ctrl->RType) {
59 :     case RTYPE_KWAYRANDOM:
60 :     Random_KWayEdgeRefine(ctrl, graph, nparts, tpwgts, ubfactor, 10, 1);
61 :     break;
62 :     case RTYPE_KWAYGREEDY:
63 :     Greedy_KWayEdgeRefine(ctrl, graph, nparts, tpwgts, ubfactor, 10);
64 :     break;
65 :     case RTYPE_KWAYRANDOM_MCONN:
66 :     Random_KWayEdgeRefineMConn(ctrl, graph, nparts, tpwgts, ubfactor, 10, 1);
67 :     break;
68 :     }
69 :     IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->RefTmr));
70 :    
71 :     if (graph == orggraph)
72 :     break;
73 :    
74 :     GKfree(&graph->gdata, LTERM); /* Deallocate the graph related arrays */
75 :    
76 :     graph = graph->finer;
77 :    
78 :     IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->ProjectTmr));
79 :     if (graph->vwgt == NULL) {
80 :     graph->vwgt = idxsmalloc(graph->nvtxs, 1, "RefineKWay: graph->vwgt");
81 :     graph->adjwgt = idxsmalloc(graph->nedges, 1, "RefineKWay: graph->adjwgt");
82 :     mustfree = 1;
83 :     }
84 :     ProjectKWayPartition(ctrl, graph, nparts);
85 :     IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->ProjectTmr));
86 :     }
87 :    
88 :     if (!IsBalanced(graph->pwgts, nparts, tpwgts, ubfactor)) {
89 :     ComputeKWayBalanceBoundary(ctrl, graph, nparts);
90 :     if (ctrl->RType == RTYPE_KWAYRANDOM_MCONN) {
91 :     Greedy_KWayEdgeBalanceMConn(ctrl, graph, nparts, tpwgts, ubfactor, 8);
92 :     Random_KWayEdgeRefineMConn(ctrl, graph, nparts, tpwgts, ubfactor, 10, 0);
93 :     }
94 :     else {
95 :     Greedy_KWayEdgeBalance(ctrl, graph, nparts, tpwgts, ubfactor, 8);
96 :     Random_KWayEdgeRefine(ctrl, graph, nparts, tpwgts, ubfactor, 10, 0);
97 :     }
98 :     }
99 :    
100 :     /* Take care any trivial non-contiguity */
101 :     IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->AuxTmr2));
102 :     EliminateComponents(ctrl, graph, nparts, tpwgts, ubfactor);
103 :     IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->AuxTmr2));
104 :    
105 :     if (mustfree)
106 :     GKfree(&graph->vwgt, &graph->adjwgt, LTERM);
107 :    
108 :     IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->UncoarsenTmr));
109 :     }
110 :    
111 :    
112 :     /*************************************************************************
113 :     * This function allocates memory for k-way edge refinement
114 :     **************************************************************************/
115 :     void AllocateKWayPartitionMemory(CtrlType *ctrl, GraphType *graph, int nparts)
116 :     {
117 :     int nvtxs, pad64;
118 :    
119 :     nvtxs = graph->nvtxs;
120 :    
121 :     pad64 = (3*nvtxs+nparts)%2;
122 :    
123 :     graph->rdata = idxmalloc(3*nvtxs+nparts+(sizeof(RInfoType)/sizeof(idxtype))*nvtxs+pad64, "AllocateKWayPartitionMemory: rdata");
124 :     graph->pwgts = graph->rdata;
125 :     graph->where = graph->rdata + nparts;
126 :     graph->bndptr = graph->rdata + nvtxs + nparts;
127 :     graph->bndind = graph->rdata + 2*nvtxs + nparts;
128 :     graph->rinfo = (RInfoType *)(graph->rdata + 3*nvtxs+nparts + pad64);
129 :    
130 :     /*
131 :     if (ctrl->wspace.edegrees != NULL)
132 :     free(ctrl->wspace.edegrees);
133 :     ctrl->wspace.edegrees = (EDegreeType *)GKmalloc(graph->nedges*sizeof(EDegreeType), "AllocateKWayPartitionMemory: edegrees");
134 :     */
135 :     }
136 :    
137 :    
138 :     /*************************************************************************
139 :     * This function computes the initial id/ed
140 :     **************************************************************************/
141 :     void ComputeKWayPartitionParams(CtrlType *ctrl, GraphType *graph, int nparts)
142 :     {
143 :     int i, j, k, l, nvtxs, nbnd, mincut, me, other;
144 :     idxtype *xadj, *vwgt, *adjncy, *adjwgt, *pwgts, *where, *bndind, *bndptr;
145 :     RInfoType *rinfo, *myrinfo;
146 :     EDegreeType *myedegrees;
147 :    
148 :     nvtxs = graph->nvtxs;
149 :     xadj = graph->xadj;
150 :     vwgt = graph->vwgt;
151 :     adjncy = graph->adjncy;
152 :     adjwgt = graph->adjwgt;
153 :    
154 :     where = graph->where;
155 :     pwgts = idxset(nparts, 0, graph->pwgts);
156 :     bndind = graph->bndind;
157 :     bndptr = idxset(nvtxs, -1, graph->bndptr);
158 :     rinfo = graph->rinfo;
159 :    
160 :    
161 :     /*------------------------------------------------------------
162 :     / Compute now the id/ed degrees
163 :     /------------------------------------------------------------*/
164 :     ctrl->wspace.cdegree = 0;
165 :     nbnd = mincut = 0;
166 :     for (i=0; i<nvtxs; i++) {
167 :     me = where[i];
168 :     pwgts[me] += vwgt[i];
169 :    
170 :     myrinfo = rinfo+i;
171 :     myrinfo->id = myrinfo->ed = myrinfo->ndegrees = 0;
172 :     myrinfo->edegrees = NULL;
173 :    
174 :     for (j=xadj[i]; j<xadj[i+1]; j++) {
175 :     if (me != where[adjncy[j]])
176 :     myrinfo->ed += adjwgt[j];
177 :     }
178 :     myrinfo->id = graph->adjwgtsum[i] - myrinfo->ed;
179 :    
180 :     if (myrinfo->ed > 0)
181 :     mincut += myrinfo->ed;
182 :    
183 :     if (myrinfo->ed-myrinfo->id >= 0)
184 :     BNDInsert(nbnd, bndind, bndptr, i);
185 :    
186 :     /* Time to compute the particular external degrees */
187 :     if (myrinfo->ed > 0) {
188 :     myedegrees = myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;
189 :     ctrl->wspace.cdegree += xadj[i+1]-xadj[i];
190 :    
191 :     for (j=xadj[i]; j<xadj[i+1]; j++) {
192 :     other = where[adjncy[j]];
193 :     if (me != other) {
194 :     for (k=0; k<myrinfo->ndegrees; k++) {
195 :     if (myedegrees[k].pid == other) {
196 :     myedegrees[k].ed += adjwgt[j];
197 :     break;
198 :     }
199 :     }
200 :     if (k == myrinfo->ndegrees) {
201 :     myedegrees[myrinfo->ndegrees].pid = other;
202 :     myedegrees[myrinfo->ndegrees++].ed = adjwgt[j];
203 :     }
204 :     }
205 :     }
206 :    
207 :     ASSERT(myrinfo->ndegrees <= xadj[i+1]-xadj[i]);
208 :     }
209 :     }
210 :    
211 :     graph->mincut = mincut/2;
212 :     graph->nbnd = nbnd;
213 :    
214 :     }
215 :    
216 :    
217 :    
218 :     /*************************************************************************
219 :     * This function projects a partition, and at the same time computes the
220 :     * parameters for refinement.
221 :     **************************************************************************/
222 :     void ProjectKWayPartition(CtrlType *ctrl, GraphType *graph, int nparts)
223 :     {
224 :     int i, j, k, nvtxs, nbnd, me, other, istart, iend, ndegrees;
225 :     idxtype *xadj, *adjncy, *adjwgt, *adjwgtsum;
226 :     idxtype *cmap, *where, *bndptr, *bndind;
227 :     idxtype *cwhere;
228 :     GraphType *cgraph;
229 :     RInfoType *crinfo, *rinfo, *myrinfo;
230 :     EDegreeType *myedegrees;
231 :     idxtype *htable;
232 :    
233 :     cgraph = graph->coarser;
234 :     cwhere = cgraph->where;
235 :     crinfo = cgraph->rinfo;
236 :    
237 :     nvtxs = graph->nvtxs;
238 :     cmap = graph->cmap;
239 :     xadj = graph->xadj;
240 :     adjncy = graph->adjncy;
241 :     adjwgt = graph->adjwgt;
242 :     adjwgtsum = graph->adjwgtsum;
243 :    
244 :     AllocateKWayPartitionMemory(ctrl, graph, nparts);
245 :     where = graph->where;
246 :     rinfo = graph->rinfo;
247 :     bndind = graph->bndind;
248 :     bndptr = idxset(nvtxs, -1, graph->bndptr);
249 :    
250 :     /* Go through and project partition and compute id/ed for the nodes */
251 :     for (i=0; i<nvtxs; i++) {
252 :     k = cmap[i];
253 :     where[i] = cwhere[k];
254 :     cmap[i] = crinfo[k].ed; /* For optimization */
255 :     }
256 :    
257 :     htable = idxset(nparts, -1, idxwspacemalloc(ctrl, nparts));
258 :    
259 :     ctrl->wspace.cdegree = 0;
260 :     for (nbnd=0, i=0; i<nvtxs; i++) {
261 :     me = where[i];
262 :    
263 :     myrinfo = rinfo+i;
264 :     myrinfo->id = myrinfo->ed = myrinfo->ndegrees = 0;
265 :     myrinfo->edegrees = NULL;
266 :    
267 :     myrinfo->id = adjwgtsum[i];
268 :    
269 :     if (cmap[i] > 0) { /* If it is an interface node. Note cmap[i] = crinfo[cmap[i]].ed */
270 :     istart = xadj[i];
271 :     iend = xadj[i+1];
272 :    
273 :     myedegrees = myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;
274 :     ctrl->wspace.cdegree += iend-istart;
275 :    
276 :     ndegrees = 0;
277 :     for (j=istart; j<iend; j++) {
278 :     other = where[adjncy[j]];
279 :     if (me != other) {
280 :     myrinfo->ed += adjwgt[j];
281 :     if ((k = htable[other]) == -1) {
282 :     htable[other] = ndegrees;
283 :     myedegrees[ndegrees].pid = other;
284 :     myedegrees[ndegrees++].ed = adjwgt[j];
285 :     }
286 :     else {
287 :     myedegrees[k].ed += adjwgt[j];
288 :     }
289 :     }
290 :     }
291 :     myrinfo->id -= myrinfo->ed;
292 :    
293 :     /* Remove space for edegrees if it was interior */
294 :     if (myrinfo->ed == 0) {
295 :     myrinfo->edegrees = NULL;
296 :     ctrl->wspace.cdegree -= iend-istart;
297 :     }
298 :     else {
299 :     if (myrinfo->ed-myrinfo->id >= 0)
300 :     BNDInsert(nbnd, bndind, bndptr, i);
301 :    
302 :     myrinfo->ndegrees = ndegrees;
303 :    
304 :     for (j=0; j<ndegrees; j++)
305 :     htable[myedegrees[j].pid] = -1;
306 :     }
307 :     }
308 :     }
309 :    
310 :     idxcopy(nparts, cgraph->pwgts, graph->pwgts);
311 :     graph->mincut = cgraph->mincut;
312 :     graph->nbnd = nbnd;
313 :    
314 :     FreeGraph(graph->coarser);
315 :     graph->coarser = NULL;
316 :    
317 :     idxwspacefree(ctrl, nparts);
318 :    
319 :     ASSERT(CheckBnd2(graph));
320 :    
321 :     }
322 :    
323 :    
324 :    
325 :     /*************************************************************************
326 :     * This function checks if the partition weights are within the balance
327 :     * contraints
328 :     **************************************************************************/
329 :     int IsBalanced(idxtype *pwgts, int nparts, float *tpwgts, float ubfactor)
330 :     {
331 :     int i, j, tvwgt;
332 :    
333 :     tvwgt = idxsum(nparts, pwgts);
334 :     for (i=0; i<nparts; i++) {
335 :     if (pwgts[i] > tpwgts[i]*tvwgt*(ubfactor+0.005))
336 :     return 0;
337 :     }
338 :    
339 :     return 1;
340 :     }
341 :    
342 :    
343 :     /*************************************************************************
344 :     * This function computes the boundary definition for balancing
345 :     **************************************************************************/
346 :     void ComputeKWayBoundary(CtrlType *ctrl, GraphType *graph, int nparts)
347 :     {
348 :     int i, nvtxs, nbnd;
349 :     idxtype *bndind, *bndptr;
350 :    
351 :     nvtxs = graph->nvtxs;
352 :     bndind = graph->bndind;
353 :     bndptr = idxset(nvtxs, -1, graph->bndptr);
354 :    
355 :    
356 :     /*------------------------------------------------------------
357 :     / Compute the new boundary
358 :     /------------------------------------------------------------*/
359 :     nbnd = 0;
360 :     for (i=0; i<nvtxs; i++) {
361 :     if (graph->rinfo[i].ed-graph->rinfo[i].id >= 0)
362 :     BNDInsert(nbnd, bndind, bndptr, i);
363 :     }
364 :    
365 :     graph->nbnd = nbnd;
366 :     }
367 :    
368 :     /*************************************************************************
369 :     * This function computes the boundary definition for balancing
370 :     **************************************************************************/
371 :     void ComputeKWayBalanceBoundary(CtrlType *ctrl, GraphType *graph, int nparts)
372 :     {
373 :     int i, nvtxs, nbnd;
374 :     idxtype *bndind, *bndptr;
375 :    
376 :     nvtxs = graph->nvtxs;
377 :     bndind = graph->bndind;
378 :     bndptr = idxset(nvtxs, -1, graph->bndptr);
379 :    
380 :    
381 :     /*------------------------------------------------------------
382 :     / Compute the new boundary
383 :     /------------------------------------------------------------*/
384 :     nbnd = 0;
385 :     for (i=0; i<nvtxs; i++) {
386 :     if (graph->rinfo[i].ed > 0)
387 :     BNDInsert(nbnd, bndind, bndptr, i);
388 :     }
389 :    
390 :     graph->nbnd = nbnd;
391 :     }
392 :    

root@r-forge.r-project.org
ViewVC Help
Powered by ViewVC 1.0.0  
Thanks to:
Vienna University of Economics and Business Powered By FusionForge