refine.c
Go to the documentation of this file.
1 /*
2 \file
3 \brief This file contains the driving routines for multilevel refinement
4 
5 \date Started 7/24/1997
6 \author George
7 \author Copyright 1997-2009, Regents of the University of Minnesota
8 \version\verbatim $Id: refine.c 10513 2011-07-07 22:06:03Z karypis $ \endverbatim
9 */
10 
11 #include "metislib.h"
12 
13 
14 /*************************************************************************/
16 /*************************************************************************/
17 void Refine2Way(ctrl_t *ctrl, graph_t *orggraph, graph_t *graph, real_t *tpwgts)
18 {
19 
21 
22  /* Compute the parameters of the coarsest graph */
23  Compute2WayPartitionParams(ctrl, graph);
24 
25  for (;;) {
26  ASSERT(CheckBnd(graph));
27 
29 
30  Balance2Way(ctrl, graph, tpwgts);
31 
32  FM_2WayRefine(ctrl, graph, tpwgts, ctrl->niter);
33 
35 
36  if (graph == orggraph)
37  break;
38 
39  graph = graph->finer;
41  Project2WayPartition(ctrl, graph);
43  }
44 
46 }
47 
48 
49 /*************************************************************************/
51 /*************************************************************************/
53 {
54  idx_t nvtxs, ncon;
55 
56  nvtxs = graph->nvtxs;
57  ncon = graph->ncon;
58 
59  graph->pwgts = imalloc(2*ncon, "Allocate2WayPartitionMemory: pwgts");
60  graph->where = imalloc(nvtxs, "Allocate2WayPartitionMemory: where");
61  graph->bndptr = imalloc(nvtxs, "Allocate2WayPartitionMemory: bndptr");
62  graph->bndind = imalloc(nvtxs, "Allocate2WayPartitionMemory: bndind");
63  graph->id = imalloc(nvtxs, "Allocate2WayPartitionMemory: id");
64  graph->ed = imalloc(nvtxs, "Allocate2WayPartitionMemory: ed");
65 }
66 
67 
68 /*************************************************************************/
70 /*************************************************************************/
72 {
73  idx_t i, j, nvtxs, ncon, nbnd, mincut, istart, iend, tid, ted, me;
74  idx_t *xadj, *vwgt, *adjncy, *adjwgt, *pwgts;
75  idx_t *where, *bndptr, *bndind, *id, *ed;
76 
77  nvtxs = graph->nvtxs;
78  ncon = graph->ncon;
79  xadj = graph->xadj;
80  vwgt = graph->vwgt;
81  adjncy = graph->adjncy;
82  adjwgt = graph->adjwgt;
83 
84  where = graph->where;
85  id = graph->id;
86  ed = graph->ed;
87 
88  pwgts = iset(2*ncon, 0, graph->pwgts);
89  bndptr = iset(nvtxs, -1, graph->bndptr);
90  bndind = graph->bndind;
91 
92  /* Compute pwgts */
93  if (ncon == 1) {
94  for (i=0; i<nvtxs; i++) {
95  ASSERT(where[i] >= 0 && where[i] <= 1);
96  pwgts[where[i]] += vwgt[i];
97  }
98  ASSERT(pwgts[0]+pwgts[1] == graph->tvwgt[0]);
99  }
100  else {
101  for (i=0; i<nvtxs; i++) {
102  me = where[i];
103  for (j=0; j<ncon; j++)
104  pwgts[me*ncon+j] += vwgt[i*ncon+j];
105  }
106  }
107 
108 
109  /* Compute the required info for refinement */
110  for (nbnd=0, mincut=0, i=0; i<nvtxs; i++) {
111  istart = xadj[i];
112  iend = xadj[i+1];
113 
114  me = where[i];
115  tid = ted = 0;
116 
117  for (j=istart; j<iend; j++) {
118  if (me == where[adjncy[j]])
119  tid += adjwgt[j];
120  else
121  ted += adjwgt[j];
122  }
123  id[i] = tid;
124  ed[i] = ted;
125 
126  if (ted > 0 || istart == iend) {
127  BNDInsert(nbnd, bndind, bndptr, i);
128  mincut += ted;
129  }
130  }
131 
132  graph->mincut = mincut/2;
133  graph->nbnd = nbnd;
134 
135 }
136 
137 
138 /*************************************************************************/
140 /*************************************************************************/
142 {
143  idx_t i, j, istart, iend, nvtxs, nbnd, me, tid, ted;
144  idx_t *xadj, *adjncy, *adjwgt;
145  idx_t *cmap, *where, *bndptr, *bndind;
146  idx_t *cwhere, *cbndptr;
147  idx_t *id, *ed;
148  graph_t *cgraph;
149 
150  Allocate2WayPartitionMemory(ctrl, graph);
151 
152  cgraph = graph->coarser;
153  cwhere = cgraph->where;
154  cbndptr = cgraph->bndptr;
155 
156  nvtxs = graph->nvtxs;
157  cmap = graph->cmap;
158  xadj = graph->xadj;
159  adjncy = graph->adjncy;
160  adjwgt = graph->adjwgt;
161 
162  where = graph->where;
163  id = graph->id;
164  ed = graph->ed;
165 
166  bndptr = iset(nvtxs, -1, graph->bndptr);
167  bndind = graph->bndind;
168 
169  /* Project the partition and record which of these nodes came from the
170  coarser boundary */
171  for (i=0; i<nvtxs; i++) {
172  j = cmap[i];
173  where[i] = cwhere[j];
174  cmap[i] = cbndptr[j];
175  }
176 
177  /* Compute the refinement information of the nodes */
178  for (nbnd=0, i=0; i<nvtxs; i++) {
179  istart = xadj[i];
180  iend = xadj[i+1];
181 
182  tid = ted = 0;
183  if (cmap[i] == -1) { /* Interior node. Note that cmap[i] = cbndptr[cmap[i]] */
184  for (j=istart; j<iend; j++)
185  tid += adjwgt[j];
186  }
187  else { /* Potentially an interface node */
188  me = where[i];
189  for (j=istart; j<iend; j++) {
190  if (me == where[adjncy[j]])
191  tid += adjwgt[j];
192  else
193  ted += adjwgt[j];
194  }
195  }
196  id[i] = tid;
197  ed[i] = ted;
198 
199  if (ted > 0 || istart == iend)
200  BNDInsert(nbnd, bndind, bndptr, i);
201  }
202  graph->mincut = cgraph->mincut;
203  graph->nbnd = nbnd;
204 
205  /* copy pwgts */
206  icopy(2*graph->ncon, cgraph->pwgts, graph->pwgts);
207 
208  FreeGraph(&graph->coarser);
209  graph->coarser = NULL;
210 }
211 
idx_t idx_t idx_t idx_t * vwgt
idx_t * bndind
double RefTmr
#define Balance2Way
Definition: rename.h:21
#define gk_startcputimer(tmr)
Definition: gk_macros.h:33
idx_t * xadj
#define imalloc
Definition: gklib_rename.h:42
#define gk_stopcputimer(tmr)
Definition: gk_macros.h:34
idx_t * pwgts
idx_t * adjwgt
struct graph_t * finer
#define FreeGraph
Definition: rename.h:98
idx_t * bndptr
idx_t idx_t * xadj
idx_t * where
idx_t nvtxs
idx_t * id
mdbglvl_et dbglvl
NonlinearFactorGraph graph
#define FM_2WayRefine
Definition: rename.h:74
static const Similarity3 id
idx_t * ed
struct graph_t * coarser
idx_t niter
#define ASSERT(expression)
Definition: ccolamd.c:872
double UncoarsenTmr
#define BNDInsert(nbnd, bndind, bndptr, vtx)
idx_t * cmap
int32_t idx_t
idx_t ncon
#define CheckBnd
Definition: rename.h:65
float real_t
idx_t * ncon
#define NULL
Definition: ccolamd.c:609
idx_t idx_t idx_t idx_t idx_t idx_t idx_t real_t * tpwgts
idx_t mincut
idx_t idx_t idx_t idx_t idx_t idx_t * adjwgt
#define iset
Definition: gklib_rename.h:67
#define icopy
Definition: gklib_rename.h:28
idx_t idx_t idx_t idx_t * where
idx_t * adjncy
idx_t * tvwgt
idx_t idx_t idx_t * adjncy
void Project2WayPartition(ctrl_t *ctrl, graph_t *graph)
Definition: refine.c:141
#define IFSET(a, flag, cmd)
Definition: gk_macros.h:45
void Allocate2WayPartitionMemory(ctrl_t *ctrl, graph_t *graph)
Definition: refine.c:52
double ProjectTmr
std::ptrdiff_t j
void Refine2Way(ctrl_t *ctrl, graph_t *orggraph, graph_t *graph, real_t *tpwgts)
Definition: refine.c:17
idx_t * vwgt
void Compute2WayPartitionParams(ctrl_t *ctrl, graph_t *graph)
Definition: refine.c:71


gtsam
Author(s):
autogenerated on Tue Jul 4 2023 02:35:32