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

Go to the source code of this file.

Functions
void	Init2WayPartition (ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niparts)
void	InitSeparator (ctrl_t *ctrl, graph_t *graph, idx_t niparts)
void	RandomBisection (ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niparts)
void	GrowBisection (ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niparts)
void	McRandomBisection (ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niparts)
void	McGrowBisection (ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niparts)
void	GrowBisectionNode (ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niparts)
void	GrowBisectionNode2 (ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niparts)

---

Function Documentation

void Init2WayPartition	(	ctrl_t *	ctrl,
		graph_t *	graph,
		real_t *	ntpwgts,
		idx_t	niparts
	)

This function computes the initial bisection of the coarsest graph

Definition at line 19 of file initpart.c.

References ctrl_t::dbglvl, gk_errexit(), GrowBisection(), ctrl_t::InitPartTmr, ctrl_t::iptype, McGrowBisection(), McRandomBisection(), METIS_DBG_IPART, METIS_DBG_MOVEINFO, METIS_DBG_REFINE, METIS_DBG_TIME, METIS_IPTYPE_GROW, METIS_IPTYPE_RANDOM, graph_t::mincut, graph_t::ncon, graph_t::nedges, RandomBisection(), and graph_t::tvwgt.

Referenced by MultilevelBisect().

Here is the call graph for this function:

Here is the caller graph for this function:

void InitSeparator	(	ctrl_t *	ctrl,
		graph_t *	graph,
		idx_t	niparts
	)

This function computes the initial separator of the coarsest graph

Definition at line 67 of file initpart.c.

References Compute2WayPartitionParams(), ConstructSeparator(), ctrl_t::dbglvl, gk_errexit(), GrowBisection(), GrowBisectionNode(), ctrl_t::InitPartTmr, ctrl_t::iptype, METIS_DBG_IPART, METIS_DBG_MOVEINFO, METIS_DBG_REFINE, METIS_DBG_TIME, METIS_IPTYPE_EDGE, METIS_IPTYPE_NODE, graph_t::mincut, graph_t::nedges, RandomBisection(), and Setup2WayBalMultipliers().

Referenced by MlevelNodeBisectionL1().

Here is the call graph for this function:

Here is the caller graph for this function:

void RandomBisection	(	ctrl_t *	ctrl,
		graph_t *	graph,
		real_t *	ntpwgts,
		idx_t	niparts
	)

This function computes a bisection of a graph by randomly assigning the vertices followed by a bisection refinement. The resulting partition is returned in graph->where.

Definition at line 114 of file initpart.c.

References graph_t::adjncy, adjncy, graph_t::adjwgt, adjwgt, Allocate2WayPartitionMemory(), Balance2Way(), Compute2WayPartitionParams(), FM_2WayRefine(), iwspacemalloc(), graph_t::mincut, graph_t::nvtxs, perm, graph_t::tvwgt, ctrl_t::ubfactors, graph_t::vwgt, vwgt, graph_t::where, where, graph_t::xadj, and xadj.

Referenced by Init2WayPartition(), and InitSeparator().

Here is the call graph for this function:

Here is the caller graph for this function:

void GrowBisection	(	ctrl_t *	ctrl,
		graph_t *	graph,
		real_t *	ntpwgts,
		idx_t	niparts
	)

This function takes a graph and produces a bisection by using a region growing algorithm. The resulting bisection is refined using FM. The resulting partition is returned in graph->where.

Definition at line 189 of file initpart.c.

References graph_t::adjncy, adjncy, graph_t::adjwgt, adjwgt, Allocate2WayPartitionMemory(), Balance2Way(), Compute2WayPartitionParams(), FM_2WayRefine(), iwspacemalloc(), graph_t::mincut, ctrl_t::niter, graph_t::nvtxs, graph_t::tvwgt, ctrl_t::ubfactors, graph_t::vwgt, vwgt, graph_t::where, where, graph_t::xadj, and xadj.

Referenced by Init2WayPartition(), and InitSeparator().

Here is the call graph for this function:

Here is the caller graph for this function:

void McRandomBisection	(	ctrl_t *	ctrl,
		graph_t *	graph,
		real_t *	ntpwgts,
		idx_t	niparts
	)

This function takes a multi-constraint graph and computes a bisection by randomly assigning the vertices and then refining it. The resulting partition is returned in graph->where.

Definition at line 325 of file initpart.c.

References Allocate2WayPartitionMemory(), Balance2Way(), Compute2WayPartitionParams(), FM_2WayRefine(), iwspacemalloc(), graph_t::mincut, graph_t::ncon, ncon, ctrl_t::niter, graph_t::nvtxs, perm, graph_t::vwgt, vwgt, graph_t::where, and where.

Referenced by Init2WayPartition().

Here is the call graph for this function:

Here is the caller graph for this function:

void McGrowBisection	(	ctrl_t *	ctrl,
		graph_t *	graph,
		real_t *	ntpwgts,
		idx_t	niparts
	)

This function takes a multi-constraint graph and produces a bisection by using a region growing algorithm. The resulting partition is returned in graph->where.

Definition at line 385 of file initpart.c.

References Allocate2WayPartitionMemory(), Balance2Way(), Compute2WayPartitionParams(), FM_2WayRefine(), iwspacemalloc(), graph_t::mincut, ncon, ctrl_t::niter, graph_t::nvtxs, graph_t::where, and where.

Referenced by Init2WayPartition().

Here is the call graph for this function:

Here is the caller graph for this function:

void GrowBisectionNode	(	ctrl_t *	ctrl,
		graph_t *	graph,
		real_t *	ntpwgts,
		idx_t	niparts
	)

Definition at line 433 of file initpart.c.

References graph_t::adjncy, adjncy, graph_t::adjwgt, adjwgt, Balance2Way(), graph_t::bndind, graph_t::bndptr, Compute2WayNodePartitionParams(), Compute2WayPartitionParams(), graph_t::ed, FM_2WayNodeRefine1Sided(), FM_2WayNodeRefine2Sided(), FM_2WayRefine(), gk_malloc(), graph_t::id, iwspacemalloc(), graph_t::mincut, graph_t::nbnd, graph_t::nrinfo, graph_t::nvtxs, graph_t::pwgts, graph_t::tvwgt, ctrl_t::ubfactors, graph_t::vwgt, vwgt, graph_t::where, where, graph_t::xadj, and xadj.

Referenced by InitSeparator().

Here is the call graph for this function:

Here is the caller graph for this function:

void GrowBisectionNode2	(	ctrl_t *	ctrl,
		graph_t *	graph,
		real_t *	ntpwgts,
		idx_t	niparts
	)

Definition at line 570 of file initpart.c.

References graph_t::bndind, graph_t::bndptr, Compute2WayNodePartitionParams(), Compute2WayPartitionParams(), graph_t::ed, FM_2WayNodeRefine2Sided(), FM_2WayRefine(), General2WayBalance(), gk_malloc(), graph_t::id, iwspacemalloc(), graph_t::mincut, graph_t::nbnd, ctrl_t::niter, graph_t::nrinfo, graph_t::nvtxs, graph_t::pwgts, graph_t::where, where, graph_t::xadj, and xadj.

Here is the call graph for this function: