1 /* 2 * Copyright 1997, Regents of the University of Minnesota 3 * 4 * struct.h 5 * 6 * This file contains data structures for ILU routines. 7 * 8 * Started 9/26/95 9 * George 10 * 11 * $Id: struct.h 13900 2013-03-24 15:27:07Z karypis $ 12 */ 13 14 #ifndef _LIBMETIS_STRUCT_H_ 15 #define _LIBMETIS_STRUCT_H_ 16 17 18 19 /*************************************************************************/ 20 /*! This data structure stores cut-based k-way refinement info about an 21 adjacent subdomain for a given vertex. */ 22 /*************************************************************************/ 23 typedef struct cnbr_t { 24 idx_t pid; /*!< The partition ID */ 25 idx_t ed; /*!< The sum of the weights of the adjacent edges 26 that are incident on pid */ 27 } cnbr_t; 28 29 30 /*************************************************************************/ 31 /*! The following data structure stores holds information on degrees for k-way 32 partition */ 33 /*************************************************************************/ 34 typedef struct ckrinfo_t { 35 idx_t id; /*!< The internal degree of a vertex (sum of weights) */ 36 idx_t ed; /*!< The total external degree of a vertex */ 37 idx_t nnbrs; /*!< The number of neighboring subdomains */ 38 idx_t inbr; /*!< The index in the cnbr_t array where the nnbrs list 39 of neighbors is stored */ 40 } ckrinfo_t; 41 42 43 /*************************************************************************/ 44 /*! This data structure stores volume-based k-way refinement info about an 45 adjacent subdomain for a given vertex. */ 46 /*************************************************************************/ 47 typedef struct vnbr_t { 48 idx_t pid; /*!< The partition ID */ 49 idx_t ned; /*!< The number of the adjacent edges 50 that are incident on pid */ 51 idx_t gv; /*!< The gain in volume achieved by moving the 52 vertex to pid */ 53 } vnbr_t; 54 55 56 /*************************************************************************/ 57 /*! The following data structure holds information on degrees for k-way 58 vol-based partition */ 59 /*************************************************************************/ 60 typedef struct vkrinfo_t { 61 idx_t nid; /*!< The internal degree of a vertex (count of edges) */ 62 idx_t ned; /*!< The total external degree of a vertex (count of edges) */ 63 idx_t gv; /*!< The volume gain of moving that vertex */ 64 idx_t nnbrs; /*!< The number of neighboring subdomains */ 65 idx_t inbr; /*!< The index in the vnbr_t array where the nnbrs list 66 of neighbors is stored */ 67 } vkrinfo_t; 68 69 70 /*************************************************************************/ 71 /*! The following data structure holds information on degrees for k-way 72 partition */ 73 /*************************************************************************/ 74 typedef struct nrinfo_t { 75 idx_t edegrees[2]; 76 } nrinfo_t; 77 78 79 /*************************************************************************/ 80 /*! This data structure holds a graph */ 81 /*************************************************************************/ 82 typedef struct graph_t { 83 idx_t nvtxs, nedges; /* The # of vertices and edges in the graph */ 84 idx_t ncon; /* The # of constrains */ 85 idx_t *xadj; /* Pointers to the locally stored vertices */ 86 idx_t *vwgt; /* Vertex weights */ 87 idx_t *vsize; /* Vertex sizes for min-volume formulation */ 88 idx_t *adjncy; /* Array that stores the adjacency lists of nvtxs */ 89 idx_t *adjwgt; /* Array that stores the weights of the adjacency lists */ 90 91 idx_t *tvwgt; /* The sum of the vertex weights in the graph */ 92 real_t *invtvwgt; /* The inverse of the sum of the vertex weights in the graph */ 93 94 95 /* These are to keep track control if the corresponding fields correspond to 96 application or library memory */ 97 int free_xadj, free_vwgt, free_vsize, free_adjncy, free_adjwgt; 98 99 idx_t *label; 100 101 idx_t *cmap; 102 103 /* Partition parameters */ 104 idx_t mincut, minvol; 105 idx_t *where, *pwgts; 106 idx_t nbnd; 107 idx_t *bndptr, *bndind; 108 109 /* Bisection refinement parameters */ 110 idx_t *id, *ed; 111 112 /* K-way refinement parameters */ 113 ckrinfo_t *ckrinfo; /*!< The per-vertex cut-based refinement info */ 114 vkrinfo_t *vkrinfo; /*!< The per-vertex volume-based refinement info */ 115 116 /* Node refinement information */ 117 nrinfo_t *nrinfo; 118 119 struct graph_t *coarser, *finer; 120 } graph_t; 121 122 123 /*************************************************************************/ 124 /*! This data structure holds a mesh */ 125 /*************************************************************************/ 126 typedef struct mesh_t { 127 idx_t ne, nn; /*!< The # of elements and nodes in the mesh */ 128 idx_t ncon; /*!< The number of element balancing constraints (element weights) */ 129 130 idx_t *eptr, *eind; /*!< The CSR-structure storing the nodes in the elements */ 131 idx_t *ewgt; /*!< The weights of the elements */ 132 } mesh_t; 133 134 135 136 /*************************************************************************/ 137 /*! The following structure stores information used by Metis */ 138 /*************************************************************************/ 139 typedef struct ctrl_t { 140 moptype_et optype; /* Type of operation */ 141 mobjtype_et objtype; /* Type of refinement objective */ 142 mdbglvl_et dbglvl; /* Controls the debuging output of the program */ 143 mctype_et ctype; /* The type of coarsening */ 144 miptype_et iptype; /* The type of initial partitioning */ 145 mrtype_et rtype; /* The type of refinement */ 146 147 idx_t CoarsenTo; /* The # of vertices in the coarsest graph */ 148 idx_t nIparts; /* The number of initial partitions to compute */ 149 idx_t no2hop; /* Indicates if 2-hop matching will be used */ 150 idx_t minconn; /* Indicates if the subdomain connectivity will be minimized */ 151 idx_t contig; /* Indicates if contigous partitions are required */ 152 idx_t nseps; /* The number of separators to be found during multiple bisections */ 153 idx_t ufactor; /* The user-supplied load imbalance factor */ 154 idx_t compress; /* If the graph will be compressed prior to ordering */ 155 idx_t ccorder; /* If connected components will be ordered separately */ 156 idx_t seed; /* The seed for the random number generator */ 157 idx_t ncuts; /* The number of different partitionings to compute */ 158 idx_t niter; /* The number of iterations during each refinement */ 159 idx_t numflag; /* The user-supplied numflag for the graph */ 160 idx_t *maxvwgt; /* The maximum allowed weight for a vertex */ 161 162 idx_t ncon; /*!< The number of balancing constraints */ 163 idx_t nparts; /*!< The number of partitions */ 164 165 real_t pfactor; /* .1*(user-supplied prunning factor) */ 166 167 real_t *ubfactors; /*!< The per-constraint ubfactors */ 168 169 real_t *tpwgts; /*!< The target partition weights */ 170 real_t *pijbm; /*!< The nparts*ncon multiplies for the ith partition 171 and jth constraint for obtaining the balance */ 172 173 real_t cfactor; /*!< The achieved compression factor */ 174 175 /* Various Timers */ 176 double TotalTmr, InitPartTmr, MatchTmr, ContractTmr, CoarsenTmr, UncoarsenTmr, 177 RefTmr, ProjectTmr, SplitTmr, Aux1Tmr, Aux2Tmr, Aux3Tmr; 178 179 /* Workspace information */ 180 gk_mcore_t *mcore; /*!< The persistent memory core for within function 181 mallocs/frees */ 182 183 /* These are for use by the k-way refinement routines */ 184 size_t nbrpoolsize; /*!< The number of {c,v}nbr_t entries that have been allocated */ 185 size_t nbrpoolcpos; /*!< The position of the first free entry in the array */ 186 size_t nbrpoolreallocs; /*!< The number of times the pool was resized */ 187 188 cnbr_t *cnbrpool; /*!< The pool of cnbr_t entries to be used during refinement. 189 The size and current position of the pool is controlled 190 by nnbrs & cnbrs */ 191 vnbr_t *vnbrpool; /*!< The pool of vnbr_t entries to be used during refinement. 192 The size and current position of the pool is controlled 193 by nnbrs & cnbrs */ 194 195 /* The subdomain graph, in sparse format */ 196 idx_t *maxnads; /* The maximum allocated number of adjacent domains */ 197 idx_t *nads; /* The number of adjacent domains */ 198 idx_t **adids; /* The IDs of the adjacent domains */ 199 idx_t **adwgts; /* The edge-weight to the adjacent domains */ 200 idx_t *pvec1, *pvec2; /* Auxiliar nparts-size vectors for efficiency */ 201 202 } ctrl_t; 203 204 205 206 #endif 207