Functions
ometis.c File Reference
#include "metislib.h"
Include dependency graph for ometis.c:

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

◆ METIS_NodeND()

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
nvtxsis the number of vertices in the graph.
xadjis of length nvtxs+1 marking the start of the adjancy list of each vertex in adjncy.
adjncystores the adjacency lists of the vertices. The adjnacy list of a vertex should not contain the vertex itself.
vwgtis an array of size nvtxs storing the weight of each vertex. If vwgt is NULL, then the vertices are considered to have unit weight.
numflagis either 0 or 1 indicating that the numbering of the vertices starts from 0 or 1, respectively.
optionsis an array of size METIS_NOPTIONS used to pass various options impacting the of the algorithm. A NULL value indicates use of default options.
permis an array of size nvtxs such that if A and A' are the original and permuted matrices, then A'[i] = A[perm[i]].
ipermis an array of size nvtxs such that if A and A' are the original and permuted matrices, then A[i] = A'[iperm[i]].

Definition at line 43 of file ometis.c.

◆ MlevelNestedDissection()

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.

◆ MlevelNestedDissectionCC()

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.

◆ MlevelNodeBisectionL1()

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.

◆ MlevelNodeBisectionL2()

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.

◆ MlevelNodeBisectionMultiple()

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.

◆ MMDOrder()

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.

◆ SplitGraphOrder()

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.

◆ SplitGraphOrderCC()

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.



gtsam
Author(s):
autogenerated on Tue Jul 4 2023 02:40:51