Functions
libmetis/proto.h File Reference
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Functions

void Allocate2WayNodePartitionMemory (ctrl_t *ctrl, graph_t *graph)
 
void Allocate2WayPartitionMemory (ctrl_t *ctrl, graph_t *graph)
 
void AllocateKWayPartitionMemory (ctrl_t *ctrl, graph_t *graph)
 
void AllocateRefinementWorkSpace (ctrl_t *ctrl, idx_t nbrpoolsize)
 
void AllocateWorkSpace (ctrl_t *ctrl, graph_t *graph)
 
void Balance2Way (ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts)
 
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)
 
int BetterVBalance (idx_t ncon, real_t *itvwgt, idx_t *v_vwgt, idx_t *u1_vwgt, idx_t *u2_vwgt)
 
void Bnd2WayBalance (ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts)
 
void BucketSortKeysInc (ctrl_t *ctrl, idx_t n, idx_t max, idx_t *keys, idx_t *tperm, idx_t *perm)
 
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)
 
idx_t CheckBnd (graph_t *)
 
idx_t CheckBnd2 (graph_t *)
 
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)
 
void CheckKWayVolPartitionParams (ctrl_t *ctrl, graph_t *graph)
 
idx_t CheckNodeBnd (graph_t *, idx_t)
 
idx_t CheckNodePartitionParams (graph_t *)
 
int CheckParams (ctrl_t *ctrl)
 
idx_t CheckRInfo (ctrl_t *ctrl, ckrinfo_t *rinfo)
 
idx_t cnbrpoolGetNext (ctrl_t *ctrl, idx_t nnbrs)
 
void cnbrpoolReset (ctrl_t *ctrl)
 
graph_tCoarsenGraph (ctrl_t *ctrl, graph_t *graph)
 
graph_tCoarsenGraphNlevels (ctrl_t *ctrl, graph_t *graph, idx_t nlevels)
 
graph_tCompressGraph (ctrl_t *ctrl, idx_t nvtxs, idx_t *xadj, idx_t *adjncy, idx_t *vwgt, idx_t *cptr, idx_t *cind)
 
void Compute2WayNodePartitionParams (ctrl_t *ctrl, graph_t *graph)
 
void Compute2WayPartitionParams (ctrl_t *ctrl, graph_t *graph)
 
void ComputeBFSOrdering (ctrl_t *ctrl, graph_t *graph, idx_t *bfsperm)
 
idx_t ComputeCut (graph_t *graph, idx_t *where)
 
real_t ComputeElementBalance (idx_t, idx_t, idx_t *)
 
void ComputeKWayBoundary (ctrl_t *ctrl, graph_t *graph, idx_t bndtype)
 
void ComputeKWayPartitionParams (ctrl_t *ctrl, graph_t *graph)
 
void ComputeKWayVolGains (ctrl_t *ctrl, graph_t *graph)
 
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)
 
idx_t ComputeMaxCut (graph_t *graph, idx_t nparts, idx_t *where)
 
void ComputePartitionBalance (graph_t *, idx_t, idx_t *, real_t *)
 
void ComputePartitionInfoBipartite (graph_t *, idx_t, idx_t *)
 
void ComputeSubDomainGraph (ctrl_t *ctrl, graph_t *graph)
 
idx_t ComputeVolume (graph_t *, idx_t *)
 
void ConstructMinCoverSeparator (ctrl_t *ctrl, graph_t *graph)
 
void ConstructSeparator (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_tCreateGraph (void)
 
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)
 
void CreateGraphNodal (idx_t ne, idx_t nn, idx_t *eptr, idx_t *eind, idx_t **r_xadj, idx_t **r_adjncy)
 
mesh_tCreateMesh (void)
 
void EliminateComponents (ctrl_t *ctrl, graph_t *graph)
 
void EliminateSubDomainEdges (ctrl_t *ctrl, graph_t *graph)
 
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)
 
idx_t FindCommonNodes (idx_t qid, idx_t nelmnts, idx_t *elmntids, idx_t *eptr, idx_t *eind, idx_t *marker, idx_t *nbrs)
 
idx_t FindPartitionInducedComponents (graph_t *graph, idx_t *where, idx_t *cptr, idx_t *cind)
 
idx_t FindSepInducedComponents (ctrl_t *, graph_t *, idx_t *, idx_t *)
 
graph_tFixGraph (graph_t *graph)
 
void FM_2WayCutRefine (ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niter)
 
void FM_2WayNodeBalance (ctrl_t *ctrl, graph_t *graph)
 
void FM_2WayNodeRefine1Sided (ctrl_t *ctrl, graph_t *graph, idx_t niter)
 
void FM_2WayNodeRefine1SidedP (ctrl_t *ctrl, graph_t *graph, idx_t *hmarker, real_t ubfactor, idx_t npasses)
 
void FM_2WayNodeRefine2Sided (ctrl_t *ctrl, graph_t *graph, idx_t niter)
 
void FM_2WayNodeRefine2SidedP (ctrl_t *ctrl, graph_t *graph, idx_t *hmarker, real_t ubfactor, idx_t npasses)
 
void FM_2WayRefine (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 FreeCtrl (ctrl_t **r_ctrl)
 
void FreeGraph (graph_t **graph)
 
void FreeMesh (mesh_t **mesh)
 
void FreeRData (graph_t *graph)
 
void FreeWorkSpace (ctrl_t *ctrl)
 
void General2WayBalance (ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts)
 
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 Greedy_KWayCutOptimize (ctrl_t *ctrl, graph_t *graph, idx_t niter, real_t ffactor, idx_t omode)
 
void Greedy_KWayOptimize (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)
 
void GrowBisection (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)
 
idx_t iargmax2_nrm (size_t n, idx_t *x, real_t *y)
 
idx_t iargmax_nrm (size_t n, idx_t *x, real_t *y)
 
idx_t iargmax_strd (size_t, idx_t *, idx_t)
 
ikv_t * ikvwspacemalloc (ctrl_t *, idx_t)
 
void InduceRowPartFromColumnPart (idx_t nrows, idx_t *rowptr, idx_t *rowind, idx_t *rpart, idx_t *cpart, idx_t nparts, real_t *tpwgts)
 
void Init2WayPartition (ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niparts)
 
void InitGraph (graph_t *graph)
 
void InitKWayPartitioning (ctrl_t *ctrl, graph_t *graph)
 
void InitMesh (mesh_t *mesh)
 
void InitRandom (idx_t)
 
void InitSeparator (ctrl_t *ctrl, graph_t *graph, idx_t niparts)
 
void InitTimers (ctrl_t *)
 
idx_t IsArticulationNode (idx_t i, idx_t *xadj, idx_t *adjncy, idx_t *where, idx_t *bfslvl, idx_t *bfsind, idx_t *bfsmrk)
 
int IsBalanced (ctrl_t *ctrl, graph_t *graph, real_t ffactor)
 
idx_t IsConnected (graph_t *graph, idx_t report)
 
idx_t IsConnectedSubdomain (ctrl_t *, graph_t *, idx_t, idx_t)
 
idx_t IsSeparable (graph_t *)
 
int ivecaxpygez (idx_t n, idx_t a, idx_t *x, idx_t *y, idx_t *z)
 
int ivecaxpylez (idx_t n, idx_t a, idx_t *x, idx_t *y, idx_t *z)
 
int ivecge (idx_t n, idx_t *x, idx_t *z)
 
int ivecle (idx_t n, idx_t *x, idx_t *z)
 
idx_tiwspacemalloc (ctrl_t *, idx_t)
 
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)
 
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_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_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_RM (ctrl_t *ctrl, graph_t *graph)
 
idx_t Match_SHEM (ctrl_t *ctrl, graph_t *graph)
 
void McGeneral2WayBalance (ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts)
 
void McGrowBisection (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)
 
int metis_rcode (int sigrval)
 
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_ColDFS (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_RowDFS (idx_t *, idx_t *, idx_t, idx_t *, idx_t *, idx_t)
 
idx_t MlevelKWayPartitioning (ctrl_t *ctrl, graph_t *graph, idx_t *part)
 
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 MlevelNestedDissectionP (ctrl_t *ctrl, graph_t *graph, idx_t *order, idx_t lastvtx, idx_t npes, idx_t cpos, idx_t *sizes)
 
void MlevelNodeBisectionL1 (ctrl_t *ctrl, graph_t *graph, idx_t niparts)
 
void MlevelNodeBisectionL2 (ctrl_t *ctrl, graph_t *graph, idx_t niparts)
 
void MlevelNodeBisectionMultiple (ctrl_t *ctrl, graph_t *graph)
 
idx_t MlevelRecursiveBisection (ctrl_t *ctrl, graph_t *graph, idx_t nparts, idx_t *part, real_t *tpwgts, idx_t fpart)
 
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 MMDOrder (ctrl_t *ctrl, graph_t *graph, idx_t *order, idx_t lastvtx)
 
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)
 
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)
 
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)
 
idx_t MultilevelBisect (ctrl_t *ctrl, graph_t *graph, real_t *tpwgts)
 
void Print2WayRefineStats (ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, real_t deltabal, idx_t mincutorder)
 
void PrintCGraphStats (ctrl_t *ctrl, graph_t *graph)
 
void PrintCtrl (ctrl_t *ctrl)
 
void PrintSubDomainGraph (graph_t *graph, idx_t nparts, idx_t *where)
 
void PrintTimers (ctrl_t *)
 
void Project2WayNodePartition (ctrl_t *ctrl, graph_t *graph)
 
void Project2WayPartition (ctrl_t *ctrl, graph_t *graph)
 
void ProjectKWayPartition (ctrl_t *ctrl, graph_t *graph)
 
graph_tPruneGraph (ctrl_t *ctrl, idx_t nvtxs, idx_t *xadj, idx_t *adjncy, idx_t *vwgt, idx_t *iperm, real_t factor)
 
void RandomBisection (ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niparts)
 
idx_t rargmax2 (size_t, real_t *)
 
void ReAdjustMemory (ctrl_t *ctrl, graph_t *graph, graph_t *cgraph)
 
void Refine2Way (ctrl_t *ctrl, graph_t *orggraph, graph_t *graph, real_t *rtpwgts)
 
void Refine2WayNode (ctrl_t *ctrl, graph_t *orggraph, graph_t *graph)
 
void RefineKWay (ctrl_t *ctrl, graph_t *orggraph, graph_t *graph)
 
int rvecge (idx_t n, real_t *x, real_t *y)
 
int rvecle (idx_t n, real_t *x, real_t *y)
 
real_t rvecmaxdiff (idx_t n, real_t *x, real_t *y)
 
int rvecsumle (idx_t n, real_t *x1, real_t *x2, real_t *y)
 
real_trwspacemalloc (ctrl_t *, idx_t)
 
void SelectQueue (graph_t *graph, real_t *pijbm, real_t *ubfactors, rpq_t **queues, idx_t *from, idx_t *cnum)
 
void Setup2WayBalMultipliers (ctrl_t *ctrl, graph_t *graph, real_t *tpwgts)
 
graph_tSetupCoarseGraph (graph_t *graph, idx_t cnvtxs, idx_t dovsize)
 
ctrl_tSetupCtrl (moptype_et optype, idx_t *options, idx_t ncon, idx_t nparts, real_t *tpwgts, real_t *ubvec)
 
