1 /* 2 * Copyright 1997, Regents of the University of Minnesota 3 * 4 * proto.h 5 * 6 * This file contains header files 7 * 8 * Started 10/19/95 9 * George 10 * 11 * $Id: proto.h 13933 2013-03-29 22:20:46Z karypis $ 12 * 13 */ 14 15 #ifndef _LIBMETIS_PROTO_H_ 16 #define _LIBMETIS_PROTO_H_ 17 18 /* auxapi.c */ 19 20 /* balance.c */ 21 void Balance2Way(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts); 22 void Bnd2WayBalance(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts); 23 void General2WayBalance(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts); 24 void McGeneral2WayBalance(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts); 25 26 27 /* bucketsort.c */ 28 void BucketSortKeysInc(ctrl_t *ctrl, idx_t n, idx_t max, idx_t *keys, 29 idx_t *tperm, idx_t *perm); 30 31 32 /* checkgraph.c */ 33 int CheckGraph(graph_t *graph, int numflag, int verbose); 34 int CheckInputGraphWeights(idx_t nvtxs, idx_t ncon, idx_t *xadj, idx_t *adjncy, 35 idx_t *vwgt, idx_t *vsize, idx_t *adjwgt); 36 graph_t *FixGraph(graph_t *graph); 37 38 39 /* coarsen.c */ 40 graph_t *CoarsenGraph(ctrl_t *ctrl, graph_t *graph); 41 graph_t *CoarsenGraphNlevels(ctrl_t *ctrl, graph_t *graph, idx_t nlevels); 42 idx_t Match_RM(ctrl_t *ctrl, graph_t *graph); 43 idx_t Match_SHEM(ctrl_t *ctrl, graph_t *graph); 44 idx_t Match_2Hop(ctrl_t *ctrl, graph_t *graph, idx_t *perm, idx_t *match, 45 idx_t cnvtxs, size_t nunmatched); 46 idx_t Match_2HopAny(ctrl_t *ctrl, graph_t *graph, idx_t *perm, idx_t *match, 47 idx_t cnvtxs, size_t *r_nunmatched, size_t maxdegree); 48 idx_t Match_2HopAll(ctrl_t *ctrl, graph_t *graph, idx_t *perm, idx_t *match, 49 idx_t cnvtxs, size_t *r_nunmatched, size_t maxdegree); 50 void PrintCGraphStats(ctrl_t *ctrl, graph_t *graph); 51 void CreateCoarseGraph(ctrl_t *ctrl, graph_t *graph, idx_t cnvtxs, 52 idx_t *match); 53 void CreateCoarseGraphNoMask(ctrl_t *ctrl, graph_t *graph, idx_t cnvtxs, 54 idx_t *match); 55 void CreateCoarseGraphPerm(ctrl_t *ctrl, graph_t *graph, idx_t cnvtxs, 56 idx_t *match, idx_t *perm); 57 graph_t *SetupCoarseGraph(graph_t *graph, idx_t cnvtxs, idx_t dovsize); 58 void ReAdjustMemory(ctrl_t *ctrl, graph_t *graph, graph_t *cgraph); 59 60 61 62 /* compress.c */ 63 graph_t *CompressGraph(ctrl_t *ctrl, idx_t nvtxs, idx_t *xadj, idx_t *adjncy, 64 idx_t *vwgt, idx_t *cptr, idx_t *cind); 65 graph_t *PruneGraph(ctrl_t *ctrl, idx_t nvtxs, idx_t *xadj, idx_t *adjncy, 66 idx_t *vwgt, idx_t *iperm, real_t factor); 67 68 69 /* contig.c */ 70 idx_t FindPartitionInducedComponents(graph_t *graph, idx_t *where, 71 idx_t *cptr, idx_t *cind); 72 void ComputeBFSOrdering(ctrl_t *ctrl, graph_t *graph, idx_t *bfsperm); 73 idx_t IsConnected(graph_t *graph, idx_t report); 74 idx_t IsConnectedSubdomain(ctrl_t *, graph_t *, idx_t, idx_t); 75 idx_t FindSepInducedComponents(ctrl_t *, graph_t *, idx_t *, idx_t *); 76 void EliminateComponents(ctrl_t *ctrl, graph_t *graph); 77 void MoveGroupContigForCut(ctrl_t *ctrl, graph_t *graph, idx_t to, idx_t gid, 78 idx_t *ptr, idx_t *ind); 79 void MoveGroupContigForVol(ctrl_t *ctrl, graph_t *graph, idx_t to, idx_t gid, 80 idx_t *ptr, idx_t *ind, idx_t *vmarker, idx_t *pmarker, 81 idx_t *modind); 82 83 84 /* debug.c */ 85 idx_t ComputeCut(graph_t *graph, idx_t *where); 86 idx_t ComputeVolume(graph_t *, idx_t *); 87 idx_t ComputeMaxCut(graph_t *graph, idx_t nparts, idx_t *where); 88 idx_t CheckBnd(graph_t *); 89 idx_t CheckBnd2(graph_t *); 90 idx_t CheckNodeBnd(graph_t *, idx_t); 91 idx_t CheckRInfo(ctrl_t *ctrl, ckrinfo_t *rinfo); 92 idx_t CheckNodePartitionParams(graph_t *); 93 idx_t IsSeparable(graph_t *); 94 void CheckKWayVolPartitionParams(ctrl_t *ctrl, graph_t *graph); 95 96 97 /* fm.c */ 98 void FM_2WayRefine(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niter); 99 void FM_2WayCutRefine(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niter); 100 void FM_Mc2WayCutRefine(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niter); 101 void SelectQueue(graph_t *graph, real_t *pijbm, real_t *ubfactors, rpq_t **queues, 102 idx_t *from, idx_t *cnum); 103 void Print2WayRefineStats(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, 104 real_t deltabal, idx_t mincutorder); 105 106 107 /* fortran.c */ 108 void Change2CNumbering(idx_t, idx_t *, idx_t *); 109 void Change2FNumbering(idx_t, idx_t *, idx_t *, idx_t *); 110 void Change2FNumbering2(idx_t, idx_t *, idx_t *); 111 void Change2FNumberingOrder(idx_t, idx_t *, idx_t *, idx_t *, idx_t *); 112 void ChangeMesh2CNumbering(idx_t n, idx_t *ptr, idx_t *ind); 113 void ChangeMesh2FNumbering(idx_t n, idx_t *ptr, idx_t *ind, idx_t nvtxs, 114 idx_t *xadj, idx_t *adjncy); 115 void ChangeMesh2FNumbering2(idx_t ne, idx_t nn, idx_t *ptr, idx_t *ind, 116 idx_t *epart, idx_t *npart); 117 118 119 /* graph.c */ 120 graph_t *SetupGraph(ctrl_t *ctrl, idx_t nvtxs, idx_t ncon, idx_t *xadj, 121 idx_t *adjncy, idx_t *vwgt, idx_t *vsize, idx_t *adjwgt); 122 void SetupGraph_tvwgt(graph_t *graph); 123 void SetupGraph_label(graph_t *graph); 124 graph_t *SetupSplitGraph(graph_t *graph, idx_t snvtxs, idx_t snedges); 125 graph_t *CreateGraph(void); 126 void InitGraph(graph_t *graph); 127 void FreeRData(graph_t *graph); 128 void FreeGraph(graph_t **graph); 129 130 131 /* initpart.c */ 132 void Init2WayPartition(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niparts); 133 void InitSeparator(ctrl_t *ctrl, graph_t *graph, idx_t niparts); 134 void RandomBisection(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niparts); 135 void GrowBisection(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niparts); 136 void McRandomBisection(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niparts); 137 void McGrowBisection(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niparts); 138 void GrowBisectionNode(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niparts); 139 void GrowBisectionNode2(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niparts); 140 141 142 /* kmetis.c */ 143 idx_t MlevelKWayPartitioning(ctrl_t *ctrl, graph_t *graph, idx_t *part); 144 void InitKWayPartitioning(ctrl_t *ctrl, graph_t *graph); 145 146 147 /* kwayfm.c */ 148 void Greedy_KWayOptimize(ctrl_t *ctrl, graph_t *graph, idx_t niter, 149 real_t ffactor, idx_t omode); 150 void Greedy_KWayCutOptimize(ctrl_t *ctrl, graph_t *graph, idx_t niter, 151 real_t ffactor, idx_t omode); 152 void Greedy_KWayVolOptimize(ctrl_t *ctrl, graph_t *graph, idx_t niter, 153 real_t ffactor, idx_t omode); 154 void Greedy_McKWayCutOptimize(ctrl_t *ctrl, graph_t *graph, idx_t niter, 155 real_t ffactor, idx_t omode); 156 void Greedy_McKWayVolOptimize(ctrl_t *ctrl, graph_t *graph, idx_t niter, 157 real_t ffactor, idx_t omode); 158 idx_t IsArticulationNode(idx_t i, idx_t *xadj, idx_t *adjncy, idx_t *where, 159 idx_t *bfslvl, idx_t *bfsind, idx_t *bfsmrk); 160 void KWayVolUpdate(ctrl_t *ctrl, graph_t *graph, idx_t v, idx_t from, 161 idx_t to, ipq_t *queue, idx_t *vstatus, idx_t *r_nupd, idx_t *updptr, 162 idx_t *updind, idx_t bndtype, idx_t *vmarker, idx_t *pmarker, 163 idx_t *modind); 164 165 166 /* kwayrefine.c */ 167 void RefineKWay(ctrl_t *ctrl, graph_t *orggraph, graph_t *graph); 168 void AllocateKWayPartitionMemory(ctrl_t *ctrl, graph_t *graph); 169 void ComputeKWayPartitionParams(ctrl_t *ctrl, graph_t *graph); 170 void ProjectKWayPartition(ctrl_t *ctrl, graph_t *graph); 171 void ComputeKWayBoundary(ctrl_t *ctrl, graph_t *graph, idx_t bndtype); 172 void ComputeKWayVolGains(ctrl_t *ctrl, graph_t *graph); 173 int IsBalanced(ctrl_t *ctrl, graph_t *graph, real_t ffactor); 174 175 176 /* mcutil.c */ 177 int rvecle(idx_t n, real_t *x, real_t *y); 178 int rvecge(idx_t n, real_t *x, real_t *y); 179 int rvecsumle(idx_t n, real_t *x1, real_t *x2, real_t *y); 180 real_t rvecmaxdiff(idx_t n, real_t *x, real_t *y); 181 int ivecle(idx_t n, idx_t *x, idx_t *z); 182 int ivecge(idx_t n, idx_t *x, idx_t *z); 183 int ivecaxpylez(idx_t n, idx_t a, idx_t *x, idx_t *y, idx_t *z); 184 int ivecaxpygez(idx_t n, idx_t a, idx_t *x, idx_t *y, idx_t *z); 185 int BetterVBalance(idx_t ncon, real_t *itvwgt, idx_t *v_vwgt, idx_t *u1_vwgt, 186 idx_t *u2_vwgt); 187 int BetterBalance2Way(idx_t n, real_t *x, real_t *y); 188 int BetterBalanceKWay(idx_t ncon, idx_t *vwgt, real_t *itvwgt, idx_t a1, 189 idx_t *pt1, real_t *bm1, idx_t a2, idx_t *pt2, real_t *bm2); 190 real_t ComputeLoadImbalance(graph_t *graph, idx_t nparts, real_t *pijbm); 191 real_t ComputeLoadImbalanceDiff(graph_t *graph, idx_t nparts, real_t *pijbm, 192 real_t *ubvec); 193 real_t ComputeLoadImbalanceDiffVec(graph_t *graph, idx_t nparts, real_t *pijbm, 194 real_t *ubfactors, real_t *diffvec); 195 void ComputeLoadImbalanceVec(graph_t *graph, idx_t nparts, real_t *pijbm, 196 real_t *lbvec); 197 198 199 /* mesh.c */ 200 void CreateGraphDual(idx_t ne, idx_t nn, idx_t *eptr, idx_t *eind, idx_t ncommon, 201 idx_t **r_xadj, idx_t **r_adjncy); 202 idx_t FindCommonElements(idx_t qid, idx_t elen, idx_t *eind, idx_t *nptr, 203 idx_t *nind, idx_t *eptr, idx_t ncommon, idx_t *marker, idx_t *nbrs); 204 void CreateGraphNodal(idx_t ne, idx_t nn, idx_t *eptr, idx_t *eind, idx_t **r_xadj, 205 idx_t **r_adjncy); 206 idx_t FindCommonNodes(idx_t qid, idx_t nelmnts, idx_t *elmntids, idx_t *eptr, 207 idx_t *eind, idx_t *marker, idx_t *nbrs); 208 mesh_t *CreateMesh(void); 209 void InitMesh(mesh_t *mesh); 210 void FreeMesh(mesh_t **mesh); 211 212 213 /* meshpart.c */ 214 void InduceRowPartFromColumnPart(idx_t nrows, idx_t *rowptr, idx_t *rowind, 215 idx_t *rpart, idx_t *cpart, idx_t nparts, real_t *tpwgts); 216 217 218 /* minconn.c */ 219 void ComputeSubDomainGraph(ctrl_t *ctrl, graph_t *graph); 220 void UpdateEdgeSubDomainGraph(ctrl_t *ctrl, idx_t u, idx_t v, idx_t ewgt, 221 idx_t *r_maxndoms); 222 void PrintSubDomainGraph(graph_t *graph, idx_t nparts, idx_t *where); 223 void EliminateSubDomainEdges(ctrl_t *ctrl, graph_t *graph); 224 void MoveGroupMinConnForCut(ctrl_t *ctrl, graph_t *graph, idx_t to, idx_t nind, 225 idx_t *ind); 226 void MoveGroupMinConnForVol(ctrl_t *ctrl, graph_t *graph, idx_t to, idx_t nind, 227 idx_t *ind, idx_t *vmarker, idx_t *pmarker, idx_t *modind); 228 229 230 /* mincover.o */ 231 void MinCover(idx_t *, idx_t *, idx_t, idx_t, idx_t *, idx_t *); 232 idx_t MinCover_Augment(idx_t *, idx_t *, idx_t, idx_t *, idx_t *, idx_t *, idx_t); 233 void MinCover_Decompose(idx_t *, idx_t *, idx_t, idx_t, idx_t *, idx_t *, idx_t *); 234 void MinCover_ColDFS(idx_t *, idx_t *, idx_t, idx_t *, idx_t *, idx_t); 235 void MinCover_RowDFS(idx_t *, idx_t *, idx_t, idx_t *, idx_t *, idx_t); 236 237 238 /* mmd.c */ 239 void genmmd(idx_t, idx_t *, idx_t *, idx_t *, idx_t *, idx_t , idx_t *, idx_t *, idx_t *, idx_t *, idx_t, idx_t *); 240 void mmdelm(idx_t, idx_t *xadj, idx_t *, idx_t *, idx_t *, idx_t *, idx_t *, idx_t *, idx_t *, idx_t, idx_t); 241 idx_t mmdint(idx_t, idx_t *xadj, idx_t *, idx_t *, idx_t *, idx_t *, idx_t *, idx_t *, idx_t *); 242 void mmdnum(idx_t, idx_t *, idx_t *, idx_t *); 243 void mmdupd(idx_t, idx_t, idx_t *, idx_t *, idx_t, idx_t *, idx_t *, idx_t *, idx_t *, idx_t *, idx_t *, idx_t *, idx_t, idx_t *tag); 244 245 246 /* ometis.c */ 247 void MlevelNestedDissection(ctrl_t *ctrl, graph_t *graph, idx_t *order, 248 idx_t lastvtx); 249 void MlevelNestedDissectionCC(ctrl_t *ctrl, graph_t *graph, idx_t *order, 250 idx_t lastvtx); 251 void MlevelNodeBisectionMultiple(ctrl_t *ctrl, graph_t *graph); 252 void MlevelNodeBisectionL2(ctrl_t *ctrl, graph_t *graph, idx_t niparts); 253 void MlevelNodeBisectionL1(ctrl_t *ctrl, graph_t *graph, idx_t niparts); 254 void SplitGraphOrder(ctrl_t *ctrl, graph_t *graph, graph_t **r_lgraph, 255 graph_t **r_rgraph); 256 graph_t **SplitGraphOrderCC(ctrl_t *ctrl, graph_t *graph, idx_t ncmps, 257 idx_t *cptr, idx_t *cind); 258 void MMDOrder(ctrl_t *ctrl, graph_t *graph, idx_t *order, idx_t lastvtx); 259 260 261 /* options.c */ 262 ctrl_t *SetupCtrl(moptype_et optype, idx_t *options, idx_t ncon, idx_t nparts, 263 real_t *tpwgts, real_t *ubvec); 264 void SetupKWayBalMultipliers(ctrl_t *ctrl, graph_t *graph); 265 void Setup2WayBalMultipliers(ctrl_t *ctrl, graph_t *graph, real_t *tpwgts); 266 void PrintCtrl(ctrl_t *ctrl); 267 int CheckParams(ctrl_t *ctrl); 268 void FreeCtrl(ctrl_t **r_ctrl); 269 270 271 /* parmetis.c */ 272 void MlevelNestedDissectionP(ctrl_t *ctrl, graph_t *graph, idx_t *order, 273 idx_t lastvtx, idx_t npes, idx_t cpos, idx_t *sizes); 274 void FM_2WayNodeRefine1SidedP(ctrl_t *ctrl, graph_t *graph, idx_t *hmarker, 275 real_t ubfactor, idx_t npasses); 276 void FM_2WayNodeRefine2SidedP(ctrl_t *ctrl, graph_t *graph, idx_t *hmarker, 277 real_t ubfactor, idx_t npasses); 278 279 280 /* pmetis.c */ 281 idx_t MlevelRecursiveBisection(ctrl_t *ctrl, graph_t *graph, idx_t nparts, 282 idx_t *part, real_t *tpwgts, idx_t fpart); 283 idx_t MultilevelBisect(ctrl_t *ctrl, graph_t *graph, real_t *tpwgts); 284 void SplitGraphPart(ctrl_t *ctrl, graph_t *graph, graph_t **r_lgraph, graph_t **r_rgraph); 285 286 287 /* refine.c */ 288 void Refine2Way(ctrl_t *ctrl, graph_t *orggraph, graph_t *graph, real_t *rtpwgts); 289 void Allocate2WayPartitionMemory(ctrl_t *ctrl, graph_t *graph); 290 void Compute2WayPartitionParams(ctrl_t *ctrl, graph_t *graph); 291 void Project2WayPartition(ctrl_t *ctrl, graph_t *graph); 292 293 294 /* separator.c */ 295 void ConstructSeparator(ctrl_t *ctrl, graph_t *graph); 296 void ConstructMinCoverSeparator(ctrl_t *ctrl, graph_t *graph); 297 298 299 /* sfm.c */ 300 void FM_2WayNodeRefine2Sided(ctrl_t *ctrl, graph_t *graph, idx_t niter); 301 void FM_2WayNodeRefine1Sided(ctrl_t *ctrl, graph_t *graph, idx_t niter); 302 void FM_2WayNodeBalance(ctrl_t *ctrl, graph_t *graph); 303 304 305 /* srefine.c */ 306 void Refine2WayNode(ctrl_t *ctrl, graph_t *orggraph, graph_t *graph); 307 void Allocate2WayNodePartitionMemory(ctrl_t *ctrl, graph_t *graph); 308 void Compute2WayNodePartitionParams(ctrl_t *ctrl, graph_t *graph); 309 void Project2WayNodePartition(ctrl_t *ctrl, graph_t *graph); 310 311 312 /* stat.c */ 313 void ComputePartitionInfoBipartite(graph_t *, idx_t, idx_t *); 314 void ComputePartitionBalance(graph_t *, idx_t, idx_t *, real_t *); 315 real_t ComputeElementBalance(idx_t, idx_t, idx_t *); 316 317 318 /* timing.c */ 319 void InitTimers(ctrl_t *); 320 void PrintTimers(ctrl_t *); 321 322 /* util.c */ 323 idx_t iargmax_strd(size_t, idx_t *, idx_t); 324 idx_t iargmax_nrm(size_t n, idx_t *x, real_t *y); 325 idx_t iargmax2_nrm(size_t n, idx_t *x, real_t *y); 326 idx_t rargmax2(size_t, real_t *); 327 void InitRandom(idx_t); 328 int metis_rcode(int sigrval); 329 330 331 332 /* wspace.c */ 333 void AllocateWorkSpace(ctrl_t *ctrl, graph_t *graph); 334 void AllocateRefinementWorkSpace(ctrl_t *ctrl, idx_t nbrpoolsize); 335 void FreeWorkSpace(ctrl_t *ctrl); 336 void *wspacemalloc(ctrl_t *ctrl, size_t nbytes); 337 void wspacepush(ctrl_t *ctrl); 338 void wspacepop(ctrl_t *ctrl); 339 idx_t *iwspacemalloc(ctrl_t *, idx_t); 340 real_t *rwspacemalloc(ctrl_t *, idx_t); 341 ikv_t *ikvwspacemalloc(ctrl_t *, idx_t); 342 void cnbrpoolReset(ctrl_t *ctrl); 343 idx_t cnbrpoolGetNext(ctrl_t *ctrl, idx_t nnbrs); 344 void vnbrpoolReset(ctrl_t *ctrl); 345 idx_t vnbrpoolGetNext(ctrl_t *ctrl, idx_t nnbrs); 346 347 348 #endif 349