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

Go to the source code of this file.

Functions
int	METIS_NodeNDP (idx_t nvtxs, idx_t *xadj, idx_t *adjncy, idx_t *vwgt, idx_t npes, idx_t *options, idx_t *perm, idx_t *iperm, idx_t *sizes)
void	MlevelNestedDissectionP (ctrl_t *ctrl, graph_t *graph, idx_t *order, idx_t lastvtx, idx_t npes, idx_t cpos, idx_t *sizes)
int	METIS_ComputeVertexSeparator (idx_t *nvtxs, idx_t *xadj, idx_t *adjncy, idx_t *vwgt, idx_t *options, idx_t *r_sepsize, idx_t *part)
int	METIS_NodeRefine (idx_t nvtxs, idx_t *xadj, idx_t *vwgt, idx_t *adjncy, idx_t *where, idx_t *hmarker, real_t ubfactor)
void	FM_2WayNodeRefine1SidedP (ctrl_t *ctrl, graph_t *graph, idx_t *hmarker, real_t ubfactor, idx_t npasses)
void	FM_2WayNodeRefine2SidedP (ctrl_t *ctrl, graph_t *graph, idx_t *hmarker, real_t ubfactor, idx_t npasses)

---

Function Documentation

int METIS_NodeNDP	(	idx_t	nvtxs,
		idx_t *	xadj,
		idx_t *	adjncy,
		idx_t *	vwgt,
		idx_t	npes,
		idx_t *	options,
		idx_t *	perm,
		idx_t *	iperm,
		idx_t *	sizes
	)

This function is the entry point for the node ND code for ParMETIS. The difference between this routine and the standard METIS_NodeND are the following

• It performs at least log2(npes) levels of nested dissection.
• It stores the size of the log2(npes) top-level separators in the sizes array.

Definition at line 28 of file parmetis.c.

References AllocateWorkSpace(), ctrl_t::compress, CompressGraph(), ctrl_t::dbglvl, FreeCtrl(), gk_free(), InitTimers(), PUP::l, METIS_DBG_TIME, METIS_ERROR_INPUT, METIS_OK, METIS_OP_OMETIS, MlevelNestedDissectionP(), graph_t::nvtxs, PrintTimers(), SetupCtrl(), SetupGraph(), and ctrl_t::TotalTmr.

Here is the call graph for this function:

void MlevelNestedDissectionP	(	ctrl_t *	ctrl,
		graph_t *	graph,
		idx_t *	order,
		idx_t	lastvtx,
		idx_t	npes,
		idx_t	cpos,
		idx_t *	sizes
	)

This function is similar to MlevelNestedDissection with the difference that it also records separator sizes for the top log2(npes) levels

Definition at line 105 of file parmetis.c.

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

Referenced by METIS_NodeNDP(), and MlevelNestedDissectionP().

Here is the call graph for this function:

Here is the caller graph for this function:

int METIS_ComputeVertexSeparator	(	idx_t *	nvtxs,
		idx_t *	xadj,
		idx_t *	adjncy,
		idx_t *	vwgt,
		idx_t *	options,
		idx_t *	r_sepsize,
		idx_t *	part
	)

This function bisects a graph by computing a vertex separator

Definition at line 161 of file parmetis.c.

References AllocateWorkSpace(), ctrl_t::CoarsenTo, FreeCtrl(), FreeGraph(), InitRandom(), METIS_ERROR_INPUT, METIS_OK, METIS_OP_OMETIS, MlevelNodeBisectionMultiple(), graph_t::pwgts, ctrl_t::seed, SetupCtrl(), SetupGraph(), and graph_t::where.

Here is the call graph for this function:

int METIS_NodeRefine	(	idx_t	nvtxs,
		idx_t *	xadj,
		idx_t *	vwgt,
		idx_t *	adjncy,
		idx_t *	where,
		idx_t *	hmarker,
		real_t	ubfactor
	)

This function is the entry point of a node-based separator refinement of the nodes with an hmarker[] of 0.

Definition at line 199 of file parmetis.c.

References Allocate2WayNodePartitionMemory(), AllocateWorkSpace(), Compute2WayNodePartitionParams(), FM_2WayNodeRefine1SidedP(), FreeCtrl(), FreeGraph(), METIS_ERROR_INPUT, METIS_OK, METIS_OP_OMETIS, SetupCtrl(), SetupGraph(), and graph_t::where.

Here is the call graph for this function:

void FM_2WayNodeRefine1SidedP	(	ctrl_t *	ctrl,
		graph_t *	graph,
		idx_t *	hmarker,
		real_t	ubfactor,
		idx_t	npasses
	)

This function performs a node-based 1-sided FM refinement that moves only nodes whose hmarker[] == -1. It is used by Parmetis.

Definition at line 237 of file parmetis.c.

References abs(), graph_t::adjncy, adjncy, graph_t::bndind, graph_t::bndptr, CheckNodeBnd(), CheckNodePartitionParams(), ctrl_t::dbglvl, nrinfo_t::edegrees, iwspacemalloc(), METIS_DBG_MOVEINFO, METIS_DBG_REFINE, graph_t::mincut, graph_t::nbnd, graph_t::nrinfo, graph_t::nvtxs, graph_t::pwgts, rpq_t, graph_t::vwgt, vwgt, graph_t::where, where, graph_t::xadj, and xadj.

Referenced by METIS_NodeRefine().

Here is the call graph for this function:

Here is the caller graph for this function:

void FM_2WayNodeRefine2SidedP	(	ctrl_t *	ctrl,
		graph_t *	graph,
		idx_t *	hmarker,
		real_t	ubfactor,
		idx_t	npasses
	)

This function performs a node-based (two-sided) FM refinement that moves only nodes whose hmarker[] == -1. It is used by Parmetis.

Definition at line 467 of file parmetis.c.

References abs(), graph_t::adjncy, adjncy, graph_t::bndind, graph_t::bndptr, CheckNodeBnd(), CheckNodePartitionParams(), ctrl_t::dbglvl, nrinfo_t::edegrees, iwspacemalloc(), METIS_DBG_MOVEINFO, METIS_DBG_REFINE, graph_t::mincut, graph_t::nbnd, graph_t::nrinfo, graph_t::nvtxs, graph_t::pwgts, rpq_t, PUP::u, graph_t::vwgt, vwgt, graph_t::where, where, graph_t::xadj, and xadj.

Here is the call graph for this function: