kmetis.c
Go to the documentation of this file.
1 
12 #include "metislib.h"
13 
14 
15 /*************************************************************************/
17 /*************************************************************************/
21  idx_t *part)
22 {
23  int sigrval=0, renumber=0;
24  graph_t *graph;
25  ctrl_t *ctrl;
26 
27  /* set up malloc cleaning code and signal catchers */
28  if (!gk_malloc_init())
29  return METIS_ERROR_MEMORY;
30 
31  gk_sigtrap();
32 
33  if ((sigrval = gk_sigcatch()) != 0)
34  goto SIGTHROW;
35 
36 
37  /* set up the run parameters */
38  ctrl = SetupCtrl(METIS_OP_KMETIS, options, *ncon, *nparts, tpwgts, ubvec);
39  if (!ctrl) {
40  gk_siguntrap();
41  return METIS_ERROR_INPUT;
42  }
43 
44  /* if required, change the numbering to 0 */
45  if (ctrl->numflag == 1) {
46  Change2CNumbering(*nvtxs, xadj, adjncy);
47  renumber = 1;
48  }
49 
50  /* set up the graph */
51  graph = SetupGraph(ctrl, *nvtxs, *ncon, xadj, adjncy, vwgt, vsize, adjwgt);
52 
53  /* set up multipliers for making balance computations easier */
54  SetupKWayBalMultipliers(ctrl, graph);
55 
56  /* set various run parameters that depend on the graph */
57  ctrl->CoarsenTo = gk_max((*nvtxs)/(20*gk_log2(*nparts)), 30*(*nparts));
58  ctrl->nIparts = (ctrl->CoarsenTo == 30*(*nparts) ? 4 : 5);
59 
60  /* take care contiguity requests for disconnected graphs */
61  if (ctrl->contig && !IsConnected(graph, 0))
62  gk_errexit(SIGERR, "METIS Error: A contiguous partition is requested for a non-contiguous input graph.\n");
63 
64  /* allocate workspace memory */
65  AllocateWorkSpace(ctrl, graph);
66 
67  /* start the partitioning */
68  IFSET(ctrl->dbglvl, METIS_DBG_TIME, InitTimers(ctrl));
70 
71  *objval = MlevelKWayPartitioning(ctrl, graph, part);
72 
74  IFSET(ctrl->dbglvl, METIS_DBG_TIME, PrintTimers(ctrl));
75 
76  /* clean up */
77  FreeCtrl(&ctrl);
78 
79 SIGTHROW:
80  /* if required, change the numbering back to 1 */
81  if (renumber)
82  Change2FNumbering(*nvtxs, xadj, adjncy, part);
83 
84  gk_siguntrap();
86 
87  return metis_rcode(sigrval);
88 }
89 
90 
91 /*************************************************************************/
102 /*************************************************************************/
104 {
105  idx_t i, j, objval=0, curobj=0, bestobj=0;
106  real_t curbal=0.0, bestbal=0.0;
107  graph_t *cgraph;
108  int status;
109 
110 
111  for (i=0; i<ctrl->ncuts; i++) {
112  cgraph = CoarsenGraph(ctrl, graph);
113 
115  AllocateKWayPartitionMemory(ctrl, cgraph);
116 
117  /* Release the work space */
118  FreeWorkSpace(ctrl);
119 
120  /* Compute the initial partitioning */
121  InitKWayPartitioning(ctrl, cgraph);
122 
123  /* Re-allocate the work space */
124  AllocateWorkSpace(ctrl, graph);
125  AllocateRefinementWorkSpace(ctrl, 2*cgraph->nedges);
126 
128  IFSET(ctrl->dbglvl, METIS_DBG_IPART,
129  printf("Initial %"PRIDX"-way partitioning cut: %"PRIDX"\n", ctrl->nparts, objval));
130 
131  RefineKWay(ctrl, graph, cgraph);
132 
133  switch (ctrl->objtype) {
134  case METIS_OBJTYPE_CUT:
135  curobj = graph->mincut;
136  break;
137 
138  case METIS_OBJTYPE_VOL:
139  curobj = graph->minvol;
140  break;
141 
142  default:
143  gk_errexit(SIGERR, "Unknown objtype: %d\n", ctrl->objtype);
144  }
145 
146  curbal = ComputeLoadImbalanceDiff(graph, ctrl->nparts, ctrl->pijbm, ctrl->ubfactors);
147 
148  if (i == 0
149  || (curbal <= 0.0005 && bestobj > curobj)
150  || (bestbal > 0.0005 && curbal < bestbal)) {
151  icopy(graph->nvtxs, graph->where, part);
152  bestobj = curobj;
153  bestbal = curbal;
154  }
155 
156  FreeRData(graph);
157 
158  if (bestobj == 0)
159  break;
160  }
161 
162  FreeGraph(&graph);
163 
164  return bestobj;
165 }
166 
167 
168 /*************************************************************************/
171 /*************************************************************************/
173 {
174  idx_t i, ntrials, options[METIS_NOPTIONS], curobj=0, bestobj=0;
175  idx_t *bestwhere=NULL;
176  real_t *ubvec=NULL;
177  int status;
178 
179  METIS_SetDefaultOptions(options);
180  options[METIS_OPTION_NITER] = 10;
182  options[METIS_OPTION_NO2HOP] = ctrl->no2hop;
183 
184 
185  ubvec = rmalloc(graph->ncon, "InitKWayPartitioning: ubvec");
186  for (i=0; i<graph->ncon; i++)
187  ubvec[i] = (real_t)pow(ctrl->ubfactors[i], 1.0/log(ctrl->nparts));
188 
189 
190  switch (ctrl->objtype) {
191  case METIS_OBJTYPE_CUT:
192  case METIS_OBJTYPE_VOL:
193  options[METIS_OPTION_NCUTS] = ctrl->nIparts;
194  status = METIS_PartGraphRecursive(&graph->nvtxs, &graph->ncon,
195  graph->xadj, graph->adjncy, graph->vwgt, graph->vsize,
196  graph->adjwgt, &ctrl->nparts, ctrl->tpwgts, ubvec,
197  options, &curobj, graph->where);
198 
199  if (status != METIS_OK)
200  gk_errexit(SIGERR, "Failed during initial partitioning\n");
201 
202  break;
203 
204 #ifdef XXX /* This does not seem to help */
205  case METIS_OBJTYPE_VOL:
206  bestwhere = imalloc(graph->nvtxs, "InitKWayPartitioning: bestwhere");
207  options[METIS_OPTION_NCUTS] = 2;
208 
209  ntrials = (ctrl->nIparts+1)/2;
210  for (i=0; i<ntrials; i++) {
211  status = METIS_PartGraphRecursive(&graph->nvtxs, &graph->ncon,
212  graph->xadj, graph->adjncy, graph->vwgt, graph->vsize,
213  graph->adjwgt, &ctrl->nparts, ctrl->tpwgts, ubvec,
214  options, &curobj, graph->where);
215  if (status != METIS_OK)
216  gk_errexit(SIGERR, "Failed during initial partitioning\n");
217 
218  curobj = ComputeVolume(graph, graph->where);
219 
220  if (i == 0 || bestobj > curobj) {
221  bestobj = curobj;
222  if (i < ntrials-1)
223  icopy(graph->nvtxs, graph->where, bestwhere);
224  }
225 
226  if (bestobj == 0)
227  break;
228  }
229  if (bestobj != curobj)
230  icopy(graph->nvtxs, bestwhere, graph->where);
231 
232  break;
233 #endif
234 
235  default:
236  gk_errexit(SIGERR, "Unknown objtype: %d\n", ctrl->objtype);
237  }
238 
239  gk_free((void **)&ubvec, &bestwhere, LTERM);
240 
241 }
242 
243 
idx_t idx_t idx_t idx_t * vwgt
void InitKWayPartitioning(ctrl_t *ctrl, graph_t *graph)
Definition: kmetis.c:172
int gk_siguntrap()
Definition: error.c:116
double TotalTmr
real_t * tpwgts
idx_t idx_t idx_t idx_t idx_t idx_t idx_t real_t real_t idx_t idx_t idx_t * part
#define gk_startcputimer(tmr)
Definition: gk_macros.h:33
#define SetupGraph
Definition: rename.h:90
#define ComputeLoadImbalanceDiff
Definition: rename.h:144
idx_t * xadj
#define imalloc
Definition: gklib_rename.h:42
#define SetupKWayBalMultipliers
Definition: rename.h:195
#define gk_stopcputimer(tmr)
Definition: gk_macros.h:34
idx_t * adjwgt
#define FreeGraph
Definition: rename.h:98
#define metis_rcode
Definition: rename.h:247
idx_t idx_t * xadj
idx_t minvol
idx_t * where
const Eigen::CwiseBinaryOp< Eigen::internal::scalar_pow_op< typename Derived::Scalar, typename ExponentDerived::Scalar >, const Derived, const ExponentDerived > pow(const Eigen::ArrayBase< Derived > &x, const Eigen::ArrayBase< ExponentDerived > &exponents)
idx_t idx_t idx_t idx_t idx_t idx_t idx_t * nparts
idx_t nvtxs
idx_t * vsize
#define AllocateKWayPartitionMemory
Definition: rename.h:124
void gk_errexit(int signum, char *f_str,...)
Definition: error.c:77
mdbglvl_et dbglvl
idx_t ncuts
#define CoarsenGraph
Definition: rename.h:35
NonlinearFactorGraph graph
EIGEN_DEVICE_FUNC const LogReturnType log() const
int METIS_SetDefaultOptions(idx_t *options)
Definition: auxapi.c:36
int gk_log2(int)
Definition: GKlib/util.c:83
double InitPartTmr
idx_t idx_t idx_t idx_t idx_t * vsize
#define PRIDX
idx_t nedges
#define METIS_NOPTIONS
#define AllocateRefinementWorkSpace
Definition: rename.h:251
#define AllocateWorkSpace
Definition: rename.h:250
idx_t idx_t idx_t idx_t idx_t idx_t real_t idx_t idx_t * objval
#define SIGERR
Definition: gk_defs.h:38
#define gk_max(a, b)
Definition: gk_macros.h:16
int32_t idx_t
#define InitTimers
Definition: rename.h:238
#define Change2CNumbering
Definition: rename.h:81
idx_t nparts
idx_t no2hop
#define IsConnected
Definition: rename.h:54
real_t * pijbm
idx_t ncon
idx_t idx_t idx_t idx_t idx_t idx_t idx_t real_t real_t * ubvec
void gk_malloc_cleanup(int showstats)
Definition: memory.c:118
float real_t
idx_t * ncon
#define NULL
Definition: ccolamd.c:609
#define ComputeVolume
Definition: rename.h:63
idx_t idx_t idx_t idx_t idx_t idx_t idx_t real_t * tpwgts
#define SetupCtrl
Definition: rename.h:194
idx_t mincut
idx_t idx_t idx_t idx_t idx_t idx_t * adjwgt
#define FreeCtrl
Definition: rename.h:198
real_t * ubfactors
#define icopy
Definition: gklib_rename.h:28
void gk_free(void **ptr1,...)
Definition: memory.c:202
idx_t * adjncy
#define gk_sigcatch()
Definition: gk_macros.h:52
int METIS_PartGraphKway(idx_t *nvtxs, idx_t *ncon, idx_t *xadj, idx_t *adjncy, idx_t *vwgt, idx_t *vsize, idx_t *adjwgt, idx_t *nparts, real_t *tpwgts, real_t *ubvec, idx_t *options, idx_t *objval, idx_t *part)
Definition: kmetis.c:18
idx_t contig
idx_t idx_t idx_t * adjncy
#define PrintTimers
Definition: rename.h:239
#define FreeWorkSpace
Definition: rename.h:252
#define FreeRData
Definition: rename.h:97
int METIS_PartGraphRecursive(idx_t *nvtxs, idx_t *ncon, idx_t *xadj, idx_t *adjncy, idx_t *vwgt, idx_t *vsize, idx_t *adjwgt, idx_t *nparts, real_t *tpwgts, real_t *ubvec, idx_t *options, idx_t *objval, idx_t *part)
Recursive partitioning routine.
Definition: pmetis.c:91
idx_t CoarsenTo
idx_t nIparts
#define IFSET(a, flag, cmd)
Definition: gk_macros.h:45
#define RefineKWay
Definition: rename.h:123
idx_t MlevelKWayPartitioning(ctrl_t *ctrl, graph_t *graph, idx_t *part)
Definition: kmetis.c:103
int gk_malloc_init()
Definition: memory.c:99
std::ptrdiff_t j
int gk_sigtrap()
Definition: error.c:98
mobjtype_et objtype
#define Change2FNumbering
Definition: rename.h:82
idx_t numflag
#define rmalloc
Definition: gklib_rename.h:93
#define LTERM
Definition: gk_defs.h:14
idx_t * vwgt


gtsam
Author(s):
autogenerated on Tue Jul 4 2023 02:34:30