/*
* 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 10592 2011-07-16 21:17:53Z karypis $
*/
/*************************************************************************/
/*! 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 key-key-value triplets
**************************************************************************/
typedef struct i2kv_t {
idx_t key1, key2;
idx_t val;
} i2kv_t;
/*************************************************************************
* The following data structure 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;
/*************************************************************************
* The following data structure holds information on degrees for k-way
* partition
**************************************************************************/
struct nrinfodef {
idx_t edegrees[2];
};
typedef struct nrinfodef NRInfoType;
/*************************************************************************
* The following data structure stores a sparse matrix in CSR format
* The diagonal entry is in the first position of each row.
**************************************************************************/
typedef struct matrix_t {
idx_t nrows, nnzs; /* Number of rows and nonzeros in the matrix */
idx_t *rowptr;
idx_t *colind;
real_t *values;
real_t *transfer;
} matrix_t;
/*************************************************************************
* This data structure holds the input graph
**************************************************************************/
typedef struct graph_t {
idx_t gnvtxs, nvtxs, nedges, ncon, nobj;
idx_t *xadj; /* Pointers to the locally stored vertices */
idx_t *vwgt; /* Vertex weights */
real_t *nvwgt; /* Vertex weights */
idx_t *vsize; /* Vertex size */
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 *vtxdist; /* Distribution of vertices */
idx_t *home; /* The initial partition of the vertex */
/* used for not freeing application supplied arrays */
idx_t free_vwgt;
idx_t free_adjwgt;
idx_t free_vsize;
/* Coarsening structures */
idx_t *match;
idx_t *cmap;
/* Used during initial partitioning */
idx_t *label;
/* Communication/Setup parameters */
idx_t nnbrs; /*!< The number of neighboring processors */
idx_t nrecv; /*!< The total number of remote vertices that need to
be received. nrecv == recvptr[nnbrs] */
idx_t nsend; /*!< The total number of local vertices that need to
be sent. This corresponds to the communication
volume of each pe, in the sense that if a vertex
needs to be sent multiple times, it is accounted
in nsend. nsend == sendptr[nnbrs] */
idx_t *peind; /*!< Array of size nnbrs storing the neighboring PEs */
idx_t *sendptr, *sendind; /*!< CSR format of the vertices that are sent to each
of the neighboring processors */
idx_t *recvptr, *recvind; /*!< CSR format of the vertices that are received from
each of the neighboring PEs. */
idx_t *imap; /*!< The inverse map of local to global indices */
idx_t *pexadj, *peadjncy,
*peadjloc; /*!< CSR format of the PEs each vertex is adjancent to
along with the location in the sendind of the
non-local adjancent vertices */
idx_t nlocal; /*!< Number of interior vertices */
idx_t *lperm; /*!< lperm[0:nlocal] points to interior vertices,
the rest are interface */
/* Communication parameters for projecting the partition.
* These are computed during CreateCoarseGraph and used during projection
* Note that during projection, the meaning of received and sent is reversed! */
idx_t *rlens, *slens; /* Arrays of size nnbrs of how many vertices you are sending and receiving */
ikv_t *rcand;
/* Partition parameters */
idx_t *where;
idx_t *lpwgts, *gpwgts;
real_t *lnpwgts, *gnpwgts;
ckrinfo_t *ckrinfo;
/* Node refinement information */
idx_t nsep; /* The number of vertices in the separator */
NRInfoType *nrinfo;
idx_t *sepind; /* The indices of the vertices in the separator */
idx_t lmincut, mincut;
idx_t level;
idx_t match_type;
idx_t edgewgt_type;
struct graph_t *coarser, *finer;
} graph_t;
/*************************************************************************
* The following data type implements a timer
**************************************************************************/
typedef double timer;
/*************************************************************************
* The following structure stores information used by parallel kmetis
**************************************************************************/
typedef struct ctrl_t {
pmoptype_et optype; /*!< The operation being performed */
idx_t mype, npes; /* Info about the parallel system */
idx_t ncon; /*!< The number of balancing constraints */
idx_t CoarsenTo; /* The # of vertices in the coarsest graph */
idx_t dbglvl; /* Controls the debuging output of the program */
idx_t nparts; /* The number of partitions */
idx_t foldf; /* What is the folding factor */
idx_t mtype; /* The matching type */
idx_t ipart; /* The initial partitioning type */
idx_t rtype; /* The refinement type */
idx_t p_nseps; /* The number of separators to compute at each
parallel bisection */
idx_t s_nseps; /* The number of separators to compute at each
serial bisection */
real_t ubfrac; /* The max/avg fraction for separator bisections */
idx_t seed; /* Random number seed */
idx_t sync; /* Random number seed */
real_t *tpwgts; /* Target subdomain weights */
real_t *invtvwgts; /* Per-constraint 1/total vertex weight */
real_t *ubvec; /* Per-constraint unbalance factor */
idx_t partType;
idx_t ps_relation;
real_t redist_factor;
real_t redist_base;
real_t ipc_factor;
real_t edge_size_ratio;
matrix_t *matrix;
idx_t free_comm; /*!< Used to indicate if gcomm needs to be freed */
MPI_Comm gcomm; /*!< A copy of the application supplied communicator */
MPI_Comm comm; /*!< The current communicator */
idx_t ncommpes; /*!< The maximum number of processors that a processor
may need to communicate with. This determines the
size of the sreq/rreq/statuses arrays and is
updated after every call to CommSetup() */
MPI_Request *sreq; /*!< MPI send requests */
MPI_Request *rreq; /*!< MPI receive requests */
MPI_Status *statuses; /*!< MPI status for p2p i-messages */
MPI_Status status;
/* workspace variables */
gk_mcore_t *mcore; /* GKlib's mcore */
/* These are for use by the k-way refinement routines */
size_t nbrpoolsize; /*!< The number of cnbr_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 */
/* Various Timers */
timer TotalTmr, InitPartTmr, MatchTmr, ContractTmr, CoarsenTmr, RefTmr,
SetupTmr, ProjectTmr, KWayInitTmr, KWayTmr, MoveTmr, RemapTmr,
SerialTmr, AuxTmr1, AuxTmr2, AuxTmr3, AuxTmr4, AuxTmr5, AuxTmr6;
} ctrl_t;
/*************************************************************************
* The following data structure stores a mesh.
**************************************************************************/
typedef struct mesh_t {
idx_t etype;
idx_t gnelms, gnns;
idx_t nelms, nns;
idx_t ncon;
idx_t esize, gminnode;
idx_t *elmdist;
idx_t *elements;
idx_t *elmwgt;
} mesh_t;