graph_tSetupGraph (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_label (graph_t *graph)
 
void SetupGraph_tvwgt (graph_t *graph)
 
void SetupKWayBalMultipliers (ctrl_t *ctrl, graph_t *graph)
 
graph_tSetupSplitGraph (graph_t *graph, idx_t snvtxs, idx_t snedges)
 
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 SplitGraphPart (ctrl_t *ctrl, graph_t *graph, graph_t **r_lgraph, graph_t **r_rgraph)
 
void UpdateEdgeSubDomainGraph (ctrl_t *ctrl, idx_t u, idx_t v, idx_t ewgt, idx_t *r_maxndoms)
 
idx_t vnbrpoolGetNext (ctrl_t *ctrl, idx_t nnbrs)
 
void vnbrpoolReset (ctrl_t *ctrl)
 
void * wspacemalloc (ctrl_t *ctrl, size_t nbytes)
 
void wspacepop (ctrl_t *ctrl)
 
void wspacepush (ctrl_t *ctrl)
 

Function Documentation

void Allocate2WayNodePartitionMemory ( ctrl_t ctrl,
graph_t graph 
)

This function allocates memory for 2-way node-based refinement

Definition at line 66 of file srefine.c.

void Allocate2WayPartitionMemory ( ctrl_t ctrl,
graph_t graph 
)

This function allocates memory for 2-way edge refinement

Definition at line 52 of file refine.c.

void AllocateKWayPartitionMemory ( ctrl_t ctrl,
graph_t graph 
)

This function allocates memory for the k-way cut-based refinement

Definition at line 116 of file kwayrefine.c.

void AllocateRefinementWorkSpace ( ctrl_t ctrl,
idx_t  nbrpoolsize 
)

This function allocates refinement-specific memory for the workspace

Definition at line 43 of file wspace.c.

void AllocateWorkSpace ( ctrl_t ctrl,
graph_t graph 
)

This function allocates memory for the workspace

Definition at line 17 of file wspace.c.

void Balance2Way ( ctrl_t ctrl,
graph_t graph,
real_t ntpwgts 
)

Definition at line 16 of file balance.c.

int BetterBalance2Way ( idx_t  n,
real_t x,
real_t y 
)

This function takes two ubfactor-centered load imbalance vectors x & y, and returns true if y is better balanced than x.

Definition at line 169 of file mcutil.c.

int BetterBalanceKWay ( idx_t  ncon,
idx_t vwgt,
real_t ubvec,
idx_t  a1,
idx_t pt1,
real_t bm1,
idx_t  a2,
idx_t pt2,
real_t bm2 
)

Given a vertex and two weights, this function returns 1, if the second partition will be more balanced than the first after the weighted additional of that vertex. The balance determination takes into account the ideal target weights of the two partitions.

Definition at line 189 of file mcutil.c.

int BetterVBalance ( idx_t  ncon,
real_t invtvwgt,
idx_t v_vwgt,
idx_t u1_vwgt,
idx_t u2_vwgt 
)

This function checks if v+u2 provides a better balance in the weight vector that v+u1

Definition at line 143 of file mcutil.c.

void Bnd2WayBalance ( ctrl_t ctrl,
graph_t graph,
real_t ntpwgts 
)

Definition at line 41 of file balance.c.

void BucketSortKeysInc ( ctrl_t ctrl,
idx_t  n,
idx_t  max,
idx_t keys,
idx_t tperm,
idx_t perm 
)

Definition at line 23 of file bucketsort.c.

void Change2CNumbering ( idx_t  nvtxs,
idx_t xadj,
idx_t adjncy 
)

This function changes the numbering to start from 0 instead of 1

Definition at line 19 of file fortran.c.

void Change2FNumbering ( idx_t  nvtxs,
idx_t xadj,
idx_t adjncy,
idx_t vector 
)

This function changes the numbering to start from 1 instead of 0

Definition at line 34 of file fortran.c.

void Change2FNumbering2 ( idx_t  nvtxs,
idx_t xadj,
idx_t adjncy 
)

This function changes the numbering to start from 1 instead of 0

Definition at line 51 of file fortran.c.

void Change2FNumberingOrder ( idx_t  nvtxs,
idx_t xadj,
idx_t adjncy,
idx_t v1,
idx_t v2 
)

This function changes the numbering to start from 1 instead of 0

Definition at line 68 of file fortran.c.

void ChangeMesh2CNumbering ( idx_t  n,
idx_t ptr,
idx_t ind 
)

This function changes the numbering to start from 0 instead of 1

Definition at line 92 of file fortran.c.

void ChangeMesh2FNumbering ( idx_t  n,
idx_t ptr,
idx_t ind,
idx_t  nvtxs,
idx_t xadj,
idx_t adjncy 
)

This function changes the numbering to start from 1 instead of 0

Definition at line 106 of file fortran.c.

void ChangeMesh2FNumbering2 ( idx_t  ne,
idx_t  nn,
idx_t ptr,
idx_t ind,
idx_t epart,
idx_t npart 
)

This function changes the numbering to start from 1 instead of 0

Definition at line 126 of file fortran.c.

idx_t CheckBnd ( graph_t graph)

This function checks whether or not the boundary information is correct

Definition at line 121 of file debug.c.

idx_t CheckBnd2 ( graph_t graph)

This function checks whether or not the boundary information is correct

Definition at line 158 of file debug.c.

int CheckGraph ( graph_t graph,
int  numflag,
int  verbose 
)

This function checks if a graph is valid. A valid graph must satisfy the following constraints:

  • It should contain no self-edges.
  • It should be undirected; i.e., (u,v) and (v,u) should be present.
  • The adjacency list should not contain multiple edges to the same other vertex.
Parameters
graphis the graph to be checked, whose numbering starts from 0.
numflagis 0 if error reporting will be done using 0 as the numbering, or 1 if the reporting should be done using 1.
verboseis 1 the identified errors will be displayed, or 0, if it should run silently.

Definition at line 32 of file checkgraph.c.

int CheckInputGraphWeights ( idx_t  nvtxs,
idx_t  ncon,
idx_t xadj,
idx_t adjncy,
idx_t vwgt,
idx_t vsize,
idx_t adjwgt 
)

This function performs a quick check of the weights of the graph

Definition at line 120 of file checkgraph.c.

void CheckKWayVolPartitionParams ( ctrl_t ctrl,
graph_t graph 
)

This function recomputes the vrinfo fields and checks them against those in the graph->vrinfo structure

Definition at line 339 of file debug.c.

idx_t CheckNodeBnd ( graph_t graph,
idx_t  onbnd 
)

This function checks whether or not the boundary information is correct

Definition at line 195 of file debug.c.

idx_t CheckNodePartitionParams ( graph_t graph)

This function checks the correctness of the NodeFM data structures

Definition at line 255 of file debug.c.

int CheckParams ( ctrl_t ctrl)

This function checks the validity of user-supplied parameters

Definition at line 287 of file options.c.

idx_t CheckRInfo ( ctrl_t ctrl,
ckrinfo_t rinfo 
)

This function checks whether or not the rinfo of a vertex is consistent

Definition at line 232 of file debug.c.

idx_t cnbrpoolGetNext ( ctrl_t ctrl,
idx_t  nnbrs 
)

This function gets the next free index from cnbrpool

Definition at line 172 of file wspace.c.

void cnbrpoolReset ( ctrl_t ctrl)

This function resets the cnbrpool

Definition at line 163 of file wspace.c.

graph_t* CoarsenGraph ( ctrl_t ctrl,
graph_t graph 
)

This function takes a graph and creates a sequence of coarser graphs. It implements the coarsening phase of the multilevel paradigm.

Definition at line 22 of file coarsen.c.

graph_t* CoarsenGraphNlevels ( ctrl_t ctrl,
graph_t graph,
idx_t  nlevels 
)

This function takes a graph and creates a sequence of nlevels coarser graphs, where nlevels is an input parameter.

Definition at line 85 of file coarsen.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 
)

This function compresses a graph by merging identical vertices The compression should lead to at least 10% reduction.

The compressed graph that is generated has its adjwgts set to 1.

Returns
1 if compression was performed, otherwise it returns 0.

Definition at line 25 of file compress.c.

void Compute2WayNodePartitionParams ( ctrl_t ctrl,
graph_t graph 
)

This function computes the edegrees[] to the left & right sides

Definition at line 83 of file srefine.c.

void Compute2WayPartitionParams ( ctrl_t ctrl,
graph_t graph 
)

This function computes the initial id/ed

Definition at line 71 of file refine.c.

void ComputeBFSOrdering ( ctrl_t ctrl,
graph_t graph,
idx_t bfsperm 
)

This function computes a permutation of the vertices based on a breadth-first-traversal. It can be used for re-ordering the graph to reduce its bandwidth for better cache locality.

Parameters
ctrlis the control structure
graphis the graph structure
permis the array that upon completion, perm[i] will store the ID of the vertex that corresponds to the ith vertex in the re-ordered graph.

Definition at line 115 of file contig.c.

idx_t ComputeCut ( graph_t graph,
idx_t where 
)

This function computes the total edgecut

Definition at line 21 of file debug.c.

real_t ComputeElementBalance ( idx_t  ,
idx_t  ,
idx_t  
)

Definition at line 160 of file libmetis/stat.c.

