struct.h

/*
 * Copyright 1997, Regents of the University of Minnesota
 *
 * struct.h
 *
 * This file contains data structures for ILU routines.
 *
 * Started 9/26/95
 * George
 *
 * $Id: struct.h 13900 2013-03-24 15:27:07Z karypis $
 */

#ifndef _LIBMETIS_STRUCT_H_
#define _LIBMETIS_STRUCT_H_



/*************************************************************************/
/*! This data structure stores cut-based k-way refinement info about an
    adjacent subdomain for a given vertex. */
/*************************************************************************/
typedef struct cnbr_t {
  idx_t pid;            /*!< The partition ID */
  idx_t ed;             /*!< The sum of the weights of the adjacent edges
                             that are incident on pid */
} cnbr_t;


/*************************************************************************/
/*! The following data structure stores holds information on degrees for k-way
    partition */
/*************************************************************************/
typedef struct ckrinfo_t {
 idx_t id;              /*!< The internal degree of a vertex (sum of weights) */
 idx_t ed;            	/*!< The total external degree of a vertex */
 idx_t nnbrs;          	/*!< The number of neighboring subdomains */
 idx_t inbr;            /*!< The index in the cnbr_t array where the nnbrs list 
                             of neighbors is stored */
} ckrinfo_t;


/*************************************************************************/
/*! This data structure stores volume-based k-way refinement info about an
    adjacent subdomain for a given vertex. */
/*************************************************************************/
typedef struct vnbr_t {
  idx_t pid;            /*!< The partition ID */
  idx_t ned;            /*!< The number of the adjacent edges
                             that are incident on pid */
  idx_t gv;             /*!< The gain in volume achieved by moving the
                             vertex to pid */
} vnbr_t;


/*************************************************************************/
/*! The following data structure holds information on degrees for k-way
    vol-based partition */
/*************************************************************************/
typedef struct vkrinfo_t {
 idx_t nid;             /*!< The internal degree of a vertex (count of edges) */
 idx_t ned;            	/*!< The total external degree of a vertex (count of edges) */
 idx_t gv;            	/*!< The volume gain of moving that vertex */
 idx_t nnbrs;          	/*!< The number of neighboring subdomains */
 idx_t inbr;            /*!< The index in the vnbr_t array where the nnbrs list 
                             of neighbors is stored */
} vkrinfo_t;


/*************************************************************************/
/*! The following data structure holds information on degrees for k-way
    partition */
/*************************************************************************/
typedef struct nrinfo_t {
 idx_t edegrees[2];  
} nrinfo_t;


/*************************************************************************/
/*! This data structure holds a graph */
/*************************************************************************/
typedef struct graph_t {
  idx_t nvtxs, nedges;	/* The # of vertices and edges in the graph */
  idx_t ncon;		/* The # of constrains */ 
  idx_t *xadj;		/* Pointers to the locally stored vertices */
  idx_t *vwgt;		/* Vertex weights */
  idx_t *vsize;		/* Vertex sizes for min-volume formulation */
  idx_t *adjncy;        /* Array that stores the adjacency lists of nvtxs */
  idx_t *adjwgt;        /* Array that stores the weights of the adjacency lists */

  idx_t *tvwgt;         /* The sum of the vertex weights in the graph */
  real_t *invtvwgt;     /* The inverse of the sum of the vertex weights in the graph */


  /* These are to keep track control if the corresponding fields correspond to
     application or library memory */
  int free_xadj, free_vwgt, free_vsize, free_adjncy, free_adjwgt;

  idx_t *label;

  idx_t *cmap;

  /* Partition parameters */
  idx_t mincut, minvol;
  idx_t *where, *pwgts;
  idx_t nbnd;
  idx_t *bndptr, *bndind;

  /* Bisection refinement parameters */
  idx_t *id, *ed;

  /* K-way refinement parameters */
  ckrinfo_t *ckrinfo;   /*!< The per-vertex cut-based refinement info */
  vkrinfo_t *vkrinfo;   /*!< The per-vertex volume-based refinement info */

  /* Node refinement information */
  nrinfo_t *nrinfo;

  struct graph_t *coarser, *finer;
} graph_t;


