/* * Copyright 1997, Regents of the University of Minnesota * * proto.h * * This file contains header files * * Started 10/19/95 * George * * $Id: proto.h 13933 2013-03-29 22:20:46Z karypis $ * */ #ifndef _LIBMETIS_PROTO_H_ #define _LIBMETIS_PROTO_H_ /* auxapi.c */ /* balance.c */ void Balance2Way(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts); void Bnd2WayBalance(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts); void General2WayBalance(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts); void McGeneral2WayBalance(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts); /* bucketsort.c */ void BucketSortKeysInc(ctrl_t *ctrl, idx_t n, idx_t max, idx_t *keys, idx_t *tperm, idx_t *perm); /* checkgraph.c */ int CheckGraph(graph_t *graph, int numflag, int verbose); int CheckInputGraphWeights(idx_t nvtxs, idx_t ncon, idx_t *xadj, idx_t *adjncy, idx_t *vwgt, idx_t *vsize, idx_t *adjwgt); graph_t *FixGraph(graph_t *graph); /* coarsen.c */ graph_t *CoarsenGraph(ctrl_t *ctrl, graph_t *graph); graph_t *CoarsenGraphNlevels(ctrl_t *ctrl, graph_t *graph, idx_t nlevels); idx_t Match_RM(ctrl_t *ctrl, graph_t *graph); idx_t Match_SHEM(ctrl_t *ctrl, graph_t *graph); idx_t Match_2Hop(ctrl_t *ctrl, graph_t *graph, idx_t *perm, idx_t *match, idx_t cnvtxs, size_t nunmatched); idx_t Match_2HopAny(ctrl_t *ctrl, graph_t *graph, idx_t *perm, idx_t *match, idx_t cnvtxs, size_t *r_nunmatched, size_t maxdegree); idx_t Match_2HopAll(ctrl_t *ctrl, graph_t *graph, idx_t *perm, idx_t *match, idx_t cnvtxs, size_t *r_nunmatched, size_t maxdegree); void PrintCGraphStats(ctrl_t *ctrl, graph_t *graph); void CreateCoarseGraph(ctrl_t *ctrl, graph_t *graph, idx_t cnvtxs, idx_t *match); void CreateCoarseGraphNoMask(ctrl_t *ctrl, graph_t *graph, idx_t cnvtxs, idx_t *match); void CreateCoarseGraphPerm(ctrl_t *ctrl, graph_t *graph, idx_t cnvtxs, idx_t *match, idx_t *perm); graph_t *SetupCoarseGraph(graph_t *graph, idx_t cnvtxs, idx_t dovsize); void ReAdjustMemory(ctrl_t *ctrl, graph_t *graph, graph_t *cgraph); /* compress.c */ graph_t *CompressGraph(ctrl_t *ctrl, idx_t nvtxs, idx_t *xadj, idx_t *adjncy, idx_t *vwgt, idx_t *cptr, idx_t *cind); graph_t *PruneGraph(ctrl_t *ctrl, idx_t nvtxs, idx_t *xadj, idx_t *adjncy, idx_t *vwgt, idx_t *iperm, real_t factor); /* contig.c */ idx_t FindPartitionInducedComponents(graph_t *graph, idx_t *where, idx_t *cptr, idx_t *cind); void ComputeBFSOrdering(ctrl_t *ctrl, graph_t *graph, idx_t *bfsperm); idx_t IsConnected(graph_t *graph, idx_t report); idx_t IsConnectedSubdomain(ctrl_t *, graph_t *, idx_t, idx_t); idx_t FindSepInducedComponents(ctrl_t *, graph_t *, idx_t *, idx_t *); void EliminateComponents(ctrl_t *ctrl, graph_t *graph); void MoveGroupContigForCut(ctrl_t *ctrl, graph_t *graph, idx_t to, idx_t gid, idx_t *ptr, idx_t *ind); void MoveGroupContigForVol(ctrl_t *ctrl, graph_t *graph, idx_t to, idx_t gid, idx_t *ptr, idx_t *ind, idx_t *vmarker, idx_t *pmarker, idx_t *modind); /* debug.c */ idx_t ComputeCut(graph_t *graph, idx_t *where); idx_t ComputeVolume(graph_t *, idx_t *); idx_t ComputeMaxCut(graph_t *graph, idx_t nparts, idx_t *where); idx_t CheckBnd(graph_t *); idx_t CheckBnd2(graph_t *); idx_t CheckNodeBnd(graph_t *, idx_t); idx_t CheckRInfo(ctrl_t *ctrl, ckrinfo_t *rinfo); idx_t CheckNodePartitionParams(graph_t *); idx_t IsSeparable(graph_t *); void CheckKWayVolPartitionParams(ctrl_t *ctrl, graph_t *graph); /* fm.c */ void FM_2WayRefine(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niter); void FM_2WayCutRefine(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niter); void FM_Mc2WayCutRefine(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niter); void SelectQueue(graph_t *graph, real_t *pijbm, real_t *ubfactors, rpq_t **queues, idx_t *from, idx_t *cnum); void Print2WayRefineStats(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, real_t deltabal, idx_t mincutorder); /* fortran.c */ void Change2CNumbering(idx_t, idx_t *, idx_t *); void Change2FNumbering(idx_t, idx_t *, idx_t *, idx_t *); void Change2FNumbering2(idx_t, idx_t *, idx_t *); void Change2FNumberingOrder(idx_t, idx_t *, idx_t *, idx_t *, idx_t *); void ChangeMesh2CNumbering(idx_t n, idx_t *ptr, idx_t *ind); void ChangeMesh2FNumbering(idx_t n, idx_t *ptr, idx_t *ind, idx_t nvtxs, idx_t *xadj, idx_t *adjncy); void ChangeMesh2FNumbering2(idx_t ne, idx_t nn, idx_t *ptr, idx_t *ind, idx_t *epart, idx_t *npart); /* graph.c */ graph_t *SetupGraph(ctrl_t *ctrl, idx_t nvtxs, idx_t ncon, idx_t *xadj, idx_t *adjncy, idx_t *vwgt, idx_t *vsize, idx_t *adjwgt); void SetupGraph_tvwgt(graph_t *graph); void SetupGraph_label(graph_t *graph); graph_t *SetupSplitGraph(graph_t *graph, idx_t snvtxs, idx_t snedges); graph_t *CreateGraph(void); void InitGraph(graph_t *graph); void FreeRData(graph_t *graph); void FreeGraph(graph_t **graph); /* initpart.c */ void Init2WayPartition(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niparts); void InitSeparator(ctrl_t *ctrl, graph_t *graph, idx_t niparts); void RandomBisection(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niparts); void GrowBisection(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niparts); void McRandomBisection(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niparts); void McGrowBisection(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niparts); void GrowBisectionNode(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niparts); void GrowBisectionNode2(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niparts); /* kmetis.c */ idx_t MlevelKWayPartitioning(ctrl_t *ctrl, graph_t *graph, idx_t *part); void InitKWayPartitioning(ctrl_t *ctrl, graph_t *graph); /* kwayfm.c */ void Greedy_KWayOptimize(ctrl_t *ctrl, graph_t *graph, idx_t niter, real_t ffactor, idx_t omode); void Greedy_KWayCutOptimize(ctrl_t *ctrl, graph_t *graph, idx_t niter, real_t ffactor, idx_t omode); void Greedy_KWayVolOptimize(ctrl_t *ctrl, graph_t *graph, idx_t niter, real_t ffactor, idx_t omode); void Greedy_McKWayCutOptimize(ctrl_t *ctrl, graph_t *graph, idx_t niter, real_t ffactor, idx_t omode); void Greedy_McKWayVolOptimize(ctrl_t *ctrl, graph_t *graph, idx_t niter, real_t ffactor, idx_t omode); idx_t IsArticulationNode(idx_t i, idx_t *xadj, idx_t *adjncy, idx_t *where, idx_t *bfslvl, idx_t *bfsind, idx_t *bfsmrk); void KWayVolUpdate(ctrl_t *ctrl, graph_t *graph, idx_t v, idx_t from, idx_t to, ipq_t *queue, idx_t *vstatus, idx_t *r_nupd, idx_t *updptr, idx_t *updind, idx_t bndtype, idx_t *vmarker, idx_t *pmarker, idx_t *modind); /* kwayrefine.c */ void RefineKWay(ctrl_t *ctrl, graph_t *orggraph, graph_t *graph); void AllocateKWayPartitionMemory(ctrl_t *ctrl, graph_t *graph); void ComputeKWayPartitionParams(ctrl_t *ctrl, graph_t *graph); void ProjectKWayPartition(ctrl_t *ctrl, graph_t *graph); void ComputeKWayBoundary(ctrl_t *ctrl, graph_t *graph, idx_t bndtype); void ComputeKWayVolGains(ctrl_t *ctrl, graph_t *graph); int IsBalanced(ctrl_t *ctrl, graph_t *graph, real_t ffactor); /* mcutil.c */ int rvecle(idx_t n, real_t *x, real_t *y); int rvecge(idx_t n, real_t *x, real_t *y); int rvecsumle(idx_t n, real_t *x1, real_t *x2, real_t *y); real_t rvecmaxdiff(idx_t n, real_t *x, real_t *y); int ivecle(idx_t n, idx_t *x, idx_t *z); int ivecge(idx_t n, idx_t *x, idx_t *z); int ivecaxpylez(idx_t n, idx_t a, idx_t *x, idx_t *y, idx_t *z); int ivecaxpygez(idx_t n, idx_t a, idx_t *x, idx_t *y, idx_t *z); int BetterVBalance(idx_t ncon, real_t *itvwgt, idx_t *v_vwgt, idx_t *u1_vwgt, idx_t *u2_vwgt); int BetterBalance2Way(idx_t n, real_t *x, real_t *y); int BetterBalanceKWay(idx_t ncon, idx_t *vwgt, real_t *itvwgt, idx_t a1, idx_t *pt1, real_t *bm1, idx_t a2, idx_t *pt2, real_t *bm2); real_t ComputeLoadImbalance(graph_t *graph, idx_t nparts, real_t *pijbm); real_t ComputeLoadImbalanceDiff(graph_t *graph, idx_t nparts, real_t *pijbm, real_t *ubvec); real_t ComputeLoadImbalanceDiffVec(graph_t *graph, idx_t nparts, real_t *pijbm, real_t *ubfactors, real_t *diffvec); void ComputeLoadImbalanceVec(graph_t *graph, idx_t nparts, real_t *pijbm, real_t *lbvec); /* mesh.c */ void CreateGraphDual(idx_t ne, idx_t nn, idx_t *eptr, idx_t *eind, idx_t ncommon, idx_t **r_xadj, idx_t **r_adjncy); idx_t FindCommonElements(idx_t qid, idx_t elen, idx_t *eind, idx_t *nptr, idx_t *nind, idx_t *eptr, idx_t ncommon, idx_t *marker, idx_t *nbrs); void CreateGraphNodal(idx_t ne, idx_t nn, idx_t *eptr, idx_t *eind, idx_t **r_xadj, idx_t **r_adjncy); idx_t FindCommonNodes(idx_t qid, idx_t nelmnts, idx_t *elmntids, idx_t *eptr, idx_t *eind, idx_t *marker, idx_t *nbrs); mesh_t *CreateMesh(void); void InitMesh(mesh_t *mesh); void FreeMesh(mesh_t **mesh); /* meshpart.c */ void InduceRowPartFromColumnPart(idx_t nrows, idx_t *rowptr, idx_t *rowind, idx_t *rpart, idx_t *cpart, idx_t nparts, real_t *tpwgts); /* minconn.c */ void ComputeSubDomainGraph(ctrl_t *ctrl, graph_t *graph); void UpdateEdgeSubDomainGraph(ctrl_t *ctrl, idx_t u, idx_t v, idx_t ewgt, idx_t *r_maxndoms); void PrintSubDomainGraph(graph_t *graph, idx_t nparts, idx_t *where); void EliminateSubDomainEdges(ctrl_t *ctrl, graph_t *graph); void MoveGroupMinConnForCut(ctrl_t *ctrl, graph_t *graph, idx_t to, idx_t nind, idx_t *ind); void MoveGroupMinConnForVol(ctrl_t *ctrl, graph_t *graph, idx_t to, idx_t nind, idx_t *ind, idx_t *vmarker, idx_t *pmarker, idx_t *modind); /* mincover.o */ void MinCover(idx_t *, idx_t *, idx_t, idx_t, idx_t *, idx_t *); idx_t MinCover_Augment(idx_t *, idx_t *, idx_t, idx_t *, idx_t *, idx_t *, idx_t); void MinCover_Decompose(idx_t *, idx_t *, idx_t, idx_t, idx_t *, idx_t *, idx_t *); void MinCover_ColDFS(idx_t *, idx_t *, idx_t, idx_t *, idx_t *, idx_t); void MinCover_RowDFS(idx_t *, idx_t *, idx_t, idx_t *, idx_t *, idx_t); /* mmd.c */ 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 *); 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); idx_t mmdint(idx_t, idx_t *xadj, idx_t *, idx_t *, idx_t *, idx_t *, idx_t *, idx_t *, idx_t *); void mmdnum(idx_t, idx_t *, idx_t *, idx_t *); 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); /* ometis.c */ void MlevelNestedDissection(ctrl_t *ctrl, graph_t *graph, idx_t *order, idx_t lastvtx); void MlevelNestedDissectionCC(ctrl_t *ctrl, graph_t *graph, idx_t *order, idx_t lastvtx); void MlevelNodeBisectionMultiple(ctrl_t *ctrl, graph_t *graph); void MlevelNodeBisectionL2(ctrl_t *ctrl, graph_t *graph, idx_t niparts); void MlevelNodeBisectionL1(ctrl_t *ctrl, graph_t *graph, idx_t niparts); void SplitGraphOrder(ctrl_t *ctrl, graph_t *graph, graph_t **r_lgraph, graph_t **r_rgraph); graph_t **SplitGraphOrderCC(ctrl_t *ctrl, graph_t *graph, idx_t ncmps, idx_t *cptr, idx_t *cind); void MMDOrder(ctrl_t *ctrl, graph_t *graph, idx_t *order, idx_t lastvtx); /* options.c */ ctrl_t *SetupCtrl(moptype_et optype, idx_t *options, idx_t ncon, idx_t nparts, real_t *tpwgts, real_t *ubvec); void SetupKWayBalMultipliers(ctrl_t *ctrl, graph_t *graph); void Setup2WayBalMultipliers(ctrl_t *ctrl, graph_t *graph, real_t *tpwgts); void PrintCtrl(ctrl_t *ctrl); int CheckParams(ctrl_t *ctrl); void FreeCtrl(ctrl_t **r_ctrl); /* parmetis.c */ void MlevelNestedDissectionP(ctrl_t *ctrl, graph_t *graph, idx_t *order, idx_t lastvtx, idx_t npes, idx_t cpos, idx_t *sizes); void FM_2WayNodeRefine1SidedP(ctrl_t *ctrl, graph_t *graph, idx_t *hmarker, real_t ubfactor, idx_t npasses); void FM_2WayNodeRefine2SidedP(ctrl_t *ctrl, graph_t *graph, idx_t *hmarker, real_t ubfactor, idx_t npasses); /* pmetis.c */ idx_t MlevelRecursiveBisection(ctrl_t *ctrl, graph_t *graph, idx_t nparts, idx_t *part, real_t *tpwgts, idx_t fpart); idx_t MultilevelBisect(ctrl_t *ctrl, graph_t *graph, real_t *tpwgts); void SplitGraphPart(ctrl_t *ctrl, graph_t *graph, graph_t **r_lgraph, graph_t **r_rgraph); /* refine.c */ void Refine2Way(ctrl_t *ctrl, graph_t *orggraph, graph_t *graph, real_t *rtpwgts); void Allocate2WayPartitionMemory(ctrl_t *ctrl, graph_t *graph); void Compute2WayPartitionParams(ctrl_t *ctrl, graph_t *graph); void Project2WayPartition(ctrl_t *ctrl, graph_t *graph); /* separator.c */ void ConstructSeparator(ctrl_t *ctrl, graph_t *graph); void ConstructMinCoverSeparator(ctrl_t *ctrl, graph_t *graph); /* sfm.c */ void FM_2WayNodeRefine2Sided(ctrl_t *ctrl, graph_t *graph, idx_t niter); void FM_2WayNodeRefine1Sided(ctrl_t *ctrl, graph_t *graph, idx_t niter); void FM_2WayNodeBalance(ctrl_t *ctrl, graph_t *graph); /* srefine.c */ void Refine2WayNode(ctrl_t *ctrl, graph_t *orggraph, graph_t *graph); void Allocate2WayNodePartitionMemory(ctrl_t *ctrl, graph_t *graph); void Compute2WayNodePartitionParams(ctrl_t *ctrl, graph_t *graph); void Project2WayNodePartition(ctrl_t *ctrl, graph_t *graph); /* stat.c */ void ComputePartitionInfoBipartite(graph_t *, idx_t, idx_t *); void ComputePartitionBalance(graph_t *, idx_t, idx_t *, real_t *); real_t ComputeElementBalance(idx_t, idx_t, idx_t *); /* timing.c */ void InitTimers(ctrl_t *); void PrintTimers(ctrl_t *); /* util.c */ idx_t iargmax_strd(size_t, idx_t *, idx_t); idx_t iargmax_nrm(size_t n, idx_t *x, real_t *y); idx_t iargmax2_nrm(size_t n, idx_t *x, real_t *y); idx_t rargmax2(size_t, real_t *); void InitRandom(idx_t); int metis_rcode(int sigrval); /* wspace.c */ void AllocateWorkSpace(ctrl_t *ctrl, graph_t *graph); void AllocateRefinementWorkSpace(ctrl_t *ctrl, idx_t nbrpoolsize); void FreeWorkSpace(ctrl_t *ctrl); void *wspacemalloc(ctrl_t *ctrl, size_t nbytes); void wspacepush(ctrl_t *ctrl); void wspacepop(ctrl_t *ctrl); idx_t *iwspacemalloc(ctrl_t *, idx_t); real_t *rwspacemalloc(ctrl_t *, idx_t); ikv_t *ikvwspacemalloc(ctrl_t *, idx_t); void cnbrpoolReset(ctrl_t *ctrl); idx_t cnbrpoolGetNext(ctrl_t *ctrl, idx_t nnbrs); void vnbrpoolReset(ctrl_t *ctrl); idx_t vnbrpoolGetNext(ctrl_t *ctrl, idx_t nnbrs); #endif