Go to the source code of this file.
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:
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.
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.
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.
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. |
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:
Any of the above errors are fixed by performing the following operations:
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.
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.
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.
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.
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'.
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.
ctrl | is the control structure |
graph | is the graph to be partitioned |
part | is the vector that on return will store the partitioning |
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.
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.
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. |
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.
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 | ) |