void ComputeKWayBoundary ( ctrl_t ctrl,
graph_t graph,
idx_t  bndtype 
)

This function computes the boundary definition for balancing.

Definition at line 507 of file kwayrefine.c.

void ComputeKWayPartitionParams ( ctrl_t ctrl,
graph_t graph 
)

This function computes the initial id/ed for cut-based partitioning

Definition at line 149 of file kwayrefine.c.

void ComputeKWayVolGains ( ctrl_t ctrl,
graph_t graph 
)

This function computes the initial gains in the communication volume

Definition at line 562 of file kwayrefine.c.

real_t ComputeLoadImbalance ( graph_t graph,
idx_t  nparts,
real_t pijbm 
)

Computes the maximum load imbalance of a partitioning solution over all the constraints.

Definition at line 228 of file mcutil.c.

real_t ComputeLoadImbalanceDiff ( graph_t graph,
idx_t  nparts,
real_t pijbm,
real_t ubvec 
)

Computes the maximum load imbalance difference of a partitioning solution over all the constraints. The difference is defined with respect to the allowed maximum unbalance for the respective constraint.

Definition at line 256 of file mcutil.c.

real_t ComputeLoadImbalanceDiffVec ( graph_t graph,
idx_t  nparts,
real_t pijbm,
real_t ubfactors,
real_t diffvec 
)

Computes the difference between load imbalance of each constraint across the partitions minus the desired upper bound on the load imabalnce. It also returns the maximum load imbalance across the partitions & constraints.

Definition at line 284 of file mcutil.c.

void ComputeLoadImbalanceVec ( graph_t graph,
idx_t  nparts,
real_t pijbm,
real_t lbvec 
)

Computes the load imbalance of each constraint across the partitions.

Definition at line 311 of file mcutil.c.

idx_t ComputeMaxCut ( graph_t graph,
idx_t  nparts,
idx_t where 
)

This function computes the cut given the graph and a where vector

Definition at line 85 of file debug.c.

void ComputePartitionBalance ( graph_t ,
idx_t  ,
idx_t ,
real_t  
)

Definition at line 125 of file libmetis/stat.c.

void ComputePartitionInfoBipartite ( graph_t ,
idx_t  ,
idx_t  
)

Definition at line 21 of file libmetis/stat.c.

void ComputeSubDomainGraph ( ctrl_t ctrl,
graph_t graph 
)

This function computes the subdomain graph storing the result in the pre-allocated worspace arrays

Definition at line 18 of file minconn.c.

idx_t ComputeVolume ( graph_t graph,
idx_t where 
)

This function computes the total volume

Definition at line 48 of file debug.c.

void ConstructMinCoverSeparator ( ctrl_t ctrl,
graph_t graph 
)

Definition at line 69 of file separator.c.

void ConstructSeparator ( ctrl_t ctrl,
graph_t graph 
)

Definition at line 21 of file separator.c.

void CreateCoarseGraph ( ctrl_t ctrl,
graph_t graph,
idx_t  cnvtxs,
idx_t match 
)

This function creates the coarser graph. It uses a simple hash-table for identifying the adjacent vertices that get collapsed to the same node. The hash-table can have conflicts, which are handled via a linear scan.

Definition at line 621 of file coarsen.c.

void CreateCoarseGraphNoMask ( ctrl_t ctrl,
graph_t graph,
idx_t  cnvtxs,
idx_t match 
)

This function creates the coarser graph. It uses a full-size array (htable) for identifying the adjacent vertices that get collapsed to the same node.

Definition at line 800 of file coarsen.c.

void CreateCoarseGraphPerm ( ctrl_t ctrl,
graph_t graph,
idx_t  cnvtxs,
idx_t match,
idx_t perm 
)

This function creates the coarser graph. It uses a simple hash-table for identifying the adjacent vertices that get collapsed to the same node. The hash-table can have conflicts, which are handled via a linear scan. It relies on the perm[] array to visit the vertices in increasing cnvtxs order.

Definition at line 932 of file coarsen.c.

graph_t* CreateGraph ( void  )

This function creates and initializes a graph_t data structure

Definition at line 162 of file libmetis/graph.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 
)

This function creates the dual of a finite element mesh

Definition at line 162 of file mesh.c.

void CreateGraphNodal ( idx_t  ne,
idx_t  nn,
idx_t eptr,
idx_t eind,
idx_t **  r_xadj,
idx_t **  r_adjncy 
)

This function creates the (almost) nodal of a finite element mesh

Definition at line 277 of file mesh.c.

mesh_t* CreateMesh ( void  )

This function creates and initializes a mesh_t structure

Definition at line 380 of file mesh.c.

void EliminateComponents ( ctrl_t ctrl,
graph_t graph 
)

This function finds all the connected components induced by the partitioning vector in graph->where and tries to push them around to remove some of them.

Definition at line 336 of file contig.c.

void EliminateSubDomainEdges ( ctrl_t ctrl,
graph_t graph 
)

This function computes the subdomain graph

Definition at line 192 of file minconn.c.

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 
)

This function finds all elements that share at least ncommon nodes with the ``query'' element.

Definition at line 237 of file mesh.c.

idx_t FindCommonNodes ( idx_t  qid,
idx_t  nelmnts,
idx_t elmntids,
idx_t eptr,
idx_t eind,
idx_t marker,
idx_t nbrs 
)

This function finds the union of nodes that are in the same elements with the ``query'' node.

Definition at line 348 of file mesh.c.

idx_t FindPartitionInducedComponents ( graph_t graph,
idx_t where,
idx_t cptr,
idx_t cind 
)

This function finds the connected components induced by the partitioning vector.

Parameters
graphis the graph structure
whereis the partitioning vector. If this is NULL, then the entire graph is treated to belong into a single partition.
cptris the ptr structure of the CSR representation of the components. The length of this vector must be graph->nvtxs+1.
cindis the indices structure of the CSR representation of the components. The length of this vector must be graph->nvtxs.
Returns
the number of components that it found.
Note
The cptr and cind parameters can be NULL, in which case only the number of connected components is returned.

Definition at line 32 of file contig.c.

idx_t FindSepInducedComponents ( ctrl_t ctrl,
graph_t graph,
idx_t cptr,
idx_t cind 
)

This function identifies the number of connected components in a graph that result after removing the vertices that belong to the vertex separator (i.e., graph->where[i] == 2). The connected component memberships are returned in the CSR-style pair of arrays cptr, cind.

Definition at line 267 of file contig.c.

graph_t* FixGraph ( graph_t graph)

This function creates a graph whose topology is consistent with Metis' requirements that:

  • There are no self-edges.
  • It is undirected; i.e., (u,v) and (v,u) should be present and of the same weight.
  • The adjacency list should not contain multiple edges to the same other vertex.

Any of the above errors are fixed by performing the following operations:

  • Self-edges are removed.
  • The undirected graph is formed by the union of edges.
  • One of the duplicate edges is selected.

