libs/ck-libs/metis/libmetis/ometis.c File Reference

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	MlevelNodeBisectionMultiple (ctrl_t *ctrl, graph_t *graph)
void	MlevelNodeBisectionL2 (ctrl_t *ctrl, graph_t *graph, idx_t niparts)
void	MlevelNodeBisectionL1 (ctrl_t *ctrl, graph_t *graph, idx_t niparts)
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)
void	MMDOrder (ctrl_t *ctrl, graph_t *graph, idx_t *order, idx_t lastvtx)

---

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

Definition at line 43 of file ometis.c.

References AllocateWorkSpace(), ctrl_t::ccorder, ctrl_t::cfactor, Change2CNumbering(), Change2FNumberingOrder(), CheckGraph(), ctrl_t::compress, CompressGraph(), ctrl_t::dbglvl, FreeCtrl(), gk_free(), gk_malloc_cleanup(), gk_malloc_init(), gk_sigtrap(), gk_siguntrap(), InitTimers(), PUP::l, METIS_DBG_TIME, METIS_ERROR_INPUT, METIS_ERROR_MEMORY, METIS_OP_OMETIS, metis_rcode(), MlevelNestedDissection(), MlevelNestedDissectionCC(), ctrl_t::nseps, ctrl_t::numflag, numflag, graph_t::nvtxs, ctrl_t::pfactor, PrintTimers(), PruneGraph(), SetupCtrl(), SetupGraph(), and ctrl_t::TotalTmr.

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

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.

References graph_t::bndind, ctrl_t::dbglvl, FreeGraph(), graph_t::label, METIS_DBG_SEPINFO, MlevelNestedDissection(), MlevelNodeBisectionMultiple(), MMDOrder(), graph_t::nbnd, graph_t::nedges, graph_t::nvtxs, graph_t::pwgts, and SplitGraphOrder().

Referenced by METIS_NodeND(), and MlevelNestedDissection().

Here is the call graph for this function:

Here is the caller graph for this function:

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.

References graph_t::bndind, ctrl_t::dbglvl, FindSepInducedComponents(), FreeGraph(), gk_free(), iwspacemalloc(), graph_t::label, METIS_DBG_INFO, METIS_DBG_SEPINFO, MlevelNestedDissectionCC(), MlevelNodeBisectionMultiple(), MMDOrder(), graph_t::nbnd, graph_t::nvtxs, graph_t::pwgts, and SplitGraphOrderCC().

Referenced by METIS_NodeND(), and MlevelNestedDissectionCC().

Here is the call graph for this function:

Here is the caller graph for this function:

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.

References ctrl_t::compress, Compute2WayNodePartitionParams(), FreeRData(), iwspacemalloc(), graph_t::mincut, MlevelNodeBisectionL2(), ctrl_t::nseps, graph_t::nvtxs, graph_t::tvwgt, and graph_t::where.

Referenced by METIS_ComputeVertexSeparator(), MlevelNestedDissection(), MlevelNestedDissectionCC(), and MlevelNestedDissectionP().

Here is the call graph for this function:

Here is the caller graph for this function:

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.

References CoarsenGraphNlevels(), ctrl_t::CoarsenTo, FreeRData(), iwspacemalloc(), graph_t::mincut, MlevelNodeBisectionL1(), graph_t::nvtxs, Refine2WayNode(), graph_t::tvwgt, and graph_t::where.

Referenced by MlevelNodeBisectionMultiple().

Here is the call graph for this function:

Here is the caller graph for this function:

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.

References CoarsenGraph(), ctrl_t::CoarsenTo, InitSeparator(), graph_t::nvtxs, and Refine2WayNode().

Referenced by MlevelNodeBisectionL2().

Here is the call graph for this function:

Here is the caller graph for this function:

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.

References graph_t::adjncy, adjncy, graph_t::adjwgt, adjwgt, graph_t::bndind, graph_t::bndptr, ctrl_t::dbglvl, iwspacemalloc(), PUP::l, graph_t::label, METIS_DBG_TIME, graph_t::nbnd, graph_t::nedges, graph_t::nvtxs, SetupGraph_tvwgt(), SetupSplitGraph(), ctrl_t::SplitTmr, graph_t::vwgt, vwgt, graph_t::where, where, graph_t::xadj, and xadj.

Referenced by MlevelNestedDissection(), and MlevelNestedDissectionP().

Here is the call graph for this function:

Here is the caller graph for this function:

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.

Definition at line 552 of file ometis.c.

References graph_t::adjncy, adjncy, graph_t::adjwgt, adjwgt, graph_t::bndind, graph_t::bndptr, ctrl_t::dbglvl, gk_malloc(), iwspacemalloc(), PUP::l, graph_t::label, METIS_DBG_TIME, graph_t::nbnd, graph_t::nedges, graph_t::nvtxs, SetupGraph_tvwgt(), SetupSplitGraph(), ctrl_t::SplitTmr, graph_t::vwgt, vwgt, graph_t::where, where, graph_t::xadj, and xadj.

Referenced by MlevelNestedDissectionCC().

Here is the call graph for this function:

Here is the caller graph for this function:

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.

References graph_t::adjncy, adjncy, genmmd(), iperm, iwspacemalloc(), graph_t::label, list, graph_t::nvtxs, perm, graph_t::xadj, and xadj.

Referenced by MlevelNestedDissection(), MlevelNestedDissectionCC(), and MlevelNestedDissectionP().

Here is the call graph for this function:

Here is the caller graph for this function: