SCM

SCM Repository

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

Annotation of /pkg/src/Metis/mkwayrefine.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 :     * mkwayrefine.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: mkwayrefine.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 MocRefineKWayHorizontal(CtrlType *ctrl, GraphType *orggraph, GraphType *graph, int nparts,
21 :     float *ubvec)
22 :     {
23 :    
24 :     IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->UncoarsenTmr));
25 :    
26 :     /* Compute the parameters of the coarsest graph */
27 :     MocComputeKWayPartitionParams(ctrl, graph, nparts);
28 :    
29 :     for (;;) {
30 :     IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->RefTmr));
31 :    
32 :     if (!MocIsHBalanced(graph->ncon, nparts, graph->npwgts, ubvec)) {
33 :     MocComputeKWayBalanceBoundary(ctrl, graph, nparts);
34 :     MCGreedy_KWayEdgeBalanceHorizontal(ctrl, graph, nparts, ubvec, 4);
35 :     ComputeKWayBoundary(ctrl, graph, nparts);
36 :     }
37 :    
38 :     MCRandom_KWayEdgeRefineHorizontal(ctrl, graph, nparts, ubvec, 10);
39 :    
40 :     IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->RefTmr));
41 :    
42 :     if (graph == orggraph)
43 :     break;
44 :    
45 :     graph = graph->finer;
46 :     IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->ProjectTmr));
47 :     MocProjectKWayPartition(ctrl, graph, nparts);
48 :     IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->ProjectTmr));
49 :     }
50 :    
51 :     if (!MocIsHBalanced(graph->ncon, nparts, graph->npwgts, ubvec)) {
52 :     MocComputeKWayBalanceBoundary(ctrl, graph, nparts);
53 :     MCGreedy_KWayEdgeBalanceHorizontal(ctrl, graph, nparts, ubvec, 4);
54 :     ComputeKWayBoundary(ctrl, graph, nparts);
55 :     MCRandom_KWayEdgeRefineHorizontal(ctrl, graph, nparts, ubvec, 10);
56 :     }
57 :    
58 :     IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->UncoarsenTmr));
59 :     }
60 :    
61 :    
62 :    
63 :    
64 :     /*************************************************************************
65 :     * This function allocates memory for k-way edge refinement
66 :     **************************************************************************/
67 :     void MocAllocateKWayPartitionMemory(CtrlType *ctrl, GraphType *graph, int nparts)
68 :     {
69 :     int nvtxs, ncon, pad64;
70 :    
71 :     nvtxs = graph->nvtxs;
72 :     ncon = graph->ncon;
73 :    
74 :     pad64 = (3*nvtxs)%2;
75 :    
76 :     graph->rdata = idxmalloc(3*nvtxs+(sizeof(RInfoType)/sizeof(idxtype))*nvtxs+pad64, "AllocateKWayPartitionMemory: rdata");
77 :     graph->where = graph->rdata;
78 :     graph->bndptr = graph->rdata + nvtxs;
79 :     graph->bndind = graph->rdata + 2*nvtxs;
80 :     graph->rinfo = (RInfoType *)(graph->rdata + 3*nvtxs + pad64);
81 :    
82 :     graph->npwgts = fmalloc(ncon*nparts, "MocAllocateKWayPartitionMemory: npwgts");
83 :     }
84 :    
85 :    
86 :     /*************************************************************************
87 :     * This function computes the initial id/ed
88 :     **************************************************************************/
89 :     void MocComputeKWayPartitionParams(CtrlType *ctrl, GraphType *graph, int nparts)
90 :     {
91 :     int i, j, k, l, nvtxs, ncon, nbnd, mincut, me, other;
92 :     idxtype *xadj, *adjncy, *adjwgt, *where, *bndind, *bndptr;
93 :     RInfoType *rinfo, *myrinfo;
94 :     EDegreeType *myedegrees;
95 :     float *nvwgt, *npwgts;
96 :    
97 :     nvtxs = graph->nvtxs;
98 :     ncon = graph->ncon;
99 :     xadj = graph->xadj;
100 :     nvwgt = graph->nvwgt;
101 :     adjncy = graph->adjncy;
102 :     adjwgt = graph->adjwgt;
103 :    
104 :     where = graph->where;
105 :     npwgts = sset(ncon*nparts, 0.0, graph->npwgts);
106 :     bndind = graph->bndind;
107 :     bndptr = idxset(nvtxs, -1, graph->bndptr);
108 :     rinfo = graph->rinfo;
109 :    
110 :    
111 :     /*------------------------------------------------------------
112 :     / Compute now the id/ed degrees
113 :     /------------------------------------------------------------*/
114 :     ctrl->wspace.cdegree = 0;
115 :     nbnd = mincut = 0;
116 :     for (i=0; i<nvtxs; i++) {
117 :     me = where[i];
118 :     saxpy(ncon, 1.0, nvwgt+i*ncon, 1, npwgts+me*ncon, 1);
119 :    
120 :     myrinfo = rinfo+i;
121 :     myrinfo->id = myrinfo->ed = myrinfo->ndegrees = 0;
122 :     myrinfo->edegrees = NULL;
123 :    
124 :     for (j=xadj[i]; j<xadj[i+1]; j++) {
125 :     if (me != where[adjncy[j]])
126 :     myrinfo->ed += adjwgt[j];
127 :     }
128 :     myrinfo->id = graph->adjwgtsum[i] - myrinfo->ed;
129 :    
130 :     if (myrinfo->ed > 0)
131 :     mincut += myrinfo->ed;
132 :    
133 :     if (myrinfo->ed-myrinfo->id >= 0)
134 :     BNDInsert(nbnd, bndind, bndptr, i);
135 :    
136 :     /* Time to compute the particular external degrees */
137 :     if (myrinfo->ed > 0) {
138 :     myedegrees = myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;
139 :     ctrl->wspace.cdegree += xadj[i+1]-xadj[i];
140 :    
141 :     for (j=xadj[i]; j<xadj[i+1]; j++) {
142 :     other = where[adjncy[j]];
143 :     if (me != other) {
144 :     for (k=0; k<myrinfo->ndegrees; k++) {
145 :     if (myedegrees[k].pid == other) {
146 :     myedegrees[k].ed += adjwgt[j];
147 :     break;
148 :     }
149 :     }
150 :     if (k == myrinfo->ndegrees) {
151 :     myedegrees[myrinfo->ndegrees].pid = other;
152 :     myedegrees[myrinfo->ndegrees++].ed = adjwgt[j];
153 :     }
154 :     }
155 :     }
156 :    
157 :     ASSERT(myrinfo->ndegrees <= xadj[i+1]-xadj[i]);
158 :     }
159 :     }
160 :    
161 :     graph->mincut = mincut/2;
162 :     graph->nbnd = nbnd;
163 :    
164 :     }
165 :    
166 :    
167 :    
168 :     /*************************************************************************
169 :     * This function projects a partition, and at the same time computes the
170 :     * parameters for refinement.
171 :     **************************************************************************/
172 :     void MocProjectKWayPartition(CtrlType *ctrl, GraphType *graph, int nparts)
173 :     {
174 :     int i, j, k, nvtxs, nbnd, me, other, istart, iend, ndegrees;
175 :     idxtype *xadj, *adjncy, *adjwgt, *adjwgtsum;
176 :     idxtype *cmap, *where, *bndptr, *bndind;
177 :     idxtype *cwhere;
178 :     GraphType *cgraph;
179 :     RInfoType *crinfo, *rinfo, *myrinfo;
180 :     EDegreeType *myedegrees;
181 :     idxtype *htable;
182 :    
183 :     cgraph = graph->coarser;
184 :     cwhere = cgraph->where;
185 :     crinfo = cgraph->rinfo;
186 :    
187 :     nvtxs = graph->nvtxs;
188 :     cmap = graph->cmap;
189 :     xadj = graph->xadj;
190 :     adjncy = graph->adjncy;
191 :     adjwgt = graph->adjwgt;
192 :     adjwgtsum = graph->adjwgtsum;
193 :    
194 :     MocAllocateKWayPartitionMemory(ctrl, graph, nparts);
195 :     where = graph->where;
196 :     rinfo = graph->rinfo;
197 :     bndind = graph->bndind;
198 :     bndptr = idxset(nvtxs, -1, graph->bndptr);
199 :    
200 :     /* Go through and project partition and compute id/ed for the nodes */
201 :     for (i=0; i<nvtxs; i++) {
202 :     k = cmap[i];
203 :     where[i] = cwhere[k];
204 :     cmap[i] = crinfo[k].ed; /* For optimization */
205 :     }
206 :    
207 :     htable = idxset(nparts, -1, idxwspacemalloc(ctrl, nparts));
208 :    
209 :     ctrl->wspace.cdegree = 0;
210 :     for (nbnd=0, i=0; i<nvtxs; i++) {
211 :     me = where[i];
212 :    
213 :     myrinfo = rinfo+i;
214 :     myrinfo->id = myrinfo->ed = myrinfo->ndegrees = 0;
215 :     myrinfo->edegrees = NULL;
216 :    
217 :     myrinfo->id = adjwgtsum[i];
218 :    
219 :     if (cmap[i] > 0) { /* If it is an interface node. Note cmap[i] = crinfo[cmap[i]].ed */
220 :     istart = xadj[i];
221 :     iend = xadj[i+1];
222 :    
223 :     myedegrees = myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;
224 :     ctrl->wspace.cdegree += iend-istart;
225 :    
226 :     ndegrees = 0;
227 :     for (j=istart; j<iend; j++) {
228 :     other = where[adjncy[j]];
229 :     if (me != other) {
230 :     myrinfo->ed += adjwgt[j];
231 :     if ((k = htable[other]) == -1) {
232 :     htable[other] = ndegrees;
233 :     myedegrees[ndegrees].pid = other;
234 :     myedegrees[ndegrees++].ed = adjwgt[j];
235 :     }
236 :     else {
237 :     myedegrees[k].ed += adjwgt[j];
238 :     }
239 :     }
240 :     }
241 :     myrinfo->id -= myrinfo->ed;
242 :    
243 :     /* Remove space for edegrees if it was interior */
244 :     if (myrinfo->ed == 0) {
245 :     myrinfo->edegrees = NULL;
246 :     ctrl->wspace.cdegree -= iend-istart;
247 :     }
248 :     else {
249 :     if (myrinfo->ed-myrinfo->id >= 0)
250 :     BNDInsert(nbnd, bndind, bndptr, i);
251 :    
252 :     myrinfo->ndegrees = ndegrees;
253 :    
254 :     for (j=0; j<ndegrees; j++)
255 :     htable[myedegrees[j].pid] = -1;
256 :     }
257 :     }
258 :     }
259 :    
260 :     scopy(graph->ncon*nparts, cgraph->npwgts, graph->npwgts);
261 :     graph->mincut = cgraph->mincut;
262 :     graph->nbnd = nbnd;
263 :    
264 :     FreeGraph(graph->coarser);
265 :     graph->coarser = NULL;
266 :    
267 :     idxwspacefree(ctrl, nparts);
268 :    
269 :     ASSERT(CheckBnd2(graph));
270 :    
271 :     }
272 :    
273 :    
274 :    
275 :     /*************************************************************************
276 :     * This function computes the boundary definition for balancing
277 :     **************************************************************************/
278 :     void MocComputeKWayBalanceBoundary(CtrlType *ctrl, GraphType *graph, int nparts)
279 :     {
280 :     int i, nvtxs, nbnd;
281 :     idxtype *bndind, *bndptr;
282 :    
283 :     nvtxs = graph->nvtxs;
284 :     bndind = graph->bndind;
285 :     bndptr = idxset(nvtxs, -1, graph->bndptr);
286 :    
287 :    
288 :     /* Compute the new boundary */
289 :     nbnd = 0;
290 :     for (i=0; i<nvtxs; i++) {
291 :     if (graph->rinfo[i].ed > 0)
292 :     BNDInsert(nbnd, bndind, bndptr, i);
293 :     }
294 :    
295 :     graph->nbnd = nbnd;
296 :     }
297 :    

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