Cloned library METIS with extra build files for internal package management.
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 
 

541 lines
18 KiB

/**
\file
\brief This file contains various routines for dealing with options and ctrl_t.
\date Started 5/12/2011
\author George
\author Copyright 1997-2011, Regents of the University of Minnesota
\version\verbatim $Id: options.c 17717 2014-10-03 19:09:31Z dominique $ \endverbatim
*/
#include "metislib.h"
/*************************************************************************/
/*! This function creates and sets the run parameters (ctrl_t) */
/*************************************************************************/
ctrl_t *SetupCtrl(moptype_et optype, idx_t *options, idx_t ncon, idx_t nparts,
real_t *tpwgts, real_t *ubvec)
{
idx_t i, j;
ctrl_t *ctrl;
ctrl = (ctrl_t *)gk_malloc(sizeof(ctrl_t), "SetupCtrl: ctrl");
memset((void *)ctrl, 0, sizeof(ctrl_t));
ctrl->pid = getpid();
switch (optype) {
case METIS_OP_PMETIS:
ctrl->objtype = GETOPTION(options, METIS_OPTION_OBJTYPE, METIS_OBJTYPE_CUT);
ctrl->rtype = METIS_RTYPE_FM;
ctrl->ncuts = GETOPTION(options, METIS_OPTION_NCUTS, 1);
ctrl->niter = GETOPTION(options, METIS_OPTION_NITER, 10);
if (ncon == 1) {
ctrl->iptype = GETOPTION(options, METIS_OPTION_IPTYPE, METIS_IPTYPE_GROW);
ctrl->ufactor = GETOPTION(options, METIS_OPTION_UFACTOR, PMETIS_DEFAULT_UFACTOR);
ctrl->CoarsenTo = 20;
}
else {
ctrl->iptype = GETOPTION(options, METIS_OPTION_IPTYPE, METIS_IPTYPE_RANDOM);
ctrl->ufactor = GETOPTION(options, METIS_OPTION_UFACTOR, MCPMETIS_DEFAULT_UFACTOR);
ctrl->CoarsenTo = 100;
}
break;
case METIS_OP_KMETIS:
ctrl->objtype = GETOPTION(options, METIS_OPTION_OBJTYPE, METIS_OBJTYPE_CUT);
ctrl->iptype = GETOPTION(options, METIS_OPTION_IPTYPE, METIS_IPTYPE_METISRB);
ctrl->rtype = METIS_RTYPE_GREEDY;
ctrl->nIparts = GETOPTION(options, METIS_OPTION_NIPARTS, -1);
ctrl->ncuts = GETOPTION(options, METIS_OPTION_NCUTS, 1);
ctrl->niter = GETOPTION(options, METIS_OPTION_NITER, 10);
ctrl->ufactor = GETOPTION(options, METIS_OPTION_UFACTOR, KMETIS_DEFAULT_UFACTOR);
ctrl->minconn = GETOPTION(options, METIS_OPTION_MINCONN, 0);
ctrl->contig = GETOPTION(options, METIS_OPTION_CONTIG, 0);
break;
case METIS_OP_OMETIS:
ctrl->objtype = GETOPTION(options, METIS_OPTION_OBJTYPE, METIS_OBJTYPE_NODE);
ctrl->rtype = GETOPTION(options, METIS_OPTION_RTYPE, METIS_RTYPE_SEP1SIDED);
ctrl->iptype = GETOPTION(options, METIS_OPTION_IPTYPE, METIS_IPTYPE_EDGE);
ctrl->nseps = GETOPTION(options, METIS_OPTION_NSEPS, 1);
ctrl->niter = GETOPTION(options, METIS_OPTION_NITER, 10);
ctrl->ufactor = GETOPTION(options, METIS_OPTION_UFACTOR, OMETIS_DEFAULT_UFACTOR);
ctrl->compress = GETOPTION(options, METIS_OPTION_COMPRESS, 1);
ctrl->ccorder = GETOPTION(options, METIS_OPTION_CCORDER, 0);
ctrl->pfactor = 0.1*GETOPTION(options, METIS_OPTION_PFACTOR, 0);
ctrl->CoarsenTo = 100;
break;
default:
gk_errexit(SIGERR, "Unknown optype of %d\n", optype);
}
/* common options */
ctrl->ctype = GETOPTION(options, METIS_OPTION_CTYPE, METIS_CTYPE_SHEM);
ctrl->no2hop = GETOPTION(options, METIS_OPTION_NO2HOP, 0);
ctrl->ondisk = GETOPTION(options, METIS_OPTION_ONDISK, 0);
ctrl->seed = GETOPTION(options, METIS_OPTION_SEED, -1);
ctrl->dbglvl = GETOPTION(options, METIS_OPTION_DBGLVL, 0);
ctrl->numflag = GETOPTION(options, METIS_OPTION_NUMBERING, 0);
ctrl->dropedges = GETOPTION(options, METIS_OPTION_DROPEDGES, 0);
/* set non-option information */
ctrl->optype = optype;
ctrl->ncon = ncon;
ctrl->nparts = nparts;
ctrl->maxvwgt = ismalloc(ncon, 0, "SetupCtrl: maxvwgt");
/* setup the target partition weights */
if (ctrl->optype != METIS_OP_OMETIS) {
ctrl->tpwgts = rsmalloc(nparts*ncon, 0.0, "SetupCtrl: ctrl->tpwgts");
if (tpwgts) {
rcopy(nparts*ncon, tpwgts, ctrl->tpwgts);
}
else {
for (i=0; i<nparts; i++) {
for (j=0; j<ncon; j++)
ctrl->tpwgts[i*ncon+j] = 1.0/nparts;
}
}
}
else { /* METIS_OP_OMETIS */
/* this is required to allow the pijbm to be defined properly for
the edge-based refinement during initial partitioning */
ctrl->tpwgts = rsmalloc(2, .5, "SetupCtrl: ctrl->tpwgts");
}
/* setup the ubfactors */
ctrl->ubfactors = rsmalloc(ctrl->ncon, I2RUBFACTOR(ctrl->ufactor), "SetupCtrl: ubfactors");
if (ubvec)
rcopy(ctrl->ncon, ubvec, ctrl->ubfactors);
for (i=0; i<ctrl->ncon; i++)
ctrl->ubfactors[i] += 0.0000499;
/* Allocate memory for balance multipliers.
Note that for PMETIS/OMETIS routines the memory allocated is more
than required as balance multipliers for 2 parts is sufficient. */
ctrl->pijbm = rmalloc(nparts*ncon, "SetupCtrl: ctrl->pijbm");
InitRandom(ctrl->seed);
IFSET(ctrl->dbglvl, METIS_DBG_INFO, PrintCtrl(ctrl));
if (!CheckParams(ctrl)) {
FreeCtrl(&ctrl);
return NULL;
}
else {
return ctrl;
}
}
/*************************************************************************/
/*! Computes the per-partition/constraint balance multipliers */
/*************************************************************************/
void SetupKWayBalMultipliers(ctrl_t *ctrl, graph_t *graph)
{
idx_t i, j;
for (i=0; i<ctrl->nparts; i++) {
for (j=0; j<graph->ncon; j++)
ctrl->pijbm[i*graph->ncon+j] = graph->invtvwgt[j]/ctrl->tpwgts[i*graph->ncon+j];
}
}
/*************************************************************************/
/*! Computes the per-partition/constraint balance multipliers */
/*************************************************************************/
void Setup2WayBalMultipliers(ctrl_t *ctrl, graph_t *graph, real_t *tpwgts)
{
idx_t i, j;
for (i=0; i<2; i++) {
for (j=0; j<graph->ncon; j++)
ctrl->pijbm[i*graph->ncon+j] = graph->invtvwgt[j]/tpwgts[i*graph->ncon+j];
}
}
/*************************************************************************/
/*! This function prints the various control fields */
/*************************************************************************/
void PrintCtrl(ctrl_t *ctrl)
{
idx_t i, j, modnum;
printf(" Runtime parameters:\n");
printf(" Objective type: ");
switch (ctrl->objtype) {
case METIS_OBJTYPE_CUT:
printf("METIS_OBJTYPE_CUT\n");
break;
case METIS_OBJTYPE_VOL:
printf("METIS_OBJTYPE_VOL\n");
break;
case METIS_OBJTYPE_NODE:
printf("METIS_OBJTYPE_NODE\n");
break;
default:
printf("Unknown!\n");
}
printf(" Coarsening type: ");
switch (ctrl->ctype) {
case METIS_CTYPE_RM:
printf("METIS_CTYPE_RM\n");
break;
case METIS_CTYPE_SHEM:
printf("METIS_CTYPE_SHEM\n");
break;
default:
printf("Unknown!\n");
}
printf(" Initial partitioning type: ");
switch (ctrl->iptype) {
case METIS_IPTYPE_GROW:
printf("METIS_IPTYPE_GROW\n");
break;
case METIS_IPTYPE_RANDOM:
printf("METIS_IPTYPE_RANDOM\n");
break;
case METIS_IPTYPE_EDGE:
printf("METIS_IPTYPE_EDGE\n");
break;
case METIS_IPTYPE_NODE:
printf("METIS_IPTYPE_NODE\n");
break;
case METIS_IPTYPE_METISRB:
printf("METIS_IPTYPE_METISRB\n");
break;
default:
printf("Unknown!\n");
}
printf(" Refinement type: ");
switch (ctrl->rtype) {
case METIS_RTYPE_FM:
printf("METIS_RTYPE_FM\n");
break;
case METIS_RTYPE_GREEDY:
printf("METIS_RTYPE_GREEDY\n");
break;
case METIS_RTYPE_SEP2SIDED:
printf("METIS_RTYPE_SEP2SIDED\n");
break;
case METIS_RTYPE_SEP1SIDED:
printf("METIS_RTYPE_SEP1SIDED\n");
break;
default:
printf("Unknown!\n");
}
printf(" Perform a 2-hop matching: %s\n", (ctrl->no2hop ? "No" : "Yes"));
printf(" On disk storage: %s\n", (ctrl->ondisk ? "Yes" : "No"));
printf(" Drop edges: %s\n", (ctrl->dropedges ? "Yes" : "No"));
printf(" Number of balancing constraints: %"PRIDX"\n", ctrl->ncon);
printf(" Number of refinement iterations: %"PRIDX"\n", ctrl->niter);
printf(" Number of initial partitionings: %"PRIDX"\n", ctrl->nIparts);
printf(" Random number seed: %"PRIDX"\n", ctrl->seed);
if (ctrl->optype == METIS_OP_OMETIS) {
printf(" Number of separators: %"PRIDX"\n", ctrl->nseps);
printf(" Compress graph prior to ordering: %s\n", (ctrl->compress ? "Yes" : "No"));
printf(" Detect & order connected components separately: %s\n", (ctrl->ccorder ? "Yes" : "No"));
printf(" Prunning factor for high degree vertices: %"PRREAL"\n", ctrl->pfactor);
}
else {
printf(" Number of partitions: %"PRIDX"\n", ctrl->nparts);
printf(" Number of cuts: %"PRIDX"\n", ctrl->ncuts);
printf(" User-supplied ufactor: %"PRIDX"\n", ctrl->ufactor);
if (ctrl->optype == METIS_OP_KMETIS) {
printf(" Minimize connectivity: %s\n", (ctrl->minconn ? "Yes" : "No"));
printf(" Create contiguous partitions: %s\n", (ctrl->contig ? "Yes" : "No"));
}
modnum = (ctrl->ncon==1 ? 5 : (ctrl->ncon==2 ? 3 : (ctrl->ncon==3 ? 2 : 1)));
printf(" Target partition weights: ");
for (i=0; i<ctrl->nparts; i++) {
if (i%modnum == 0)
printf("\n ");
printf("%4"PRIDX"=[", i);
for (j=0; j<ctrl->ncon; j++)
printf("%s%.2e", (j==0 ? "" : " "), (double)ctrl->tpwgts[i*ctrl->ncon+j]);
printf("]");
}
printf("\n");
}
printf(" Allowed maximum load imbalance: ");
for (i=0; i<ctrl->ncon; i++)
printf("%.3"PRREAL" ", ctrl->ubfactors[i]);
printf("\n");
printf("\n");
}
/*************************************************************************/
/*! This function checks the validity of user-supplied parameters */
/*************************************************************************/
int CheckParams(ctrl_t *ctrl)
{
idx_t i, j;
real_t sum;
mdbglvl_et dbglvl=METIS_DBG_INFO;
switch (ctrl->optype) {
case METIS_OP_PMETIS:
if (ctrl->objtype != METIS_OBJTYPE_CUT) {
IFSET(dbglvl, METIS_DBG_INFO, printf("Input Error: Incorrect objective type.\n"));
return 0;
}
if (ctrl->ctype != METIS_CTYPE_RM && ctrl->ctype != METIS_CTYPE_SHEM) {
IFSET(dbglvl, METIS_DBG_INFO, printf("Input Error: Incorrect coarsening scheme.\n"));
return 0;
}
if (ctrl->iptype != METIS_IPTYPE_GROW && ctrl->iptype != METIS_IPTYPE_RANDOM) {
IFSET(dbglvl, METIS_DBG_INFO, printf("Input Error: Incorrect initial partitioning scheme.\n"));
return 0;
}
if (ctrl->rtype != METIS_RTYPE_FM) {
IFSET(dbglvl, METIS_DBG_INFO, printf("Input Error: Incorrect refinement scheme.\n"));
return 0;
}
if (ctrl->ncuts <= 0) {
IFSET(dbglvl, METIS_DBG_INFO, printf("Input Error: Incorrect ncuts.\n"));
return 0;
}
if (ctrl->niter <= 0) {
IFSET(dbglvl, METIS_DBG_INFO, printf("Input Error: Incorrect niter.\n"));
return 0;
}
if (ctrl->ufactor <= 0) {
IFSET(dbglvl, METIS_DBG_INFO, printf("Input Error: Incorrect ufactor.\n"));
return 0;
}
if (ctrl->numflag != 0 && ctrl->numflag != 1) {
IFSET(dbglvl, METIS_DBG_INFO, printf("Input Error: Incorrect numflag.\n"));
return 0;
}
if (ctrl->nparts <= 0) {
IFSET(dbglvl, METIS_DBG_INFO, printf("Input Error: Incorrect nparts.\n"));
return 0;
}
if (ctrl->ncon <= 0) {
IFSET(dbglvl, METIS_DBG_INFO, printf("Input Error: Incorrect ncon.\n"));
return 0;
}
for (i=0; i<ctrl->ncon; i++) {
sum = rsum(ctrl->nparts, ctrl->tpwgts+i, ctrl->ncon);
if (sum < 0.99 || sum > 1.01) {
IFSET(dbglvl, METIS_DBG_INFO,
printf("Input Error: Incorrect sum of %"PRREAL" for tpwgts for constraint %"PRIDX".\n", sum, i));
return 0;
}
}
for (i=0; i<ctrl->ncon; i++) {
for (j=0; j<ctrl->nparts; j++) {
if (ctrl->tpwgts[j*ctrl->ncon+i] <= 0.0) {
IFSET(dbglvl, METIS_DBG_INFO,
printf("Input Error: Incorrect tpwgts for partition %"PRIDX" and constraint %"PRIDX".\n", j, i));
return 0;
}
}
}
for (i=0; i<ctrl->ncon; i++) {
if (ctrl->ubfactors[i] <= 1.0) {
IFSET(dbglvl, METIS_DBG_INFO,
printf("Input Error: Incorrect ubfactor for constraint %"PRIDX".\n", i));
return 0;
}
}
break;
case METIS_OP_KMETIS:
if (ctrl->objtype != METIS_OBJTYPE_CUT && ctrl->objtype != METIS_OBJTYPE_VOL) {
IFSET(dbglvl, METIS_DBG_INFO, printf("Input Error: Incorrect objective type.\n"));
return 0;
}
if (ctrl->ctype != METIS_CTYPE_RM && ctrl->ctype != METIS_CTYPE_SHEM) {
IFSET(dbglvl, METIS_DBG_INFO, printf("Input Error: Incorrect coarsening scheme.\n"));
return 0;
}
if (ctrl->iptype != METIS_IPTYPE_METISRB && ctrl->iptype != METIS_IPTYPE_GROW) {
IFSET(dbglvl, METIS_DBG_INFO, printf("Input Error: Incorrect initial partitioning scheme.\n"));
return 0;
}
if (ctrl->rtype != METIS_RTYPE_GREEDY) {
IFSET(dbglvl, METIS_DBG_INFO, printf("Input Error: Incorrect refinement scheme.\n"));
return 0;
}
if (ctrl->ncuts <= 0) {
IFSET(dbglvl, METIS_DBG_INFO, printf("Input Error: Incorrect ncuts.\n"));
return 0;
}
if (ctrl->niter <= 0) {
IFSET(dbglvl, METIS_DBG_INFO, printf("Input Error: Incorrect niter.\n"));
return 0;
}
if (ctrl->ufactor <= 0) {
IFSET(dbglvl, METIS_DBG_INFO, printf("Input Error: Incorrect ufactor.\n"));
return 0;
}
if (ctrl->numflag != 0 && ctrl->numflag != 1) {
IFSET(dbglvl, METIS_DBG_INFO, printf("Input Error: Incorrect numflag.\n"));
return 0;
}
if (ctrl->nparts <= 0) {
IFSET(dbglvl, METIS_DBG_INFO, printf("Input Error: Incorrect nparts.\n"));
return 0;
}
if (ctrl->ncon <= 0) {
IFSET(dbglvl, METIS_DBG_INFO, printf("Input Error: Incorrect ncon.\n"));
return 0;
}
if (ctrl->contig != 0 && ctrl->contig != 1) {
IFSET(dbglvl, METIS_DBG_INFO, printf("Input Error: Incorrect contig.\n"));
return 0;
}
if (ctrl->minconn != 0 && ctrl->minconn != 1) {
IFSET(dbglvl, METIS_DBG_INFO, printf("Input Error: Incorrect minconn.\n"));
return 0;
}
for (i=0; i<ctrl->ncon; i++) {
sum = rsum(ctrl->nparts, ctrl->tpwgts+i, ctrl->ncon);
if (sum < 0.99 || sum > 1.01) {
IFSET(dbglvl, METIS_DBG_INFO,
printf("Input Error: Incorrect sum of %"PRREAL" for tpwgts for constraint %"PRIDX".\n", sum, i));
return 0;
}
}
for (i=0; i<ctrl->ncon; i++) {
for (j=0; j<ctrl->nparts; j++) {
if (ctrl->tpwgts[j*ctrl->ncon+i] <= 0.0) {
IFSET(dbglvl, METIS_DBG_INFO,
printf("Input Error: Incorrect tpwgts for partition %"PRIDX" and constraint %"PRIDX".\n", j, i));
return 0;
}
}
}
for (i=0; i<ctrl->ncon; i++) {
if (ctrl->ubfactors[i] <= 1.0) {
IFSET(dbglvl, METIS_DBG_INFO,
printf("Input Error: Incorrect ubfactor for constraint %"PRIDX".\n", i));
return 0;
}
}
break;
case METIS_OP_OMETIS:
if (ctrl->objtype != METIS_OBJTYPE_NODE) {
IFSET(dbglvl, METIS_DBG_INFO, printf("Input Error: Incorrect objective type.\n"));
return 0;
}
if (ctrl->ctype != METIS_CTYPE_RM && ctrl->ctype != METIS_CTYPE_SHEM) {
IFSET(dbglvl, METIS_DBG_INFO, printf("Input Error: Incorrect coarsening scheme.\n"));
return 0;
}
if (ctrl->iptype != METIS_IPTYPE_EDGE && ctrl->iptype != METIS_IPTYPE_NODE) {
IFSET(dbglvl, METIS_DBG_INFO, printf("Input Error: Incorrect initial partitioning scheme.\n"));
return 0;
}
if (ctrl->rtype != METIS_RTYPE_SEP1SIDED && ctrl->rtype != METIS_RTYPE_SEP2SIDED) {
IFSET(dbglvl, METIS_DBG_INFO, printf("Input Error: Incorrect refinement scheme.\n"));
return 0;
}
if (ctrl->nseps <= 0) {
IFSET(dbglvl, METIS_DBG_INFO, printf("Input Error: Incorrect nseps.\n"));
return 0;
}
if (ctrl->niter <= 0) {
IFSET(dbglvl, METIS_DBG_INFO, printf("Input Error: Incorrect niter.\n"));
return 0;
}
if (ctrl->ufactor <= 0) {
IFSET(dbglvl, METIS_DBG_INFO, printf("Input Error: Incorrect ufactor.\n"));
return 0;
}
if (ctrl->numflag != 0 && ctrl->numflag != 1) {
IFSET(dbglvl, METIS_DBG_INFO, printf("Input Error: Incorrect numflag.\n"));
return 0;
}
if (ctrl->nparts != 3) {
IFSET(dbglvl, METIS_DBG_INFO, printf("Input Error: Incorrect nparts.\n"));
return 0;
}
if (ctrl->ncon != 1) {
IFSET(dbglvl, METIS_DBG_INFO, printf("Input Error: Incorrect ncon.\n"));
return 0;
}
if (ctrl->compress != 0 && ctrl->compress != 1) {
IFSET(dbglvl, METIS_DBG_INFO, printf("Input Error: Incorrect compress.\n"));
return 0;
}
if (ctrl->ccorder != 0 && ctrl->ccorder != 1) {
IFSET(dbglvl, METIS_DBG_INFO, printf("Input Error: Incorrect ccorder.\n"));
return 0;
}
if (ctrl->pfactor < 0.0 ) {
IFSET(dbglvl, METIS_DBG_INFO, printf("Input Error: Incorrect pfactor.\n"));
return 0;
}
for (i=0; i<ctrl->ncon; i++) {
if (ctrl->ubfactors[i] <= 1.0) {
IFSET(dbglvl, METIS_DBG_INFO,
printf("Input Error: Incorrect ubfactor for constraint %"PRIDX".\n", i));
return 0;
}
}
break;
default:
IFSET(dbglvl, METIS_DBG_INFO, printf("Input Error: Incorrect optype\n"));
return 0;
}
return 1;
}
/*************************************************************************/
/*! This function frees the memory associated with a ctrl_t */
/*************************************************************************/
void FreeCtrl(ctrl_t **r_ctrl)
{
ctrl_t *ctrl = *r_ctrl;
FreeWorkSpace(ctrl);
gk_free((void **)&ctrl->tpwgts, &ctrl->pijbm,
&ctrl->ubfactors, &ctrl->maxvwgt, &ctrl, LTERM);
*r_ctrl = NULL;
}