Charm++: Charm Source Code Documentation

00001 /*
00002  * Copyright 1997, Regents of the University of Minnesota
00003  *
00004  * proto.h
00005  *
00006  * This file contains header files
00007  *
00008  * Started 10/19/95
00009  * George
00010  *
00011  * $Id: proto.h 13933 2013-03-29 22:20:46Z karypis $
00012  *
00013  */
00014 
00015 #ifndef _LIBMETIS_PROTO_H_
00016 #define _LIBMETIS_PROTO_H_
00017 
00018 /* auxapi.c */
00019 
00020 /* balance.c */
00021 void Balance2Way(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts);
00022 void Bnd2WayBalance(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts);
00023 void General2WayBalance(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts);
00024 void McGeneral2WayBalance(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts);
00025 
00026 
00027 /* bucketsort.c */
00028 void BucketSortKeysInc(ctrl_t *ctrl, idx_t n, idx_t max, idx_t *keys,
00029          idx_t *tperm, idx_t *perm);
00030 
00031 
00032 /* checkgraph.c */
00033 int CheckGraph(graph_t *graph, int numflag, int verbose);
00034 int CheckInputGraphWeights(idx_t nvtxs, idx_t ncon, idx_t *xadj, idx_t *adjncy,
00035         idx_t *vwgt, idx_t *vsize, idx_t *adjwgt);
00036 graph_t *FixGraph(graph_t *graph);
00037 
00038 
00039 /* coarsen.c */
00040 graph_t *CoarsenGraph(ctrl_t *ctrl, graph_t *graph);
00041 graph_t *CoarsenGraphNlevels(ctrl_t *ctrl, graph_t *graph, idx_t nlevels);
00042 idx_t Match_RM(ctrl_t *ctrl, graph_t *graph);
00043 idx_t Match_SHEM(ctrl_t *ctrl, graph_t *graph);
00044 idx_t Match_2Hop(ctrl_t *ctrl, graph_t *graph, idx_t *perm, idx_t *match,
00045           idx_t cnvtxs, size_t nunmatched);
00046 idx_t Match_2HopAny(ctrl_t *ctrl, graph_t *graph, idx_t *perm, idx_t *match,
00047           idx_t cnvtxs, size_t *r_nunmatched, size_t maxdegree);
00048 idx_t Match_2HopAll(ctrl_t *ctrl, graph_t *graph, idx_t *perm, idx_t *match,
00049           idx_t cnvtxs, size_t *r_nunmatched, size_t maxdegree);
00050 void PrintCGraphStats(ctrl_t *ctrl, graph_t *graph);
00051 void CreateCoarseGraph(ctrl_t *ctrl, graph_t *graph, idx_t cnvtxs, 
00052          idx_t *match);
00053 void CreateCoarseGraphNoMask(ctrl_t *ctrl, graph_t *graph, idx_t cnvtxs, 
00054          idx_t *match);
00055 void CreateCoarseGraphPerm(ctrl_t *ctrl, graph_t *graph, idx_t cnvtxs, 
00056          idx_t *match, idx_t *perm);
00057 graph_t *SetupCoarseGraph(graph_t *graph, idx_t cnvtxs, idx_t dovsize);
00058 void ReAdjustMemory(ctrl_t *ctrl, graph_t *graph, graph_t *cgraph);
00059 
00060 
00061 
00062 /* compress.c */
00063 graph_t *CompressGraph(ctrl_t *ctrl, idx_t nvtxs, idx_t *xadj, idx_t *adjncy, 
00064              idx_t *vwgt, idx_t *cptr, idx_t *cind);
00065 graph_t *PruneGraph(ctrl_t *ctrl, idx_t nvtxs, idx_t *xadj, idx_t *adjncy, 
00066              idx_t *vwgt, idx_t *iperm, real_t factor);
00067 
00068 
00069 /* contig.c */
00070 idx_t FindPartitionInducedComponents(graph_t *graph, idx_t *where, 
00071           idx_t *cptr, idx_t *cind);
00072 void ComputeBFSOrdering(ctrl_t *ctrl, graph_t *graph, idx_t *bfsperm);
00073 idx_t IsConnected(graph_t *graph, idx_t report);
00074 idx_t IsConnectedSubdomain(ctrl_t *, graph_t *, idx_t, idx_t);
00075 idx_t FindSepInducedComponents(ctrl_t *, graph_t *, idx_t *, idx_t *);
00076 void EliminateComponents(ctrl_t *ctrl, graph_t *graph);
00077 void MoveGroupContigForCut(ctrl_t *ctrl, graph_t *graph, idx_t to, idx_t gid, 
00078          idx_t *ptr, idx_t *ind);
00079 void MoveGroupContigForVol(ctrl_t *ctrl, graph_t *graph, idx_t to, idx_t gid,
00080          idx_t *ptr, idx_t *ind, idx_t *vmarker, idx_t *pmarker,
00081          idx_t *modind);
00082 
00083 
00084 /* debug.c */
00085 idx_t ComputeCut(graph_t *graph, idx_t *where);
00086 idx_t ComputeVolume(graph_t *, idx_t *);
00087 idx_t ComputeMaxCut(graph_t *graph, idx_t nparts, idx_t *where);
00088 idx_t CheckBnd(graph_t *);
00089 idx_t CheckBnd2(graph_t *);
00090 idx_t CheckNodeBnd(graph_t *, idx_t);
00091 idx_t CheckRInfo(ctrl_t *ctrl, ckrinfo_t *rinfo);
00092 idx_t CheckNodePartitionParams(graph_t *);
00093 idx_t IsSeparable(graph_t *);
00094 void CheckKWayVolPartitionParams(ctrl_t *ctrl, graph_t *graph);
00095 
00096 
00097 /* fm.c */
00098 void FM_2WayRefine(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niter);
00099 void FM_2WayCutRefine(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niter);
00100 void FM_Mc2WayCutRefine(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niter);
00101 void SelectQueue(graph_t *graph, real_t *pijbm, real_t *ubfactors, rpq_t **queues, 
00102          idx_t *from, idx_t *cnum);
00103 void Print2WayRefineStats(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, 
00104          real_t deltabal, idx_t mincutorder);
00105 
00106 
00107 /* fortran.c */
00108 void Change2CNumbering(idx_t, idx_t *, idx_t *);
00109 void Change2FNumbering(idx_t, idx_t *, idx_t *, idx_t *);
00110 void Change2FNumbering2(idx_t, idx_t *, idx_t *);
00111 void Change2FNumberingOrder(idx_t, idx_t *, idx_t *, idx_t *, idx_t *);
00112 void ChangeMesh2CNumbering(idx_t n, idx_t *ptr, idx_t *ind);
00113 void ChangeMesh2FNumbering(idx_t n, idx_t *ptr, idx_t *ind, idx_t nvtxs,
00114          idx_t *xadj, idx_t *adjncy);
00115 void ChangeMesh2FNumbering2(idx_t ne, idx_t nn, idx_t *ptr, idx_t *ind,
00116          idx_t *epart, idx_t *npart);
00117 
00118 
00119 /* graph.c */
00120 graph_t *SetupGraph(ctrl_t *ctrl, idx_t nvtxs, idx_t ncon, idx_t *xadj, 
00121              idx_t *adjncy, idx_t *vwgt, idx_t *vsize, idx_t *adjwgt);
00122 void SetupGraph_tvwgt(graph_t *graph);
00123 void SetupGraph_label(graph_t *graph);
00124 graph_t *SetupSplitGraph(graph_t *graph, idx_t snvtxs, idx_t snedges);
00125 graph_t *CreateGraph(void);
00126 void InitGraph(graph_t *graph);
00127 void FreeRData(graph_t *graph);
00128 void FreeGraph(graph_t **graph);
00129 
00130 
00131 /* initpart.c */
00132 void Init2WayPartition(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niparts);
00133 void InitSeparator(ctrl_t *ctrl, graph_t *graph, idx_t niparts);
00134 void RandomBisection(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niparts);
00135 void GrowBisection(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niparts);
00136 void McRandomBisection(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niparts);
00137 void McGrowBisection(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niparts);
00138 void GrowBisectionNode(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niparts);
00139 void GrowBisectionNode2(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niparts);
00140 
00141 
00142 /* kmetis.c */
00143 idx_t MlevelKWayPartitioning(ctrl_t *ctrl, graph_t *graph, idx_t *part);
00144 void InitKWayPartitioning(ctrl_t *ctrl, graph_t *graph);
00145 
00146 
00147 /* kwayfm.c */
00148 void Greedy_KWayOptimize(ctrl_t *ctrl, graph_t *graph, idx_t niter, 
00149          real_t ffactor, idx_t omode);
00150 void Greedy_KWayCutOptimize(ctrl_t *ctrl, graph_t *graph, idx_t niter, 
00151          real_t ffactor, idx_t omode);
00152 void Greedy_KWayVolOptimize(ctrl_t *ctrl, graph_t *graph, idx_t niter, 
00153          real_t ffactor, idx_t omode);
00154 void Greedy_McKWayCutOptimize(ctrl_t *ctrl, graph_t *graph, idx_t niter, 
00155          real_t ffactor, idx_t omode);
00156 void Greedy_McKWayVolOptimize(ctrl_t *ctrl, graph_t *graph, idx_t niter, 
00157          real_t ffactor, idx_t omode);
00158 idx_t IsArticulationNode(idx_t i, idx_t *xadj, idx_t *adjncy, idx_t *where,
00159           idx_t *bfslvl, idx_t *bfsind, idx_t *bfsmrk);
00160 void KWayVolUpdate(ctrl_t *ctrl, graph_t *graph, idx_t v, idx_t from,
00161          idx_t to, ipq_t *queue, idx_t *vstatus, idx_t *r_nupd, idx_t *updptr,
00162          idx_t *updind, idx_t bndtype, idx_t *vmarker, idx_t *pmarker,
00163          idx_t *modind);
00164 
00165 
00166 /* kwayrefine.c */
00167 void RefineKWay(ctrl_t *ctrl, graph_t *orggraph, graph_t *graph);
00168 void AllocateKWayPartitionMemory(ctrl_t *ctrl, graph_t *graph);
00169 void ComputeKWayPartitionParams(ctrl_t *ctrl, graph_t *graph);
00170 void ProjectKWayPartition(ctrl_t *ctrl, graph_t *graph);
00171 void ComputeKWayBoundary(ctrl_t *ctrl, graph_t *graph, idx_t bndtype);
00172 void ComputeKWayVolGains(ctrl_t *ctrl, graph_t *graph);
00173 int IsBalanced(ctrl_t *ctrl, graph_t *graph, real_t ffactor);
00174 
00175 
00176 /* mcutil.c */
00177 int rvecle(idx_t n, real_t *x, real_t *y);
00178 int rvecge(idx_t n, real_t *x, real_t *y);
00179 int rvecsumle(idx_t n, real_t *x1, real_t *x2, real_t *y);
00180 real_t rvecmaxdiff(idx_t n, real_t *x, real_t *y);
00181 int ivecle(idx_t n, idx_t *x, idx_t *z);
00182 int ivecge(idx_t n, idx_t *x, idx_t *z);
00183 int ivecaxpylez(idx_t n, idx_t a, idx_t *x, idx_t *y, idx_t *z);
00184 int ivecaxpygez(idx_t n, idx_t a, idx_t *x, idx_t *y, idx_t *z);
00185 int BetterVBalance(idx_t ncon, real_t *itvwgt, idx_t *v_vwgt, idx_t *u1_vwgt,
00186             idx_t *u2_vwgt);
00187 int BetterBalance2Way(idx_t n, real_t *x, real_t *y);
00188 int BetterBalanceKWay(idx_t ncon, idx_t *vwgt, real_t *itvwgt, idx_t a1,
00189         idx_t *pt1, real_t *bm1, idx_t a2, idx_t *pt2, real_t *bm2);
00190 real_t ComputeLoadImbalance(graph_t *graph, idx_t nparts, real_t *pijbm);
00191 real_t ComputeLoadImbalanceDiff(graph_t *graph, idx_t nparts, real_t *pijbm, 
00192            real_t *ubvec);
00193 real_t ComputeLoadImbalanceDiffVec(graph_t *graph, idx_t nparts, real_t *pijbm, 
00194          real_t *ubfactors, real_t *diffvec);
00195 void ComputeLoadImbalanceVec(graph_t *graph, idx_t nparts, real_t *pijbm,
00196              real_t *lbvec);
00197 
00198 
00199 /* mesh.c */
00200 void CreateGraphDual(idx_t ne, idx_t nn, idx_t *eptr, idx_t *eind, idx_t ncommon,
00201           idx_t **r_xadj, idx_t **r_adjncy);
00202 idx_t FindCommonElements(idx_t qid, idx_t elen, idx_t *eind, idx_t *nptr,
00203           idx_t *nind, idx_t *eptr, idx_t ncommon, idx_t *marker, idx_t *nbrs);
00204 void CreateGraphNodal(idx_t ne, idx_t nn, idx_t *eptr, idx_t *eind, idx_t **r_xadj, 
00205           idx_t **r_adjncy);
00206 idx_t FindCommonNodes(idx_t qid, idx_t nelmnts, idx_t *elmntids, idx_t *eptr,
00207           idx_t *eind, idx_t *marker, idx_t *nbrs);
00208 mesh_t *CreateMesh(void);
00209 void InitMesh(mesh_t *mesh);  
00210 void FreeMesh(mesh_t **mesh);
00211 
00212 
00213 /* meshpart.c */
00214 void InduceRowPartFromColumnPart(idx_t nrows, idx_t *rowptr, idx_t *rowind,
00215          idx_t *rpart, idx_t *cpart, idx_t nparts, real_t *tpwgts);
00216 
00217 
00218 /* minconn.c */
00219 void ComputeSubDomainGraph(ctrl_t *ctrl, graph_t *graph);
00220 void UpdateEdgeSubDomainGraph(ctrl_t *ctrl, idx_t u, idx_t v, idx_t ewgt, 
00221          idx_t *r_maxndoms);
00222 void PrintSubDomainGraph(graph_t *graph, idx_t nparts, idx_t *where);
00223 void EliminateSubDomainEdges(ctrl_t *ctrl, graph_t *graph);
00224 void MoveGroupMinConnForCut(ctrl_t *ctrl, graph_t *graph, idx_t to, idx_t nind, 
00225          idx_t *ind);
00226 void MoveGroupMinConnForVol(ctrl_t *ctrl, graph_t *graph, idx_t to, idx_t nind, 
00227          idx_t *ind, idx_t *vmarker, idx_t *pmarker, idx_t *modind);
00228 
00229 
00230 /* mincover.o */
00231 void MinCover(idx_t *, idx_t *, idx_t, idx_t, idx_t *, idx_t *);
00232 idx_t MinCover_Augment(idx_t *, idx_t *, idx_t, idx_t *, idx_t *, idx_t *, idx_t);
00233 void MinCover_Decompose(idx_t *, idx_t *, idx_t, idx_t, idx_t *, idx_t *, idx_t *);
00234 void MinCover_ColDFS(idx_t *, idx_t *, idx_t, idx_t *, idx_t *, idx_t);
00235 void MinCover_RowDFS(idx_t *, idx_t *, idx_t, idx_t *, idx_t *, idx_t);
00236 
00237 
00238 /* mmd.c */
00239 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 *);
00240 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);
00241 idx_t mmdint(idx_t, idx_t *xadj, idx_t *, idx_t *, idx_t *, idx_t *, idx_t *, idx_t *, idx_t *);
00242 void mmdnum(idx_t, idx_t *, idx_t *, idx_t *);
00243 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);
00244 
00245 
00246 /* ometis.c */
00247 void MlevelNestedDissection(ctrl_t *ctrl, graph_t *graph, idx_t *order,
00248          idx_t lastvtx);
00249 void MlevelNestedDissectionCC(ctrl_t *ctrl, graph_t *graph, idx_t *order,
00250          idx_t lastvtx);
00251 void MlevelNodeBisectionMultiple(ctrl_t *ctrl, graph_t *graph);
00252 void MlevelNodeBisectionL2(ctrl_t *ctrl, graph_t *graph, idx_t niparts);
00253 void MlevelNodeBisectionL1(ctrl_t *ctrl, graph_t *graph, idx_t niparts);
00254 void SplitGraphOrder(ctrl_t *ctrl, graph_t *graph, graph_t **r_lgraph, 
00255          graph_t **r_rgraph);
00256 graph_t **SplitGraphOrderCC(ctrl_t *ctrl, graph_t *graph, idx_t ncmps,
00257               idx_t *cptr, idx_t *cind);
00258 void MMDOrder(ctrl_t *ctrl, graph_t *graph, idx_t *order, idx_t lastvtx);
00259 
00260 
00261 /* options.c */
00262 ctrl_t *SetupCtrl(moptype_et optype, idx_t *options, idx_t ncon, idx_t nparts, 
00263             real_t *tpwgts, real_t *ubvec);
00264 void SetupKWayBalMultipliers(ctrl_t *ctrl, graph_t *graph);
00265 void Setup2WayBalMultipliers(ctrl_t *ctrl, graph_t *graph, real_t *tpwgts);
00266 void PrintCtrl(ctrl_t *ctrl);
00267 int CheckParams(ctrl_t *ctrl);
00268 void FreeCtrl(ctrl_t **r_ctrl);
00269 
00270 
00271 /* parmetis.c */
00272 void MlevelNestedDissectionP(ctrl_t *ctrl, graph_t *graph, idx_t *order,
00273          idx_t lastvtx, idx_t npes, idx_t cpos, idx_t *sizes);
00274 void FM_2WayNodeRefine1SidedP(ctrl_t *ctrl, graph_t *graph, idx_t *hmarker, 
00275          real_t ubfactor, idx_t npasses);
00276 void FM_2WayNodeRefine2SidedP(ctrl_t *ctrl, graph_t *graph, idx_t *hmarker, 
00277          real_t ubfactor, idx_t npasses);
00278 
00279 
00280 /* pmetis.c */
00281 idx_t MlevelRecursiveBisection(ctrl_t *ctrl, graph_t *graph, idx_t nparts, 
00282           idx_t *part, real_t *tpwgts, idx_t fpart);
00283 idx_t MultilevelBisect(ctrl_t *ctrl, graph_t *graph, real_t *tpwgts);
00284 void SplitGraphPart(ctrl_t *ctrl, graph_t *graph, graph_t **r_lgraph, graph_t **r_rgraph);
00285 
00286 
00287 /* refine.c */
00288 void Refine2Way(ctrl_t *ctrl, graph_t *orggraph, graph_t *graph, real_t *rtpwgts);
00289 void Allocate2WayPartitionMemory(ctrl_t *ctrl, graph_t *graph);
00290 void Compute2WayPartitionParams(ctrl_t *ctrl, graph_t *graph);
00291 void Project2WayPartition(ctrl_t *ctrl, graph_t *graph);
00292 
00293 
00294 /* separator.c */
00295 void ConstructSeparator(ctrl_t *ctrl, graph_t *graph);
00296 void ConstructMinCoverSeparator(ctrl_t *ctrl, graph_t *graph);
00297 
00298 
00299 /* sfm.c */
00300 void FM_2WayNodeRefine2Sided(ctrl_t *ctrl, graph_t *graph, idx_t niter);
00301 void FM_2WayNodeRefine1Sided(ctrl_t *ctrl, graph_t *graph, idx_t niter);
00302 void FM_2WayNodeBalance(ctrl_t *ctrl, graph_t *graph);
00303 
00304 
00305 /* srefine.c */
00306 void Refine2WayNode(ctrl_t *ctrl, graph_t *orggraph, graph_t *graph);
00307 void Allocate2WayNodePartitionMemory(ctrl_t *ctrl, graph_t *graph);
00308 void Compute2WayNodePartitionParams(ctrl_t *ctrl, graph_t *graph);
00309 void Project2WayNodePartition(ctrl_t *ctrl, graph_t *graph);
00310 
00311 
00312 /* stat.c */
00313 void ComputePartitionInfoBipartite(graph_t *, idx_t, idx_t *);
00314 void ComputePartitionBalance(graph_t *, idx_t, idx_t *, real_t *);
00315 real_t ComputeElementBalance(idx_t, idx_t, idx_t *);
00316 
00317 
00318 /* timing.c */
00319 void InitTimers(ctrl_t *);
00320 void PrintTimers(ctrl_t *);
00321 
00322 /* util.c */
00323 idx_t iargmax_strd(size_t, idx_t *, idx_t);
00324 idx_t iargmax_nrm(size_t n, idx_t *x, real_t *y);
00325 idx_t iargmax2_nrm(size_t n, idx_t *x, real_t *y);
00326 idx_t rargmax2(size_t, real_t *);
00327 void InitRandom(idx_t);
00328 int metis_rcode(int sigrval);
00329 
00330 
00331 
00332 /* wspace.c */
00333 void AllocateWorkSpace(ctrl_t *ctrl, graph_t *graph);
00334 void AllocateRefinementWorkSpace(ctrl_t *ctrl, idx_t nbrpoolsize);
00335 void FreeWorkSpace(ctrl_t *ctrl);
00336 void *wspacemalloc(ctrl_t *ctrl, size_t nbytes);
00337 void wspacepush(ctrl_t *ctrl);
00338 void wspacepop(ctrl_t *ctrl);
00339 idx_t *iwspacemalloc(ctrl_t *, idx_t);
00340 real_t *rwspacemalloc(ctrl_t *, idx_t);
00341 ikv_t *ikvwspacemalloc(ctrl_t *, idx_t);
00342 void cnbrpoolReset(ctrl_t *ctrl);
00343 idx_t cnbrpoolGetNext(ctrl_t *ctrl, idx_t nnbrs);
00344 void vnbrpoolReset(ctrl_t *ctrl);
00345 idx_t vnbrpoolGetNext(ctrl_t *ctrl, idx_t nnbrs);
00346 
00347 
00348 #endif
libs/ck-libs/metis/libmetis/proto.h
