#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) |
Function Documentation
| 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.
- Parameters
-
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.
- 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.