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

The top-level routines for multilevel k-way partitioning that minimizes the edge cut. More...

Go to the source code of this file.

Functions
int	METIS_PartGraphKway (idx_t *nvtxs, idx_t *ncon, idx_t *xadj, idx_t *adjncy, idx_t *vwgt, idx_t *vsize, idx_t *adjwgt, idx_t *nparts, real_t *tpwgts, real_t *ubvec, idx_t *options, idx_t *objval, idx_t *part)
idx_t	MlevelKWayPartitioning (ctrl_t *ctrl, graph_t *graph, idx_t *part)
void	InitKWayPartitioning (ctrl_t *ctrl, graph_t *graph)

---

Detailed Description

The top-level routines for multilevel k-way partitioning that minimizes the edge cut.

Date:

Started 7/28/1997

Author:

George

Copyright 1997-2011, Regents of the University of Minnesota

Version:

$Id: kmetis.c 13905 2013-03-25 13:21:20Z karypis $ 

Definition in file kmetis.c.

---

Function Documentation

int METIS_PartGraphKway	(	idx_t *	nvtxs,
		idx_t *	ncon,
		idx_t *	xadj,
		idx_t *	adjncy,
		idx_t *	vwgt,
		idx_t *	vsize,
		idx_t *	adjwgt,
		idx_t *	nparts,
		real_t *	tpwgts,
		real_t *	ubvec,
		idx_t *	options,
		idx_t *	objval,
		idx_t *	part
	)

This function is the entry point for MCKMETIS

Definition at line 18 of file kmetis.c.

References AllocateWorkSpace(), Change2CNumbering(), Change2FNumbering(), ctrl_t::CoarsenTo, ctrl_t::contig, ctrl_t::dbglvl, FreeCtrl(), gk_errexit(), gk_log2(), gk_malloc_cleanup(), gk_malloc_init(), gk_sigtrap(), gk_siguntrap(), InitTimers(), IsConnected(), METIS_DBG_TIME, METIS_ERROR_INPUT, METIS_ERROR_MEMORY, METIS_OP_KMETIS, metis_rcode(), MlevelKWayPartitioning(), ctrl_t::nIparts, ctrl_t::numflag, PrintTimers(), SetupCtrl(), SetupGraph(), SetupKWayBalMultipliers(), and ctrl_t::TotalTmr.

Here is the call graph for this function:

idx_t MlevelKWayPartitioning	(	ctrl_t *	ctrl,
		graph_t *	graph,
		idx_t *	part
	)

This function computes a k-way partitioning of a graph that minimizes the specified objective function.

Parameters:

	ctrl	is the control structure
	graph	is the graph to be partitioned
	part	is the vector that on return will store the partitioning

Returns:

the objective value of the partitoning. The partitioning itself is stored in the part vector.

Definition at line 103 of file kmetis.c.

References AllocateKWayPartitionMemory(), AllocateRefinementWorkSpace(), AllocateWorkSpace(), CoarsenGraph(), ComputeLoadImbalanceDiff(), ctrl_t::dbglvl, FreeGraph(), FreeRData(), FreeWorkSpace(), gk_errexit(), InitKWayPartitioning(), ctrl_t::InitPartTmr, METIS_DBG_IPART, METIS_DBG_TIME, METIS_OBJTYPE_CUT, METIS_OBJTYPE_VOL, graph_t::mincut, graph_t::minvol, ctrl_t::ncuts, graph_t::nedges, ctrl_t::nparts, graph_t::nvtxs, ctrl_t::objtype, objval, ctrl_t::pijbm, RefineKWay(), status, ctrl_t::ubfactors, and graph_t::where.

Referenced by METIS_PartGraphKway().

Here is the call graph for this function:

Here is the caller graph for this function:

void InitKWayPartitioning	(	ctrl_t *	ctrl,
		graph_t *	graph
	)

This function computes the initial k-way partitioning using PMETIS

Definition at line 172 of file kmetis.c.

References graph_t::adjncy, graph_t::adjwgt, ComputeVolume(), gk_errexit(), gk_free(), METIS_OBJTYPE_CUT, METIS_OBJTYPE_VOL, METIS_OK, METIS_OPTION_NCUTS, METIS_OPTION_NITER, METIS_OPTION_NO2HOP, METIS_OPTION_OBJTYPE, METIS_PartGraphRecursive(), METIS_SetDefaultOptions(), graph_t::ncon, ctrl_t::nIparts, ctrl_t::no2hop, ctrl_t::nparts, graph_t::nvtxs, ctrl_t::objtype, status, ctrl_t::tpwgts, ctrl_t::ubfactors, ubvec, graph_t::vsize, graph_t::vwgt, graph_t::where, and graph_t::xadj.

Referenced by MlevelKWayPartitioning().

Here is the call graph for this function:

Here is the caller graph for this function: