Go to the source code of this file.
Function Documentation
This function allocates memory for the k-way cut-based refinement
Definition at line 116 of file kwayrefine.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.
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
-
graph is the graph to be checked, whose numbering starts from 0. numflag is 0 if error reporting will be done using 0 as the numbering, or 1 if the reporting should be done using 1. verbose is 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 cnbrpoolReset | ( | ctrl_t * | ctrl | ) |
| 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.
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
-
ctrl is the control structure graph is the graph structure perm is 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 160 of file libmetis/stat.c.
This function computes the boundary definition for balancing.
Definition at line 507 of file kwayrefine.c.
This function computes the initial id/ed for cut-based partitioning
Definition at line 149 of file kwayrefine.c.
This function computes the initial gains in the communication volume
Definition at line 562 of file kwayrefine.c.
Definition at line 125 of file libmetis/stat.c.
Definition at line 21 of file libmetis/stat.c.
Definition at line 69 of file separator.c.
Definition at line 21 of file separator.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.
| graph_t* CreateGraph | ( | void | ) |
This function creates and initializes a graph_t data structure
Definition at line 162 of file libmetis/graph.c.
| mesh_t* CreateMesh | ( | void | ) |
This function finds the connected components induced by the partitioning vector.
- Parameters
-
graph is the graph structure where is the partitioning vector. If this is NULL, then the entire graph is treated to belong into a single partition. cptr is the ptr structure of the CSR representation of the components. The length of this vector must be graph->nvtxs+1. cind is 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.
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.
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_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_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 FreeCtrl | ( | ctrl_t ** | r_ctrl | ) |
| 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 | ) |
| 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 | ) |
| 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
-
graph is the graph that is being refined. niter is the number of refinement iterations. ffactor is the fudge-factor for allowing positive gain moves to violate the max-pwgt constraint. omode is the type of optimization that will performed among OMODE_REFINE and OMODE_BALANCE
| 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
-
graph is the graph that is being refined. niter is the number of refinement iterations. ffactor is the fudge-factor for allowing positive gain moves to violate the max-pwgt constraint.
| 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
-
graph is the graph that is being refined. niter is the number of refinement iterations. ffactor is the fudge-factor for allowing positive gain moves to violate the max-pwgt constraint. omode is the type of optimization that will performed among OMODE_REFINE and OMODE_BALANCE
| 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
-
graph is the graph that is being refined. niter is the number of refinement iterations. ffactor is the fudge-factor for allowing positive gain moves to violate the max-pwgt constraint.
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.
Definition at line 433 of file initpart.c.
Definition at line 570 of file initpart.c.
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.
Returns the highest weight index of x[i]*y[i]
Definition at line 31 of file libmetis/util.c.
These functions return the index of the maximum element in a vector
Definition at line 46 of file libmetis/util.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.
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 InitMesh | ( | mesh_t * | mesh | ) |
| void InitRandom | ( | idx_t | seed | ) |
This function initializes the random number generator
Definition at line 21 of file libmetis/util.c.
This function computes the initial separator of the coarsest graph
Definition at line 67 of file initpart.c.
This function checks if the partition weights are within the balance contraints
Definition at line 666 of file kwayrefine.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
-
ctrl is the control structure. graph is the graph being partitioned. v is the vertex that is moving. from is the original partition of v. to is the new partition of v. queue is the priority queue. If the queue is NULL, no priority-queue related updates are performed. vstatus is an array that marks the status of the vertex in terms of the priority queue. If queue is NULL, this parameter is ignored. r_nqupd is the number of vertices that have been inserted/removed from the queue. If queue is NULL, this parameter is ignored. updptr stores the index of each vertex in updind. If queue is NULL, this parameter is ignored. updind is the list of vertices that have been inserted/removed from the queue. If queue is NULL, this parameter is ignored. vmarker is of size nvtxs and is used internally as a temporary array. On entry and return all of its entries are 0. pmarker is of sie nparts and is used internally as a temporary marking array. On entry and return all of its entries are -1. modind is an array of size nvtxs and is used to keep track of the list of vertices whose gains need to be updated.
| 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.
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.
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.
converts a signal code into a Metis return code
Definition at line 123 of file libmetis/util.c.
Definition at line 42 of file mincover.c.
Definition at line 126 of file mincover.c.
Definition at line 212 of file mincover.c.
Definition at line 163 of file mincover.c.
Definition at line 237 of file mincover.c.
This function computes a k-way partitioning of a graph that minimizes the specified objective function.
- Parameters
-
ctrl is the control structure graph is the graph to be partitioned part is 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.
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.
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).
| 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 PrintCtrl | ( | ctrl_t * | ctrl | ) |
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.
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.
These functions return the index of the almost maximum element in a vector
Definition at line 63 of file libmetis/util.c.
This function is the entry point of cut-based refinement
Definition at line 17 of file kwayrefine.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.
Setup the various arrays for the splitted graph
Definition at line 133 of file libmetis/graph.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
-
ctrl stores run state info. graph is the graph to be split. ncmps is the number of connected components. cptr is 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). cind is 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.
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
-
u is the ID of one of the incident subdomains to the edge v is the ID of the other incident subdomains to the edge ewgt is the weight to be added to the subdomain edge nparts is the number of subdomains r_maxndoms is the maximum number of adjacent subdomains and is updated as necessary. The update is skipped if a NULL value is supplied.
| void vnbrpoolReset | ( | ctrl_t * | ctrl | ) |
| void wspacepop | ( | ctrl_t * | ctrl | ) |