The routine does not change the provided vertex weights.

Definition at line 176 of file checkgraph.c.

void FM_2WayCutRefine ( ctrl_t ctrl,
graph_t graph,
real_t ntpwgts,
idx_t  niter 
)

This function performs a cut-focused FM refinement

Definition at line 29 of file fm.c.

void FM_2WayNodeBalance ( ctrl_t ctrl,
graph_t graph 
)

This function balances the left/right partitions of a separator tri-section

Definition at line 476 of file sfm.c.

void FM_2WayNodeRefine1Sided ( ctrl_t ctrl,
graph_t graph,
idx_t  niter 
)

This function performs a node-based FM refinement. Each refinement iteration is split into two sub-iterations. In each sub-iteration only moves to one of the left/right partitions is allowed; hence, it is one-sided.

Definition at line 263 of file sfm.c.

void FM_2WayNodeRefine1SidedP ( ctrl_t ctrl,
graph_t graph,
idx_t hmarker,
real_t  ubfactor,
idx_t  npasses 
)

This function performs a node-based 1-sided FM refinement that moves only nodes whose hmarker[] == -1. It is used by Parmetis.

Definition at line 237 of file parmetis.c.

void FM_2WayNodeRefine2Sided ( ctrl_t ctrl,
graph_t graph,
idx_t  niter 
)

This function performs a node-based FM refinement

Definition at line 21 of file sfm.c.

void FM_2WayNodeRefine2SidedP ( ctrl_t ctrl,
graph_t graph,
idx_t hmarker,
real_t  ubfactor,
idx_t  npasses 
)

This function performs a node-based (two-sided) FM refinement that moves only nodes whose hmarker[] == -1. It is used by Parmetis.

Definition at line 467 of file parmetis.c.

void FM_2WayRefine ( ctrl_t ctrl,
graph_t graph,
real_t ntpwgts,
idx_t  niter 
)

Definition at line 17 of file fm.c.

void FM_Mc2WayCutRefine ( ctrl_t ctrl,
graph_t graph,
real_t ntpwgts,
idx_t  niter 
)

This function performs a cut-focused multi-constraint FM refinement

Definition at line 207 of file fm.c.

void FreeCtrl ( ctrl_t **  r_ctrl)

This function frees the memory associated with a ctrl_t

Definition at line 520 of file options.c.

void FreeGraph ( graph_t **  r_graph)

This function deallocates any memory stored in a graph

Definition at line 247 of file libmetis/graph.c.

void FreeMesh ( mesh_t **  r_mesh)

This function deallocates any memory stored in a mesh

Definition at line 404 of file mesh.c.

void FreeRData ( graph_t graph)

This function frees the refinement/partition memory stored in a graph

Definition at line 228 of file libmetis/graph.c.

void FreeWorkSpace ( ctrl_t ctrl)

This function frees the workspace

Definition at line 80 of file wspace.c.

void General2WayBalance ( ctrl_t ctrl,
graph_t graph,
real_t ntpwgts 
)

Definition at line 169 of file balance.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  
)

Definition at line 53 of file mmd.c.

void Greedy_KWayCutOptimize ( ctrl_t ctrl,
graph_t graph,
idx_t  niter,
real_t  ffactor,
idx_t  omode 
)

K-way partitioning optimization in which the vertices are visited in decreasing ed/sqrt(nnbrs)-id order. Note this is just an approximation, as the ed is often split across different subdomains and the sqrt(nnbrs) is just a crude approximation.

Parameters
graphis the graph that is being refined.
niteris the number of refinement iterations.
ffactoris the fudge-factor for allowing positive gain moves to violate the max-pwgt constraint.
omodeis the type of optimization that will performed among OMODE_REFINE and OMODE_BALANCE

Definition at line 60 of file kwayfm.c.

void Greedy_KWayOptimize ( ctrl_t ctrl,
graph_t graph,
idx_t  niter,
real_t  ffactor,
idx_t  omode 
)

Definition at line 20 of file kwayfm.c.

void Greedy_KWayVolOptimize ( ctrl_t ctrl,
graph_t graph,
idx_t  niter,
real_t  ffactor,
idx_t  omode 
)

K-way refinement that minimizes the communication volume. This is a greedy routine and the vertices are visited in decreasing gv order.

Parameters
graphis the graph that is being refined.
niteris the number of refinement iterations.
ffactoris the fudge-factor for allowing positive gain moves to violate the max-pwgt constraint.

Definition at line 370 of file kwayfm.c.

void Greedy_McKWayCutOptimize ( ctrl_t ctrl,
graph_t graph,
idx_t  niter,
real_t  ffactor,
idx_t  omode 
)

K-way partitioning optimization in which the vertices are visited in decreasing ed/sqrt(nnbrs)-id order. Note this is just an approximation, as the ed is often split across different subdomains and the sqrt(nnbrs) is just a crude approximation.

Parameters
graphis the graph that is being refined.
niteris the number of refinement iterations.
ffactoris the fudge-factor for allowing positive gain moves to violate the max-pwgt constraint.
omodeis the type of optimization that will performed among OMODE_REFINE and OMODE_BALANCE

Definition at line 684 of file kwayfm.c.

void Greedy_McKWayVolOptimize ( ctrl_t ctrl,
graph_t graph,
idx_t  niter,
real_t  ffactor,
idx_t  omode 
)

K-way refinement that minimizes the communication volume. This is a greedy routine and the vertices are visited in decreasing gv order.

Parameters
graphis the graph that is being refined.
niteris the number of refinement iterations.
ffactoris the fudge-factor for allowing positive gain moves to violate the max-pwgt constraint.

Definition at line 1026 of file kwayfm.c.

void GrowBisection ( ctrl_t ctrl,
graph_t graph,
real_t ntpwgts,
idx_t  niparts 
)

This function takes a graph and produces a bisection by using a region growing algorithm. The resulting bisection is refined using FM. The resulting partition is returned in graph->where.

Definition at line 189 of file initpart.c.

void GrowBisectionNode ( ctrl_t ctrl,
graph_t graph,
real_t ntpwgts,
idx_t  niparts 
)

Definition at line 433 of file initpart.c.

void GrowBisectionNode2 ( ctrl_t ctrl,
graph_t graph,
real_t ntpwgts,
idx_t  niparts 
)

Definition at line 570 of file initpart.c.

idx_t iargmax2_nrm ( size_t  n,
idx_t x,
real_t y 
)

These functions return the index of the second largest elements in the vector formed by x.y where '.' is element-wise multiplication

Definition at line 93 of file libmetis/util.c.

idx_t iargmax_nrm ( size_t  n,
idx_t x,
real_t y 
)

Returns the highest weight index of x[i]*y[i]

Definition at line 31 of file libmetis/util.c.

idx_t iargmax_strd ( size_t  n,
idx_t x,
idx_t  incx 
)

These functions return the index of the maximum element in a vector

