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 */
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 */
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 
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 
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:
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");
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 
objval
idx_t idx_t idx_t idx_t idx_t idx_t real_t idx_t idx_t * objval
Definition: include/metis.h:215
FreeCtrl
#define FreeCtrl
Definition: rename.h:198
gk_log2
int gk_log2(int)
Definition: GKlib/util.c:83
ubvec
idx_t idx_t idx_t idx_t idx_t idx_t idx_t real_t real_t * ubvec
Definition: include/metis.h:199
gk_sigtrap
int gk_sigtrap()
Definition: error.c:97
METIS_OPTION_OBJTYPE
@ METIS_OPTION_OBJTYPE
Definition: include/metis.h:272
adjwgt
idx_t idx_t idx_t idx_t idx_t idx_t * adjwgt
Definition: include/metis.h:198
ctrl_t::pijbm
real_t * pijbm
Definition: libmetis/struct.h:170
ctrl_t::nparts
idx_t nparts
Definition: libmetis/struct.h:163
CoarsenGraph
#define CoarsenGraph
Definition: rename.h:35
gk_free
void gk_free(void **ptr1,...)
Definition: memory.c:202
vsize
idx_t idx_t idx_t idx_t idx_t * vsize
Definition: include/metis.h:198
METIS_PartGraphRecursive
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
Change2CNumbering
#define Change2CNumbering
Definition: rename.h:81
ctrl_t::ubfactors
real_t * ubfactors
Definition: libmetis/struct.h:167
ctrl_t
Definition: libmetis/struct.h:139
AllocateRefinementWorkSpace
#define AllocateRefinementWorkSpace
Definition: rename.h:251
gk_siguntrap
int gk_siguntrap()
Definition: error.c:115
metis_rcode
#define metis_rcode
Definition: rename.h:247
tpwgts
idx_t idx_t idx_t idx_t idx_t idx_t idx_t real_t * tpwgts
Definition: include/metis.h:199
adjncy
idx_t idx_t idx_t * adjncy
Definition: include/metis.h:198
AllocateWorkSpace
#define AllocateWorkSpace
Definition: rename.h:250
ctrl_t::contig
idx_t contig
Definition: libmetis/struct.h:151
imalloc
#define imalloc
Definition: gklib_rename.h:42
ctrl_t::tpwgts
real_t * tpwgts
Definition: libmetis/struct.h:169
log
const EIGEN_DEVICE_FUNC LogReturnType log() const
Definition: ArrayCwiseUnaryOps.h:128
graph_t::nedges
idx_t nedges
Definition: libmetis/struct.h:83
IFSET
#define IFSET(a, flag, cmd)
Definition: gk_macros.h:45
gk_sigcatch
#define gk_sigcatch()
Definition: gk_macros.h:52
MlevelKWayPartitioning
idx_t MlevelKWayPartitioning(ctrl_t *ctrl, graph_t *graph, idx_t *part)
Definition: kmetis.c:103
ctrl_t::InitPartTmr
double InitPartTmr
Definition: libmetis/struct.h:176
InitKWayPartitioning
void InitKWayPartitioning(ctrl_t *ctrl, graph_t *graph)
Definition: kmetis.c:172
METIS_OPTION_NITER
@ METIS_OPTION_NITER
Definition: include/metis.h:277
METIS_PartGraphKway
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
IsConnected
#define IsConnected
Definition: rename.h:54
Change2FNumbering
#define Change2FNumbering
Definition: rename.h:82
METIS_OP_KMETIS
@ METIS_OP_KMETIS
Definition: include/metis.h:264
ComputeVolume
#define ComputeVolume
Definition: rename.h:63
RefineKWay
#define RefineKWay
Definition: rename.h:123
ncon
idx_t * ncon
Definition: include/metis.h:197
nparts
idx_t idx_t idx_t idx_t idx_t idx_t idx_t * nparts
Definition: include/metis.h:199
METIS_DBG_IPART
@ METIS_DBG_IPART
Definition: include/metis.h:344
gk_startcputimer
#define gk_startcputimer(tmr)
Definition: gk_macros.h:33
j
std::ptrdiff_t j
Definition: tut_arithmetic_redux_minmax.cpp:2
SetupGraph
#define SetupGraph
Definition: rename.h:90
METIS_OK
@ METIS_OK
Definition: include/metis.h:254
ctrl_t::nIparts
idx_t nIparts
Definition: libmetis/struct.h:148
SetupKWayBalMultipliers
#define SetupKWayBalMultipliers
Definition: rename.h:195
LTERM
#define LTERM
Definition: gk_defs.h:14
ctrl_t::objtype
mobjtype_et objtype
Definition: libmetis/struct.h:141
ctrl_t::CoarsenTo
idx_t CoarsenTo
Definition: libmetis/struct.h:147
SIGERR
#define SIGERR
Definition: gk_defs.h:38
SetupCtrl
#define SetupCtrl
Definition: rename.h:194
FreeRData
#define FreeRData
Definition: rename.h:97
vwgt
idx_t idx_t idx_t idx_t * vwgt
Definition: include/metis.h:198
part
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
Definition: include/metis.h:200
ctrl_t::TotalTmr
double TotalTmr
Definition: libmetis/struct.h:176
InitTimers
#define InitTimers
Definition: rename.h:238
METIS_SetDefaultOptions
int METIS_SetDefaultOptions(idx_t *options)
Definition: auxapi.c:36
Eigen::ArrayBase::pow
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)
Definition: GlobalFunctions.h:143
xadj
idx_t idx_t * xadj
Definition: include/metis.h:197
FreeGraph
#define FreeGraph
Definition: rename.h:98
FreeWorkSpace
#define FreeWorkSpace
Definition: rename.h:252
PRIDX
#define PRIDX
Definition: include/metis.h:107
METIS_OBJTYPE_VOL
@ METIS_OBJTYPE_VOL
Definition: include/metis.h:356
real_t
float real_t
Definition: include/metis.h:132
METIS_NOPTIONS
#define METIS_NOPTIONS
Definition: include/metis.h:175
AllocateKWayPartitionMemory
#define AllocateKWayPartitionMemory
Definition: rename.h:124
METIS_OPTION_NO2HOP
@ METIS_OPTION_NO2HOP
Definition: include/metis.h:280
METIS_OBJTYPE_CUT
@ METIS_OBJTYPE_CUT
Definition: include/metis.h:355
ctrl_t::dbglvl
mdbglvl_et dbglvl
Definition: libmetis/struct.h:142
NULL
#define NULL
Definition: ccolamd.c:609
metislib.h
ctrl_t::ncuts
idx_t ncuts
Definition: libmetis/struct.h:157
ctrl_t::no2hop
idx_t no2hop
Definition: libmetis/struct.h:149
METIS_ERROR_INPUT
@ METIS_ERROR_INPUT
Definition: include/metis.h:255
icopy
#define icopy
Definition: gklib_rename.h:28
graph
NonlinearFactorGraph graph
Definition: doc/Code/OdometryExample.cpp:2
ctrl_t::numflag
idx_t numflag
Definition: libmetis/struct.h:159
rmalloc
#define rmalloc
Definition: gklib_rename.h:93
gk_max
#define gk_max(a, b)
Definition: gk_macros.h:16
METIS_ERROR_MEMORY
@ METIS_ERROR_MEMORY
Definition: include/metis.h:256
gk_stopcputimer
#define gk_stopcputimer(tmr)
Definition: gk_macros.h:34
options
Definition: options.h:16
gk_malloc_cleanup
void gk_malloc_cleanup(int showstats)
Definition: memory.c:118
i
int i
Definition: BiCGSTAB_step_by_step.cpp:9
gk_errexit
void gk_errexit(int signum, char *f_str,...)
Definition: error.c:76
METIS_OPTION_NCUTS
@ METIS_OPTION_NCUTS
Definition: include/metis.h:278
graph_t
Definition: libmetis/struct.h:82
ComputeLoadImbalanceDiff
#define ComputeLoadImbalanceDiff
Definition: rename.h:144
idx_t
int32_t idx_t
Definition: include/metis.h:101
METIS_DBG_TIME
@ METIS_DBG_TIME
Definition: include/metis.h:341
PrintTimers
#define PrintTimers
Definition: rename.h:239
gk_malloc_init
int gk_malloc_init()
Definition: memory.c:99


gtsam
Author(s):
autogenerated on Fri Nov 1 2024 03:33:01