check_input.c

This toolbox contains Matlab code for several graph and mesh partitioning methods, including geometr

/* This software was developed by Bruce Hendrickson and Robert Leland   *
 * at Sandia National Laboratories under US Department of Energy        *
 * contract DE-AC04-76DP00789 and is copyrighted by Sandia Corporation. */

/* Modified by John Gilbert 10 Jul 1996 to change the call              *
 * "check_graph" to "chaco_check_graph", to avoid a Matlab name conflict*/


#include <stdio.h>
#include <math.h>
#include "params.h"
#include "defs.h"
#include "structs.h"


static int check_params(), check_assignment();

/* Check graph and input options and parameters. */
int       check_input(graph, nvtxs, nedges, igeom, coords,
		         graphname, assignment, goal,
			 architecture, ndims_tot, mesh_dims,
		         global_method, local_method, rqi_flag, vmax, ndims,
		         eigtol)
struct vtx_data **graph;	/* linked lists of vertex data */
int       nvtxs;		/* number of vertices */
int       nedges;		/* number of edges */
int       igeom;		/* geometric dimension for inertial method */
float   **coords;		/* coordinates for inertial method */
char     *graphname;		/* graph input file name */
short    *assignment;		/* set numbers if read-from-file */
double   *goal;			/* desired sizes of different sets */
int       architecture;		/* 0=> hypercube, d=> d-dimensional mesh */
int       ndims_tot;		/* number of hypercube dimensions */
int       mesh_dims[3];		/* size of mesh in each dimension */
int       global_method;	/* global partitioning algorithm */
int       local_method;		/* local partitioning algorithm */
int       rqi_flag;		/* flag for RQI/symmlq eigensolver */
int      *vmax;			/* smallest acceptable coarsened nvtxs */
int       ndims;		/* partitioning level */
double    eigtol;		/* tolerance for eigen-pairs */
{
    extern FILE *Output_File;		/* output file or null */
    extern int DEBUG_TRACE;		/* trace main execution path? */
    double    vwgt_sum, vwgt_sum2;	/* sums of values in vwgts and goals */
    int       flag;		/* does input data pass all the tests? */
    int       flag_graph;	/* does graph check out OK? */
    int       flag_params;	/* do params look OK? */
    int       flag_assign;	/* does assignment look good? */
    int       nprocs;		/* number of processors partitioning for */
    int       i;		/* loop counter */
    int       chaco_check_graph(), check_params(), check_assignment();

    if (DEBUG_TRACE > 0) {
	printf("<Entering check_input>\n");
    }

    /* First check for consistency in the graph. */
    if (graph != NULL) {
	flag_graph = chaco_check_graph(graph, nvtxs, nedges);
	if (flag_graph) {
	    if (graphname != NULL)
		printf("ERRORS in graph input file %s.\n", graphname);
		if (Output_File != NULL) {
		    fprintf(Output_File, "ERRORS in graph input file %s.\n",
			graphname);
		}
	    else
		printf("ERRORS in graph.\n");
		if (Output_File != NULL) {
		    fprintf(Output_File, "ERRORS in graph.\n");
		}
	}
    }

    else {
	/* Only allowed if simple or inertial w/o KL and no weights. */
	flag_graph = FALSE;
	if (global_method == 1 || global_method == 2 || local_method == 1) {
	    printf("No graph input.  Only allowed for inertial or simple methods without KL.\n");
	    flag_graph = TRUE;
	}
    }

    /* Now check the input values. */
    flag = FALSE;
    flag_assign = FALSE;

    if (architecture < 0 || architecture > 3) {
	printf("Machine architecture parameter = %d, must be in [0,3].\n", architecture);
	flag = TRUE;
    }

    else if (architecture == 0) {
	if (ndims_tot < 0) {
	    printf("Dimension of hypercube = %d, must be at least 1.\n", ndims_tot);
	    flag = TRUE;
	}
    }

    else if (architecture > 0) {
	if (architecture == 1 && mesh_dims[0] <= 0) {
	    printf("Size of 1-D mesh improperly specified, %d.\n", mesh_dims[0]);
	    flag = TRUE;
	}
	if (architecture == 2 && (mesh_dims[0] <= 0 || mesh_dims[1] <= 0)) {
	    printf("Size of 2-D mesh improperly specified, %dx%d.\n", mesh_dims[0], mesh_dims[1]);
	    flag = TRUE;
	}
	if (architecture == 2 && (mesh_dims[0] <= 0 || mesh_dims[1] <= 0 || mesh_dims[2] <= 0)) {
	    printf("Size of 3-D mesh improperly specified, %dx%dx%d.\n",
		   mesh_dims[0], mesh_dims[1], mesh_dims[2]);
	    flag = TRUE;
	}
    }

    if (ndims < 1 || ndims > MAXDIMS) {
	printf("Partitioning at each step = %d, should be in [1,%d].\n",
	       ndims, MAXDIMS);
	flag = TRUE;
    }

    if (architecture == 0)
	nprocs = 1 << ndims_tot;
    else if (architecture > 0)
	nprocs = mesh_dims[0] * mesh_dims[1] * mesh_dims[2];
    if (1 << ndims > nprocs) {
	printf("Partitioning step %d too large for %d processors.\n",
	       ndims, nprocs);
	flag = TRUE;
    }

    if (global_method < 1 || global_method > 7) {
	printf("Global partitioning method = %d, must be in [1,7].\n", global_method);
	flag = TRUE;
    }

    if (local_method < 1 || local_method > 2) {
	printf("Local partitioning method = %d, must be in [1,2].\n", local_method);
	flag = TRUE;
    }

    if (global_method == 1 || (global_method == 2 && rqi_flag)) {
	i = 2 * (1 << ndims);
	if (*vmax < i) {
	    printf("WARNING: Number of vertices in coarse graph (%d) being reset to %d.\n",
		   *vmax, i);
	    if (Output_File != NULL) {
	        fprintf(Output_File,
		    "WARNING: Number of vertices in coarse graph (%d) being reset to %d.\n",
		    *vmax, i);
	    }
	    *vmax = i;
	}
    }

    if ((global_method == 1 || global_method == 2) && eigtol <= 0) {
	printf("Eigen tolerance (%g) must be positive value\n", eigtol);
	flag = TRUE;
    }

    if (global_method == 3) {
	if (igeom < 1 || igeom > 3) {
	    printf("Geometry must be 1-, 2- or 3-dimensional for inertial method\n");
	    flag = TRUE;
	}
	if (igeom > 0 && coords == NULL) {
	    printf("No coordinates given for inertial method\n");
	    flag = FALSE;
	}
	else if (igeom > 0 && coords[0] == NULL) {
	    printf("No X-coordinates given for inertial method\n");
	    flag = TRUE;
	}
	else if (igeom > 1 && coords[1] == NULL) {
	    printf("No Y-coordinates given for inertial method\n");
	    flag = TRUE;
	}
	else if (igeom > 2 && coords[2] == NULL) {
	    printf("No Z-coordinates given for inertial method\n");
	    flag = TRUE;
	}
    }

    if (global_method == 7 && local_method == 1) {
	if (nprocs > 1<<ndims) {
	    printf("Can only use local method on single level of read-in assignment,\n");
	    printf("  but ndims =  %d, while number of processors = %d.\n",
		ndims, nprocs);
	    flag = TRUE;
	}
    }

    /* Now check for consistency in the goal array. */
    if (graph != NULL)  {
        vwgt_sum = 0;
        for (i = 1; i <= nvtxs; i++) {
	    vwgt_sum += graph[i]->vwgt;
	}
    }
    else {
	vwgt_sum = nvtxs;
    }

    vwgt_sum2 = 0;
    for (i = 0; i < nprocs; i++) {
	if (goal[i] < 0) {
	    printf("goal[%d] is %g, but should be nonnegative.\n", i, goal[i]);
	    flag = TRUE;
	}
	vwgt_sum2 += goal[i];
    }

    if (fabs(vwgt_sum - vwgt_sum2) > 1e-5 * (vwgt_sum + vwgt_sum2)) {
	printf("Sum of values in goal (%g) not equal to sum of vertex weights (%g).\n",
	       vwgt_sum2, vwgt_sum);
	flag = TRUE;
    }

    /* Check assignment file if read in. */
    if (global_method == 7 && !flag) {
	flag_assign = check_assignment(assignment, nvtxs, nprocs, ndims, local_method);
    }

/* Add some checks for model parameters */

    /* Finally, check the parameters. */
    flag_params = check_params(global_method, local_method, rqi_flag, ndims);

    flag = flag || flag_graph || flag_assign || flag_params;

    return (flag);
}





static int check_params(global_method, local_method, rqi_flag, ndims)
int       global_method;	/* global partitioning algorithm */
int       local_method;		/* local partitioning algorithm */
int       rqi_flag;		/* use multilevel eigensolver? */
int       ndims;		/* number of eigenvectors */
{
    extern FILE *Output_File;	/* Output file or null */
    extern int ECHO;		/* print input/param options? to file? (-2..2) */
    extern int EXPERT;		/* is user an expert? */
    extern int OUTPUT_METRICS;	/* controls formatting of output */
    extern int OUTPUT_TIME;	/* at what level to display timing */

    extern int LANCZOS_TYPE;		/* type of Lanczos to use */
    extern double EIGEN_TOLERANCE;	/* eigen-tolerance convergence criteria */