#include "metislib.h"
Go to the source code of this file.
Functions | |
int | METIS_NodeND (idx_t *nvtxs, idx_t *xadj, idx_t *adjncy, idx_t *vwgt, idx_t *options, idx_t *perm, idx_t *iperm) |
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 | 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) |
void | MMDOrder (ctrl_t *ctrl, graph_t *graph, idx_t *order, idx_t lastvtx) |
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) |
int METIS_NodeND | ( | idx_t * | nvtxs, |
idx_t * | xadj, | ||
idx_t * | adjncy, | ||
idx_t * | vwgt, | ||
idx_t * | options, | ||
idx_t * | perm, | ||
idx_t * | iperm | ||
) |
This function is the entry point for the multilevel nested dissection ordering code. At each bisection, a node-separator is computed using a node-based refinement approach.
nvtxs | is the number of vertices in the graph. |
xadj | is of length nvtxs+1 marking the start of the adjancy list of each vertex in adjncy. |
adjncy | stores the adjacency lists of the vertices. The adjnacy list of a vertex should not contain the vertex itself. |
vwgt | is an array of size nvtxs storing the weight of each vertex. If vwgt is NULL, then the vertices are considered to have unit weight. |
numflag | is either 0 or 1 indicating that the numbering of the vertices starts from 0 or 1, respectively. |
options | is an array of size METIS_NOPTIONS used to pass various options impacting the of the algorithm. A NULL value indicates use of default options. |
perm | is an array of size nvtxs such that if A and A' are the original and permuted matrices, then A'[i] = A[perm[i]]. |
iperm | is an array of size nvtxs such that if A and A' are the original and permuted matrices, then A[i] = A'[iperm[i]]. |
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).
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. |