Definition at line 46 of file libmetis/util.c.

ikv_t* ikvwspacemalloc ( ctrl_t ctrl,
idx_t  n 
)

This function allocate space from the core

Definition at line 154 of file wspace.c.

void InduceRowPartFromColumnPart ( idx_t  nrows,
idx_t rowptr,
idx_t rowind,
idx_t rpart,
idx_t cpart,
idx_t  nparts,
real_t tpwgts 
)

Induces a partitioning of the rows based on a a partitioning of the columns. It is used by both the Nodal and Dual routines.

Definition at line 179 of file meshpart.c.

void Init2WayPartition ( ctrl_t ctrl,
graph_t graph,
real_t ntpwgts,
idx_t  niparts 
)

This function computes the initial bisection of the coarsest graph

Definition at line 19 of file initpart.c.

void InitGraph ( graph_t graph)

This function initializes a graph_t data structure

Definition at line 177 of file libmetis/graph.c.

void InitKWayPartitioning ( ctrl_t ctrl,
graph_t graph 
)

This function computes the initial k-way partitioning using PMETIS

Definition at line 172 of file kmetis.c.

void InitMesh ( mesh_t mesh)

This function initializes a mesh_t data structure

Definition at line 395 of file mesh.c.

void InitRandom ( idx_t  seed)

This function initializes the random number generator

Definition at line 21 of file libmetis/util.c.

void InitSeparator ( ctrl_t ctrl,
graph_t graph,
idx_t  niparts 
)

This function computes the initial separator of the coarsest graph

Definition at line 67 of file initpart.c.

void InitTimers ( ctrl_t )

Definition at line 21 of file timing.c.

idx_t IsArticulationNode ( idx_t  i,
idx_t xadj,
idx_t adjncy,
idx_t where,
idx_t bfslvl,
idx_t bfsind,
idx_t bfsmrk 
)

This function performs an approximate articulation vertex test. It assumes that the bfslvl, bfsind, and bfsmrk arrays are initialized appropriately.

Definition at line 1361 of file kwayfm.c.

int IsBalanced ( ctrl_t ctrl,
graph_t graph,
real_t  ffactor 
)

This function checks if the partition weights are within the balance contraints

Definition at line 666 of file kwayrefine.c.

idx_t IsConnected ( graph_t graph,
idx_t  report 
)

This function checks whether a graph is contiguous or not.

Definition at line 167 of file contig.c.

idx_t IsConnectedSubdomain ( ctrl_t ctrl,
graph_t graph,
idx_t  pid,
idx_t  report 
)

This function checks whether or not partition pid is contigous

Definition at line 184 of file contig.c.

idx_t IsSeparable ( graph_t graph)

This function checks if the separator is indeed a separator

Definition at line 309 of file debug.c.

int ivecaxpygez ( idx_t  n,
idx_t  a,
idx_t x,
idx_t y,
idx_t z 
)

This function returns true if i, a*x[i]+y[i] >= z[i].

Definition at line 128 of file mcutil.c.

int ivecaxpylez ( idx_t  n,
idx_t  a,
idx_t x,
idx_t y,
idx_t z 
)

This function returns true if i, a*x[i]+y[i] <= z[i].

Definition at line 114 of file mcutil.c.

int ivecge ( idx_t  n,
idx_t x,
idx_t z 
)

This function returns true if i, x[i] >= z[i].

Definition at line 100 of file mcutil.c.

int ivecle ( idx_t  n,
idx_t x,
idx_t z 
)

This function returns true if i, x[i] <= z[i].

Definition at line 86 of file mcutil.c.

idx_t* iwspacemalloc ( ctrl_t ctrl,
idx_t  n 
)

This function allocate space from the core

Definition at line 136 of file wspace.c.

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 
)

This function updates the edge and volume gains due to a vertex movement. v from 'from' to 'to'.

Parameters
ctrlis the control structure.
graphis the graph being partitioned.
vis the vertex that is moving.
fromis the original partition of v.
tois the new partition of v.
queueis the priority queue. If the queue is NULL, no priority-queue related updates are performed.
vstatusis an array that marks the status of the vertex in terms of the priority queue. If queue is NULL, this parameter is ignored.
r_nqupdis the number of vertices that have been inserted/removed from the queue. If queue is NULL, this parameter is ignored.
updptrstores the index of each vertex in updind. If queue is NULL, this parameter is ignored.
updindis the list of vertices that have been inserted/removed from the queue. If queue is NULL, this parameter is ignored.
vmarkeris of size nvtxs and is used internally as a temporary array. On entry and return all of its entries are 0.
pmarkeris of sie nparts and is used internally as a temporary marking array. On entry and return all of its entries are -1.
modindis an array of size nvtxs and is used to keep track of the list of vertices whose gains need to be updated.

Definition at line 1460 of file kwayfm.c.

idx_t Match_2Hop ( ctrl_t ctrl,
graph_t graph,
idx_t perm,
idx_t match,
idx_t  cnvtxs,
size_t  nunmatched 
)

This function matches the unmatched vertices using a 2-hop matching that involves vertices that are two hops away from each other.

Definition at line 415 of file coarsen.c.

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 
)

This function matches the unmatched vertices whose degree is less than maxdegree using a 2-hop matching that involves vertices that are two hops away from each other. The requirement of the 2-hop matching is that of identical adjacency lists.

Definition at line 516 of file coarsen.c.

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 
)

This function matches the unmatched vertices whose degree is less than maxdegree using a 2-hop matching that involves vertices that are two hops away from each other. The requirement of the 2-hop matching is a simple non-empty overlap between the adjancency lists of the vertices.

Definition at line 437 of file coarsen.c.

idx_t Match_RM ( ctrl_t ctrl,
graph_t graph 
)

This function finds a matching by randomly selecting one of the unmatched adjacent vertices.

Definition at line 149 of file coarsen.c.

idx_t Match_SHEM ( ctrl_t ctrl,
graph_t graph 
)

This function finds a matching using the HEM heuristic. The vertices are visited based on increasing degree to ensure that all vertices are given a chance to match with something.

Definition at line 276 of file coarsen.c.

void McGeneral2WayBalance ( ctrl_t ctrl,
graph_t graph,
real_t ntpwgts 
)

Definition at line 281 of file balance.c.

void McGrowBisection ( ctrl_t ctrl,
graph_t graph,
real_t ntpwgts,
idx_t  niparts 
)

This function takes a multi-constraint graph and produces a bisection by using a region growing algorithm. The resulting partition is returned in graph->where.

Definition at line 385 of file initpart.c.

void McRandomBisection ( ctrl_t ctrl,
graph_t graph,
real_t ntpwgts,
idx_t  niparts 
)

This function takes a multi-constraint graph and computes a bisection by randomly assigning the vertices and then refining it. The resulting partition is returned in graph->where.

Definition at line 325 of file initpart.c.

int metis_rcode ( int  sigrval)

converts a signal code into a Metis return code

