source: inundation/pymetis/metis-4.0/Lib/kwayvolrefine.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: 13.6 KB
Line 
1/*
2 * Copyright 1997, Regents of the University of Minnesota
3 *
4 * kwayvolrefine.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: kwayvolrefine.c,v 1.2 1998/11/30 16:13:57 karypis Exp $
12 */
13
14#include <metis.h>
15
16
17/*************************************************************************
18* This function is the entry point of refinement
19**************************************************************************/
20void RefineVolKWay(CtrlType *ctrl, GraphType *orggraph, GraphType *graph, int nparts, 
21                   float *tpwgts, float ubfactor)
22{
23  int i, nlevels;
24  GraphType *ptr;
25
26  IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->UncoarsenTmr));
27
28  /* Take care any non-contiguity */
29  if (ctrl->RType == RTYPE_KWAYRANDOM_MCONN) {
30    ComputeVolKWayPartitionParams(ctrl, graph, nparts);
31    EliminateVolComponents(ctrl, graph, nparts, tpwgts, 1.25);
32    EliminateVolSubDomainEdges(ctrl, graph, nparts, tpwgts);
33    EliminateVolComponents(ctrl, graph, nparts, tpwgts, 1.25);
34  }
35
36
37  /* Determine how many levels are there */
38  for (ptr=graph, nlevels=0; ptr!=orggraph; ptr=ptr->finer, nlevels++); 
39
40  /* Compute the parameters of the coarsest graph */
41  ComputeVolKWayPartitionParams(ctrl, graph, nparts);
42
43  for (i=0; ;i++) {
44    /*PrintSubDomainGraph(graph, nparts, graph->where);*/
45    MALLOC_CHECK(NULL);
46    IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->RefTmr));
47
48    if (2*i >= nlevels && !IsBalanced(graph->pwgts, nparts, tpwgts, 1.04*ubfactor)) {
49      ComputeVolKWayBalanceBoundary(ctrl, graph, nparts);
50      switch (ctrl->RType) {
51        case RTYPE_KWAYRANDOM:
52          Greedy_KWayVolBalance(ctrl, graph, nparts, tpwgts, ubfactor, 1); 
53          break;
54        case RTYPE_KWAYRANDOM_MCONN:
55          Greedy_KWayVolBalanceMConn(ctrl, graph, nparts, tpwgts, ubfactor, 1); 
56          break;
57      }
58      ComputeVolKWayBoundary(ctrl, graph, nparts);
59    }
60
61    switch (ctrl->RType) {
62      case RTYPE_KWAYRANDOM:
63        Random_KWayVolRefine(ctrl, graph, nparts, tpwgts, ubfactor, 10, 0); 
64        break;
65      case RTYPE_KWAYRANDOM_MCONN:
66        Random_KWayVolRefineMConn(ctrl, graph, nparts, tpwgts, ubfactor, 10, 0); 
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    ProjectVolKWayPartition(ctrl, graph, nparts);
80    IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->ProjectTmr));
81  }
82
83  if (!IsBalanced(graph->pwgts, nparts, tpwgts, ubfactor)) {
84    ComputeVolKWayBalanceBoundary(ctrl, graph, nparts);
85    switch (ctrl->RType) {
86      case RTYPE_KWAYRANDOM:
87        Greedy_KWayVolBalance(ctrl, graph, nparts, tpwgts, ubfactor, 8); 
88        Random_KWayVolRefine(ctrl, graph, nparts, tpwgts, ubfactor, 10, 0); 
89        break;
90      case RTYPE_KWAYRANDOM_MCONN:
91        Greedy_KWayVolBalanceMConn(ctrl, graph, nparts, tpwgts, ubfactor, 8); 
92        Random_KWayVolRefineMConn(ctrl, graph, nparts, tpwgts, ubfactor, 10, 0); 
93        break;
94    }
95  }
96
97  EliminateVolComponents(ctrl, graph, nparts, tpwgts, ubfactor); 
98
99  IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->UncoarsenTmr));
100}
101
102
103
104/*************************************************************************
105* This function allocates memory for k-way edge refinement
106**************************************************************************/
107void AllocateVolKWayPartitionMemory(CtrlType *ctrl, GraphType *graph, int nparts)
108{
109  int nvtxs, pad64;
110
111  nvtxs = graph->nvtxs;
112
113  pad64 = (3*nvtxs+nparts)%2;
114
115  graph->rdata = idxmalloc(3*nvtxs+nparts+(sizeof(VRInfoType)/sizeof(idxtype))*nvtxs+pad64, "AllocateVolKWayPartitionMemory: rdata");
116  graph->pwgts          = graph->rdata;
117  graph->where          = graph->rdata + nparts;
118  graph->bndptr         = graph->rdata + nvtxs + nparts;
119  graph->bndind         = graph->rdata + 2*nvtxs + nparts;
120  graph->vrinfo          = (VRInfoType *)(graph->rdata + 3*nvtxs+nparts + pad64);
121
122}
123
124
125
126/*************************************************************************
127* This function computes the initial id/ed
128**************************************************************************/
129void ComputeVolKWayPartitionParams(CtrlType *ctrl, GraphType *graph, int nparts)
130{
131  int i, ii, j, k, kk, l, nvtxs, nbnd, mincut, minvol, me, other, pid; 
132  idxtype *xadj, *vwgt, *adjncy, *adjwgt, *pwgts, *where;
133  VRInfoType *rinfo, *myrinfo, *orinfo;
134  VEDegreeType *myedegrees, *oedegrees;
135
136  nvtxs = graph->nvtxs;
137  xadj = graph->xadj;
138  vwgt = graph->vwgt;
139  adjncy = graph->adjncy;
140  adjwgt = graph->adjwgt;
141
142  where = graph->where;
143  pwgts = idxset(nparts, 0, graph->pwgts);
144  rinfo = graph->vrinfo;
145
146
147  /*------------------------------------------------------------
148  / Compute now the id/ed degrees
149  /------------------------------------------------------------*/
150  ctrl->wspace.cdegree = 0;
151  mincut = 0;
152  for (i=0; i<nvtxs; i++) {
153    me = where[i];
154    pwgts[me] += vwgt[i];
155
156    myrinfo = rinfo+i;
157    myrinfo->id = myrinfo->ed = myrinfo->nid = myrinfo->ndegrees = 0;
158    myrinfo->edegrees = NULL;
159
160    for (j=xadj[i]; j<xadj[i+1]; j++) {
161      if (me == where[adjncy[j]]) {
162        myrinfo->id += adjwgt[j];
163        myrinfo->nid++;
164      }
165    }
166    myrinfo->ed = graph->adjwgtsum[i] - myrinfo->id;
167
168    mincut += myrinfo->ed;
169
170    /* Time to compute the particular external degrees */
171    if (myrinfo->ed > 0) { 
172      myedegrees = myrinfo->edegrees = ctrl->wspace.vedegrees+ctrl->wspace.cdegree;
173      ctrl->wspace.cdegree += xadj[i+1]-xadj[i];
174
175      for (j=xadj[i]; j<xadj[i+1]; j++) {
176        other = where[adjncy[j]];
177        if (me != other) {
178          for (k=0; k<myrinfo->ndegrees; k++) {
179            if (myedegrees[k].pid == other) {
180              myedegrees[k].ed += adjwgt[j];
181              myedegrees[k].ned++;
182              break;
183            }
184          }
185          if (k == myrinfo->ndegrees) {
186            myedegrees[myrinfo->ndegrees].gv = 0;
187            myedegrees[myrinfo->ndegrees].pid = other;
188            myedegrees[myrinfo->ndegrees].ed = adjwgt[j];
189            myedegrees[myrinfo->ndegrees++].ned = 1;
190          }
191        }
192      }
193
194      ASSERT(myrinfo->ndegrees <= xadj[i+1]-xadj[i]);
195    }
196  }
197  graph->mincut = mincut/2;
198
199
200  ComputeKWayVolGains(ctrl, graph, nparts);
201
202}
203
204
205
206/*************************************************************************
207* This function computes the initial id/ed
208**************************************************************************/
209void ComputeKWayVolGains(CtrlType *ctrl, GraphType *graph, int nparts)
210{
211  int i, ii, j, k, kk, l, nvtxs, me, other, pid, myndegrees; 
212  idxtype *xadj, *vsize, *adjncy, *adjwgt, *where, *bndind, *bndptr, *ophtable;
213  VRInfoType *rinfo, *myrinfo, *orinfo;
214  VEDegreeType *myedegrees, *oedegrees;
215
216  nvtxs = graph->nvtxs;
217  xadj = graph->xadj;
218  vsize = graph->vsize;
219  adjncy = graph->adjncy;
220  adjwgt = graph->adjwgt;
221
222  where = graph->where;
223  bndind = graph->bndind;
224  bndptr = idxset(nvtxs, -1, graph->bndptr);
225  rinfo = graph->vrinfo;
226
227  ophtable = idxset(nparts, -1, idxwspacemalloc(ctrl, nparts));
228
229  /*------------------------------------------------------------
230  / Compute now the iv/ev degrees
231  /------------------------------------------------------------*/
232  graph->minvol = graph->nbnd = 0;
233  for (i=0; i<nvtxs; i++) {
234    myrinfo = rinfo+i;
235    myrinfo->gv = -MAXIDX;
236
237    if (myrinfo->ndegrees > 0) {
238      me = where[i];
239      myedegrees = myrinfo->edegrees;
240      myndegrees = myrinfo->ndegrees;
241
242      graph->minvol += myndegrees*vsize[i];
243
244      for (j=xadj[i]; j<xadj[i+1]; j++) {
245        ii = adjncy[j];
246        other = where[ii];
247        orinfo = rinfo+ii;
248        oedegrees = orinfo->edegrees;
249
250        for (k=0; k<orinfo->ndegrees; k++) 
251          ophtable[oedegrees[k].pid] = k;
252        ophtable[other] = 1;  /* this is to simplify coding */
253
254        if (me == other) {
255          /* Find which domains 'i' is connected and 'ii' is not and update their gain */
256          for (k=0; k<myndegrees; k++) {
257            if (ophtable[myedegrees[k].pid] == -1)
258              myedegrees[k].gv -= vsize[ii];
259          }
260        }
261        else {
262          ASSERT(ophtable[me] != -1);
263
264          if (oedegrees[ophtable[me]].ned == 1) { /* I'm the only connection of 'ii' in 'me' */
265            /* Increase the gains for all the common domains between 'i' and 'ii' */
266            for (k=0; k<myndegrees; k++) {
267              if (ophtable[myedegrees[k].pid] != -1) 
268                myedegrees[k].gv += vsize[ii];
269            }
270          }
271          else {
272            /* Find which domains 'i' is connected and 'ii' is not and update their gain */
273            for (k=0; k<myndegrees; k++) {
274              if (ophtable[myedegrees[k].pid] == -1) 
275                myedegrees[k].gv -= vsize[ii];
276            }
277          }
278        }
279
280        for (kk=0; kk<orinfo->ndegrees; kk++) 
281          ophtable[oedegrees[kk].pid] = -1;
282        ophtable[other] = -1;
283      }
284
285      /* Compute the max vgain */
286      for (k=0; k<myndegrees; k++) {
287        if (myedegrees[k].gv > myrinfo->gv)
288          myrinfo->gv = myedegrees[k].gv;
289      }
290    }
291
292    if (myrinfo->ed > 0 && myrinfo->id == 0) 
293      myrinfo->gv += vsize[i];
294
295    if (myrinfo->gv >= 0 || myrinfo->ed-myrinfo->id >= 0)
296      BNDInsert(graph->nbnd, bndind, bndptr, i);
297  }
298
299  idxwspacefree(ctrl, nparts);
300
301}
302
303
304
305/*************************************************************************
306* This function projects a partition, and at the same time computes the
307* parameters for refinement.
308**************************************************************************/
309void ProjectVolKWayPartition(CtrlType *ctrl, GraphType *graph, int nparts)
310{
311  int i, j, k, nvtxs, me, other, istart, iend, ndegrees;
312  idxtype *xadj, *adjncy, *adjwgt, *adjwgtsum;
313  idxtype *cmap, *where;
314  idxtype *cwhere;
315  GraphType *cgraph;
316  VRInfoType *crinfo, *rinfo, *myrinfo;
317  VEDegreeType *myedegrees;
318  idxtype *htable;
319
320  cgraph = graph->coarser;
321  cwhere = cgraph->where;
322  crinfo = cgraph->vrinfo;
323
324  nvtxs = graph->nvtxs;
325  cmap = graph->cmap;
326  xadj = graph->xadj;
327  adjncy = graph->adjncy;
328  adjwgt = graph->adjwgt;
329  adjwgtsum = graph->adjwgtsum;
330
331  AllocateVolKWayPartitionMemory(ctrl, graph, nparts);
332  where = graph->where;
333  rinfo = graph->vrinfo;
334
335  /* Go through and project partition and compute id/ed for the nodes */
336  for (i=0; i<nvtxs; i++) {
337    k = cmap[i];
338    where[i] = cwhere[k];
339    cmap[i] = crinfo[k].ed;  /* For optimization */
340  }
341
342  htable = idxset(nparts, -1, idxwspacemalloc(ctrl, nparts));
343
344  ctrl->wspace.cdegree = 0;
345  for (i=0; i<nvtxs; i++) {
346    me = where[i];
347
348    myrinfo = rinfo+i;
349    myrinfo->id = myrinfo->ed = myrinfo->nid = myrinfo->ndegrees = 0;
350    myrinfo->edegrees = NULL;
351
352    myrinfo->id = adjwgtsum[i];
353    myrinfo->nid = xadj[i+1]-xadj[i];
354
355    if (cmap[i] > 0) { /* If it is an interface node. Note cmap[i] = crinfo[cmap[i]].ed */
356      istart = xadj[i];
357      iend = xadj[i+1];
358
359      myedegrees = myrinfo->edegrees = ctrl->wspace.vedegrees+ctrl->wspace.cdegree;
360      ctrl->wspace.cdegree += iend-istart;
361
362      ndegrees = 0;
363      for (j=istart; j<iend; j++) {
364        other = where[adjncy[j]];
365        if (me != other) {
366          myrinfo->ed += adjwgt[j];
367          myrinfo->nid--;
368          if ((k = htable[other]) == -1) {
369            htable[other] = ndegrees;
370            myedegrees[ndegrees].gv = 0;
371            myedegrees[ndegrees].pid = other;
372            myedegrees[ndegrees].ed = adjwgt[j];
373            myedegrees[ndegrees++].ned = 1;
374          }
375          else {
376            myedegrees[k].ed += adjwgt[j];
377            myedegrees[k].ned++;
378          }
379        }
380      }
381      myrinfo->id -= myrinfo->ed;
382
383      /* Remove space for edegrees if it was interior */
384      if (myrinfo->ed == 0) { 
385        myrinfo->edegrees = NULL;
386        ctrl->wspace.cdegree -= iend-istart;
387      }
388      else {
389        myrinfo->ndegrees = ndegrees;
390
391        for (j=0; j<ndegrees; j++)
392          htable[myedegrees[j].pid] = -1;
393      }
394    }
395  }
396
397  ComputeKWayVolGains(ctrl, graph, nparts);
398
399  idxcopy(nparts, cgraph->pwgts, graph->pwgts);
400  graph->mincut = cgraph->mincut;
401
402  FreeGraph(graph->coarser);
403  graph->coarser = NULL;
404
405  idxwspacefree(ctrl, nparts);
406
407}
408
409
410
411/*************************************************************************
412* This function computes the boundary definition for balancing
413**************************************************************************/
414void ComputeVolKWayBoundary(CtrlType *ctrl, GraphType *graph, int nparts)
415{
416  int i, nvtxs, nbnd;
417  idxtype *bndind, *bndptr;
418
419  nvtxs = graph->nvtxs;
420  bndind = graph->bndind;
421  bndptr = idxset(nvtxs, -1, graph->bndptr);
422
423
424  /*------------------------------------------------------------
425  / Compute the new boundary
426  /------------------------------------------------------------*/
427  nbnd = 0;
428  for (i=0; i<nvtxs; i++) {
429    if (graph->vrinfo[i].gv >=0 || graph->vrinfo[i].ed-graph->vrinfo[i].id >= 0) 
430      BNDInsert(nbnd, bndind, bndptr, i);
431  }
432
433  graph->nbnd = nbnd;
434}
435
436/*************************************************************************
437* This function computes the boundary definition for balancing
438**************************************************************************/
439void ComputeVolKWayBalanceBoundary(CtrlType *ctrl, GraphType *graph, int nparts)
440{
441  int i, nvtxs, nbnd;
442  idxtype *bndind, *bndptr;
443
444  nvtxs = graph->nvtxs;
445  bndind = graph->bndind;
446  bndptr = idxset(nvtxs, -1, graph->bndptr);
447
448
449  /*------------------------------------------------------------
450  / Compute the new boundary
451  /------------------------------------------------------------*/
452  nbnd = 0;
453  for (i=0; i<nvtxs; i++) {
454    if (graph->vrinfo[i].ed > 0) 
455      BNDInsert(nbnd, bndind, bndptr, i);
456  }
457
458  graph->nbnd = nbnd;
459}
460
Note: See TracBrowser for help on using the repository browser.