/*************************************************************************/
/*! This data structure holds a mesh */
/*************************************************************************/
typedef struct mesh_t {
  idx_t ne, nn;	        /*!< The # of elements and nodes in the mesh */
  idx_t ncon;           /*!< The number of element balancing constraints (element weights) */

  idx_t *eptr, *eind;   /*!< The CSR-structure storing the nodes in the elements */
  idx_t *ewgt;          /*!< The weights of the elements */
} mesh_t;



/*************************************************************************/
/*! The following structure stores information used by Metis */
/*************************************************************************/
typedef struct ctrl_t {
  moptype_et  optype;	        /* Type of operation */
  mobjtype_et objtype;          /* Type of refinement objective */
  mdbglvl_et  dbglvl;		/* Controls the debuging output of the program */
  mctype_et   ctype;		/* The type of coarsening */
  miptype_et  iptype;		/* The type of initial partitioning */
  mrtype_et   rtype;		/* The type of refinement */

  idx_t CoarsenTo;		/* The # of vertices in the coarsest graph */
  idx_t nIparts;                /* The number of initial partitions to compute */
  idx_t no2hop;                 /* Indicates if 2-hop matching will be used */
  idx_t minconn;                /* Indicates if the subdomain connectivity will be minimized */
  idx_t contig;                 /* Indicates if contigous partitions are required */
  idx_t nseps;			/* The number of separators to be found during multiple bisections */
  idx_t ufactor;                /* The user-supplied load imbalance factor */
  idx_t compress;               /* If the graph will be compressed prior to ordering */
  idx_t ccorder;                /* If connected components will be ordered separately */
  idx_t seed;                   /* The seed for the random number generator */
  idx_t ncuts;                  /* The number of different partitionings to compute */
  idx_t niter;                  /* The number of iterations during each refinement */
  idx_t numflag;                /* The user-supplied numflag for the graph */
  idx_t *maxvwgt;		/* The maximum allowed weight for a vertex */

  idx_t ncon;                   /*!< The number of balancing constraints */
  idx_t nparts;                 /*!< The number of partitions */

  real_t pfactor;		/* .1*(user-supplied prunning factor) */

  real_t *ubfactors;            /*!< The per-constraint ubfactors */
  
  real_t *tpwgts;               /*!< The target partition weights */
  real_t *pijbm;                /*!< The nparts*ncon multiplies for the ith partition
                                     and jth constraint for obtaining the balance */

  real_t cfactor;               /*!< The achieved compression factor */

  /* Various Timers */
  double TotalTmr, InitPartTmr, MatchTmr, ContractTmr, CoarsenTmr, UncoarsenTmr, 
         RefTmr, ProjectTmr, SplitTmr, Aux1Tmr, Aux2Tmr, Aux3Tmr;

  /* Workspace information */
  gk_mcore_t *mcore;    /*!< The persistent memory core for within function 
                             mallocs/frees */

  /* These are for use by the k-way refinement routines */
  size_t nbrpoolsize;      /*!< The number of {c,v}nbr_t entries that have been allocated */
  size_t nbrpoolcpos;      /*!< The position of the first free entry in the array */
  size_t nbrpoolreallocs;  /*!< The number of times the pool was resized */

  cnbr_t *cnbrpool;     /*!< The pool of cnbr_t entries to be used during refinement.
                             The size and current position of the pool is controlled
                             by nnbrs & cnbrs */
  vnbr_t *vnbrpool;     /*!< The pool of vnbr_t entries to be used during refinement.
                             The size and current position of the pool is controlled
                             by nnbrs & cnbrs */

  /* The subdomain graph, in sparse format  */ 
  idx_t *maxnads;               /* The maximum allocated number of adjacent domains */
  idx_t *nads;                  /* The number of adjacent domains */
  idx_t **adids;                /* The IDs of the adjacent domains */
  idx_t **adwgts;               /* The edge-weight to the adjacent domains */
  idx_t *pvec1, *pvec2;         /* Auxiliar nparts-size vectors for efficiency */

} ctrl_t;



#endif