Definition at line 123 of file libmetis/util.c.

void MinCover ( idx_t ,
idx_t ,
idx_t  ,
idx_t  ,
idx_t ,
idx_t  
)

Definition at line 42 of file mincover.c.

idx_t MinCover_Augment ( idx_t ,
idx_t ,
idx_t  ,
idx_t ,
idx_t ,
idx_t ,
idx_t   
)

Definition at line 126 of file mincover.c.

void MinCover_ColDFS ( idx_t ,
idx_t ,
idx_t  ,
idx_t ,
idx_t ,
idx_t   
)

Definition at line 212 of file mincover.c.

void MinCover_Decompose ( idx_t ,
idx_t ,
idx_t  ,
idx_t  ,
idx_t ,
idx_t ,
idx_t  
)

Definition at line 163 of file mincover.c.

void MinCover_RowDFS ( idx_t ,
idx_t ,
idx_t  ,
idx_t ,
idx_t ,
idx_t   
)

Definition at line 237 of file mincover.c.

idx_t MlevelKWayPartitioning ( ctrl_t ctrl,
graph_t graph,
idx_t part 
)

This function computes a k-way partitioning of a graph that minimizes the specified objective function.

Parameters
ctrlis the control structure
graphis the graph to be partitioned
partis the vector that on return will store the partitioning
Returns
the objective value of the partitoning. The partitioning itself is stored in the part vector.

Definition at line 103 of file kmetis.c.

void MlevelNestedDissection ( ctrl_t ctrl,
graph_t graph,
idx_t order,
idx_t  lastvtx 
)

This is the driver for the recursive tri-section of a graph into the left, separator, and right partitions. The graphs correspond to the left and right parts are further tri-sected in a recursive fashion. The nodes in the separator are ordered at the end of the left & right nodes.

Definition at line 183 of file ometis.c.

void MlevelNestedDissectionCC ( ctrl_t ctrl,
graph_t graph,
idx_t order,
idx_t  lastvtx 
)

This routine is similar to its non 'CC' counterpart. The difference is that after each tri-section, the connected components of the original graph that result after removing the separator vertises are ordered independently (i.e., this may lead to more than just the left and the right subgraphs).

Definition at line 236 of file ometis.c.

void MlevelNestedDissectionP ( ctrl_t ctrl,
graph_t graph,
idx_t order,
idx_t  lastvtx,
idx_t  npes,
idx_t  cpos,
idx_t sizes 
)

This function is similar to MlevelNestedDissection with the difference that it also records separator sizes for the top log2(npes) levels

Definition at line 105 of file parmetis.c.

void MlevelNodeBisectionL1 ( ctrl_t ctrl,
graph_t graph,
idx_t  niparts 
)

The top-level routine of the actual multilevel node bisection

Definition at line 395 of file ometis.c.

void MlevelNodeBisectionL2 ( ctrl_t ctrl,
graph_t graph,
idx_t  niparts 
)

This function performs multilevel node bisection (i.e., tri-section). It performs multiple bisections and selects the best.

Definition at line 345 of file ometis.c.

void MlevelNodeBisectionMultiple ( ctrl_t ctrl,
graph_t graph 
)

This function performs multilevel node bisection (i.e., tri-section). It performs multiple bisections and selects the best.

Definition at line 300 of file ometis.c.

idx_t MlevelRecursiveBisection ( ctrl_t ctrl,
graph_t graph,
idx_t  nparts,
idx_t part,
real_t tpwgts,
idx_t  fpart 
)

This function is the top-level driver of the recursive bisection routine.

Definition at line 157 of file pmetis.c.

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   
)

Definition at line 171 of file mmd.c.

idx_t mmdint ( idx_t  ,
idx_t xadj,
idx_t ,
idx_t ,
idx_t ,
idx_t ,
idx_t ,
idx_t ,
idx_t  
)

Definition at line 305 of file mmd.c.

void mmdnum ( idx_t  ,
idx_t ,
idx_t ,
idx_t  
)

Definition at line 348 of file mmd.c.

void MMDOrder ( ctrl_t ctrl,
graph_t graph,
idx_t order,
idx_t  lastvtx 
)

This function uses MMD to order the graph. The vertices are numbered from lastvtx downwards.

Definition at line 655 of file ometis.c.

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 
)

Definition at line 412 of file mmd.c.

void MoveGroupContigForCut ( ctrl_t ctrl,
graph_t graph,
idx_t  to,
idx_t  gid,
idx_t ptr,
idx_t ind 
)

This function moves a collection of vertices and updates their rinfo

Definition at line 531 of file contig.c.

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 
)

This function moves a collection of vertices and updates their rinfo

Definition at line 601 of file contig.c.

void MoveGroupMinConnForCut ( ctrl_t ctrl,
graph_t graph,
idx_t  to,
idx_t  nind,
idx_t ind 
)

This function moves a collection of vertices and updates their rinfo

Definition at line 477 of file minconn.c.

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 
)

This function moves a collection of vertices and updates their rinfo

Definition at line 561 of file minconn.c.

idx_t MultilevelBisect ( ctrl_t ctrl,
graph_t graph,
real_t tpwgts 
)

This function performs a multilevel bisection

Definition at line 226 of file pmetis.c.

void Print2WayRefineStats ( ctrl_t ctrl,
graph_t graph,
real_t ntpwgts,
real_t  deltabal,
idx_t  mincutorder 
)

Prints statistics about the refinement

Definition at line 515 of file fm.c.

void PrintCGraphStats ( ctrl_t ctrl,
graph_t graph 
)

This function prints various stats for each graph during coarsening

Definition at line 601 of file coarsen.c.

void PrintCtrl ( ctrl_t ctrl)

This function prints the various control fields

Definition at line 168 of file options.c.

void PrintSubDomainGraph ( graph_t graph,
idx_t  nparts,
idx_t where 
)

This function computes the subdomain graph. For deubuging purposes.

Definition at line 683 of file minconn.c.

void PrintTimers ( ctrl_t )

Definition at line 42 of file timing.c.

void Project2WayNodePartition ( ctrl_t ctrl,
graph_t graph 
)

This function projects the node-based bisection

Definition at line 137 of file srefine.c.

void Project2WayPartition ( ctrl_t ctrl,
graph_t graph 
)

Projects a partition and computes the refinement params.

Definition at line 141 of file refine.c.

void ProjectKWayPartition ( ctrl_t ctrl,
graph_t graph 
)

This function projects a partition, and at the same time computes the parameters for refinement.

Definition at line 315 of file kwayrefine.c.

graph_t* PruneGraph ( ctrl_t ctrl,
idx_t  nvtxs,
idx_t xadj,
idx_t adjncy,
idx_t vwgt,
idx_t iperm,
real_t  factor 
)

This function prunes all the vertices in a graph with degree greater than factor*average.

Returns
the number of vertices that were prunned.

Definition at line 150 of file compress.c.

