Go to the documentation of this file.
96 int sigrval=0, renumber=0;
165 if ((nvtxs =
graph->nvtxs) == 0) {
166 printf(
"\t***Cannot bisect a graph with 0 vertices!\n"
167 "\t***You are trying to partition a graph into too many parts!\n");
179 tpwgts2[
ncon+
i] = 1.0 - tpwgts2[
i];
187 label =
graph->label;
189 for (
i=0;
i<nvtxs;
i++)
228 idx_t i, niparts, bestobj=0, curobj=0, *bestwhere=
NULL;
230 real_t bestbal=0.0, curbal=0.0;
247 curobj =
graph->mincut;
251 || (curbal <= 0.0005 && bestobj > curobj)
252 || (bestbal > 0.0005 && curbal < bestbal)) {
255 if (i < ctrl->ncuts-1)
263 if (i < ctrl->ncuts-1)
267 if (bestobj != curobj) {
283 idx_t i,
j, k,
l, istart, iend, mypart, nvtxs,
ncon, snvtxs[2], snedges[2];
285 idx_t *sxadj[2], *svwgt[2], *sadjncy[2], *sadjwgt[2], *slabel[2];
287 idx_t *auxadjncy, *auxadjwgt;
294 nvtxs =
graph->nvtxs;
300 label =
graph->label;
302 bndptr =
graph->bndptr;
308 snvtxs[0] = snvtxs[1] = snedges[0] = snedges[1] = 0;
309 for (
i=0;
i<nvtxs;
i++) {
311 rename[
i] = snvtxs[k]++;
316 sxadj[0] = lgraph->
xadj;
317 svwgt[0] = lgraph->
vwgt;
318 sadjncy[0] = lgraph->
adjncy;
319 sadjwgt[0] = lgraph->
adjwgt;
320 slabel[0] = lgraph->
label;
323 sxadj[1] = rgraph->
xadj;
324 svwgt[1] = rgraph->
vwgt;
325 sadjncy[1] = rgraph->
adjncy;
326 sadjwgt[1] = rgraph->
adjwgt;
327 slabel[1] = rgraph->
label;
329 snvtxs[0] = snvtxs[1] = snedges[0] = snedges[1] = 0;
330 sxadj[0][0] = sxadj[1][0] = 0;
331 for (
i=0;
i<nvtxs;
i++) {
336 if (bndptr[
i] == -1) {
337 auxadjncy = sadjncy[mypart] + snedges[mypart] - istart;
338 auxadjwgt = sadjwgt[mypart] + snedges[mypart] - istart;
339 for(
j=istart;
j<iend;
j++) {
343 snedges[mypart] += iend-istart;
346 auxadjncy = sadjncy[mypart];
347 auxadjwgt = sadjwgt[mypart];
349 for (
j=istart;
j<iend;
j++) {
351 if (
where[k] == mypart) {
360 for (k=0; k<
ncon; k++)
363 slabel[mypart][snvtxs[mypart]] = label[
i];
364 sxadj[mypart][++snvtxs[mypart]] = snedges[mypart];
367 for (mypart=0; mypart<2; mypart++) {
368 iend = sxadj[mypart][snvtxs[mypart]];
369 auxadjncy = sadjncy[mypart];
370 for (
i=0;
i<iend;
i++)
371 auxadjncy[
i] = rename[auxadjncy[
i]];
374 lgraph->
nedges = snedges[0];
375 rgraph->
nedges = snedges[1];
idx_t idx_t idx_t idx_t idx_t idx_t real_t idx_t idx_t * objval
idx_t idx_t idx_t idx_t idx_t idx_t idx_t real_t real_t * ubvec
idx_t idx_t idx_t idx_t idx_t idx_t * adjwgt
#define Setup2WayBalMultipliers
idx_t idx_t idx_t idx_t idx_t * vsize
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.
#define Change2CNumbering
idx_t idx_t idx_t idx_t idx_t idx_t idx_t real_t * tpwgts
idx_t idx_t idx_t * adjncy
#define AllocateWorkSpace
#define IFSET(a, flag, cmd)
#define Change2FNumbering
#define Init2WayPartition
void SplitGraphPart(ctrl_t *ctrl, graph_t *graph, graph_t **r_lgraph, graph_t **r_rgraph)
idx_t idx_t idx_t idx_t idx_t idx_t idx_t * nparts
#define Compute2WayPartitionParams
#define gk_startcputimer(tmr)
static const Line3 l(Rot3(), 1, 1)
idx_t idx_t idx_t idx_t * vwgt
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 ASSERT(expression)
idx_t MlevelRecursiveBisection(ctrl_t *ctrl, graph_t *graph, idx_t nparts, idx_t *part, real_t *tpwgts, idx_t fpart)
idx_t MultilevelBisect(ctrl_t *ctrl, graph_t *graph, real_t *tpwgts)
idx_t idx_t idx_t idx_t * where
NonlinearFactorGraph graph
#define gk_stopcputimer(tmr)
void gk_malloc_cleanup(int showstats)
#define ComputeLoadImbalanceDiff
gtsam
Author(s):
autogenerated on Fri Nov 1 2024 03:34:23