#include "metislib.h"

Include dependency graph for ometis.c:

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

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]].

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.