void RandomBisection ( ctrl_t ctrl,
graph_t graph,
real_t ntpwgts,
idx_t  niparts 
)

This function computes a bisection of a graph by randomly assigning the vertices followed by a bisection refinement. The resulting partition is returned in graph->where.

Definition at line 114 of file initpart.c.

idx_t rargmax2 ( size_t  n,
real_t x 
)

These functions return the index of the almost maximum element in a vector

Definition at line 63 of file libmetis/util.c.

void ReAdjustMemory ( ctrl_t ctrl,
graph_t graph,
graph_t cgraph 
)

This function re-adjusts the amount of memory that was allocated if it will lead to significant savings

Definition at line 1126 of file coarsen.c.

void Refine2Way ( ctrl_t ctrl,
graph_t orggraph,
graph_t graph,
real_t tpwgts 
)

This function is the entry point of refinement

Definition at line 17 of file refine.c.

void Refine2WayNode ( ctrl_t ctrl,
graph_t orggraph,
graph_t graph 
)

This function is the entry point of the separator refinement. It does not perform any refinement on graph, but it starts by first projecting it to the next level finer graph and proceeds from there.

Definition at line 23 of file srefine.c.

void RefineKWay ( ctrl_t ctrl,
graph_t orggraph,
graph_t graph 
)

This function is the entry point of cut-based refinement

Definition at line 17 of file kwayrefine.c.

int rvecge ( idx_t  n,
real_t x,
real_t y 
)

This function compares two vectors x & y and returns true if i, x[i] >= y[i].

Definition at line 38 of file mcutil.c.

int rvecle ( idx_t  n,
real_t x,
real_t y 
)

This function compares two vectors x & y and returns true if i, x[i] <= y[i].

Definition at line 22 of file mcutil.c.

real_t rvecmaxdiff ( idx_t  n,
real_t x,
real_t y 
)

This function returns max_i(x[i]-y[i])

Definition at line 68 of file mcutil.c.

int rvecsumle ( idx_t  n,
real_t x1,
real_t x2,
real_t y 
)

This function compares vectors x1+x2 against y and returns true if i, x1[i]+x2[i] <= y[i].

Definition at line 54 of file mcutil.c.

real_t* rwspacemalloc ( ctrl_t ctrl,
idx_t  n 
)

This function allocate space from the core

Definition at line 145 of file wspace.c.

void SelectQueue ( graph_t graph,
real_t pijbm,
real_t ubfactors,
rpq_t **  queues,
idx_t from,
idx_t cnum 
)

This function selects the partition number and the queue from which we will move vertices out.

Definition at line 439 of file fm.c.

void Setup2WayBalMultipliers ( ctrl_t ctrl,
graph_t graph,
real_t tpwgts 
)

Computes the per-partition/constraint balance multipliers

Definition at line 154 of file options.c.

graph_t* SetupCoarseGraph ( graph_t graph,
idx_t  cnvtxs,
idx_t  dovsize 
)

Setup the various arrays for the coarse graph

Definition at line 1093 of file coarsen.c.

ctrl_t* SetupCtrl ( moptype_et  optype,
idx_t options,
idx_t  ncon,
idx_t  nparts,
real_t tpwgts,
real_t ubvec 
)

This function creates and sets the run parameters (ctrl_t)

Definition at line 17 of file options.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 
)

This function sets up the graph from the user input

Definition at line 17 of file libmetis/graph.c.

void SetupGraph_label ( graph_t graph)

Set's up the label info

Definition at line 118 of file libmetis/graph.c.

void SetupGraph_tvwgt ( graph_t graph)

Set's up the tvwgt/invtvwgt info

Definition at line 99 of file libmetis/graph.c.

void SetupKWayBalMultipliers ( ctrl_t ctrl,
graph_t graph 
)

Computes the per-partition/constraint balance multipliers

Definition at line 140 of file options.c.

graph_t* SetupSplitGraph ( graph_t graph,
idx_t  snvtxs,
idx_t  snedges 
)

Setup the various arrays for the splitted graph

Definition at line 133 of file libmetis/graph.c.

void SplitGraphOrder ( ctrl_t ctrl,
graph_t graph,
graph_t **  r_lgraph,
graph_t **  r_rgraph 
)

This function takes a graph and a tri-section (left, right, separator) and splits it into two graphs.

This function relies on the fact that adjwgt is all equal to 1.

Definition at line 422 of file ometis.c.

graph_t** SplitGraphOrderCC ( ctrl_t ctrl,
graph_t graph,
idx_t  ncmps,
idx_t cptr,
idx_t cind 
)

This function takes a graph and generates a set of graphs, each of which is a connected component in the original graph.

This function relies on the fact that adjwgt is all equal to 1.

Parameters
ctrlstores run state info.
graphis the graph to be split.
ncmpsis the number of connected components.
cptris an array of size ncmps+1 that marks the start and end locations of the vertices in cind that make up the respective components (i.e., cptr, cind is in CSR format).
cindis an array of size equal to the number of vertices in the original graph and stores the vertices that belong to each connected component.
Returns
an array of subgraphs corresponding to the extracted subgraphs.

Definition at line 552 of file ometis.c.

void SplitGraphPart ( ctrl_t ctrl,
graph_t graph,
graph_t **  r_lgraph,
graph_t **  r_rgraph 
)

This function splits a graph into two based on its bisection

Definition at line 280 of file pmetis.c.

void UpdateEdgeSubDomainGraph ( ctrl_t ctrl,
idx_t  u,
idx_t  v,
idx_t  ewgt,
idx_t r_maxndoms 
)

This function updates the weight of an edge in the subdomain graph by adding to it the value of ewgt. The update can either increase or decrease the weight of the subdomain edge based on the value of ewgt.

Parameters
uis the ID of one of the incident subdomains to the edge
vis the ID of the other incident subdomains to the edge
ewgtis the weight to be added to the subdomain edge
npartsis the number of subdomains
r_maxndomsis the maximum number of adjacent subdomains and is updated as necessary. The update is skipped if a NULL value is supplied.

Definition at line 134 of file minconn.c.

idx_t vnbrpoolGetNext ( ctrl_t ctrl,
idx_t  nnbrs 
)

This function gets the next free index from vnbrpool

Definition at line 200 of file wspace.c.

void vnbrpoolReset ( ctrl_t ctrl)

This function resets the vnbrpool

Definition at line 191 of file wspace.c.

void* wspacemalloc ( ctrl_t ctrl,
size_t  nbytes 
)

This function allocate space from the workspace/heap

Definition at line 108 of file wspace.c.

void wspacepop ( ctrl_t ctrl)

This function frees all mops since the last push

Definition at line 127 of file wspace.c.

void wspacepush ( ctrl_t ctrl)

This function sets a marker in the stack of malloc ops to be used subsequently for freeing purposes

Definition at line 118 of file wspace.c.



gtsam
Author(s):
autogenerated on Sat May 8 2021 02:51:33