You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
353 lines
14 KiB
353 lines
14 KiB
/*
|
|
* Copyright 1997, Regents of the University of Minnesota
|
|
*
|
|
* proto.h
|
|
*
|
|
* This file contains header files
|
|
*
|
|
* Started 10/19/95
|
|
* George
|
|
*
|
|
* $Id: proto.h 20398 2016-11-22 17:17:12Z 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);
|
|
idx_t Match_JC(ctrl_t *ctrl, graph_t *graph);
|
|
void PrintCGraphStats(ctrl_t *ctrl, graph_t *graph);
|
|
void CreateCoarseGraph(ctrl_t *ctrl, graph_t *graph, idx_t cnvtxs,
|
|
idx_t *match);
|
|
graph_t *SetupCoarseGraph(graph_t *graph, idx_t cnvtxs, int 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 FreeSData(graph_t *graph);
|
|
void FreeRData(graph_t *graph);
|
|
void FreeGraph(graph_t **graph);
|
|
void graph_WriteToDisk(ctrl_t *ctrl, graph_t *graph);
|
|
void graph_ReadFromDisk(ctrl_t *ctrl, 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);
|
|
idx_t BlockKWayPartitioning(ctrl_t *ctrl, graph_t *graph, idx_t *part);
|
|
idx_t GrowMultisection(ctrl_t *ctrl, graph_t *graph, idx_t nparts, idx_t *where);
|
|
void BalanceAndRefineLP(ctrl_t *ctrl, graph_t *graph, idx_t nparts, idx_t *where);
|
|
|
|
|
|
/* 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);
|
|
void Greedy_KWayEdgeStats(ctrl_t *ctrl, graph_t *graph);
|
|
void Greedy_KWayEdgeCutOptimize(ctrl_t *ctrl, graph_t *graph, idx_t niter);
|
|
|
|
|
|
/* 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_max, 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
|
|
|