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

Go to the source code of this file.

Functions
int	rvecle (idx_t n, real_t *x, real_t *y)
int	rvecge (idx_t n, real_t *x, real_t *y)
int	rvecsumle (idx_t n, real_t *x1, real_t *x2, real_t *y)
real_t	rvecmaxdiff (idx_t n, real_t *x, real_t *y)
int	ivecle (idx_t n, idx_t *x, idx_t *z)
int	ivecge (idx_t n, idx_t *x, idx_t *z)
int	ivecaxpylez (idx_t n, idx_t a, idx_t *x, idx_t *y, idx_t *z)
int	ivecaxpygez (idx_t n, idx_t a, idx_t *x, idx_t *y, idx_t *z)
int	BetterVBalance (idx_t ncon, real_t *invtvwgt, idx_t *v_vwgt, idx_t *u1_vwgt, idx_t *u2_vwgt)
int	BetterBalance2Way (idx_t n, real_t *x, real_t *y)
int	BetterBalanceKWay (idx_t ncon, idx_t *vwgt, real_t *ubvec, idx_t a1, idx_t *pt1, real_t *bm1, idx_t a2, idx_t *pt2, real_t *bm2)
real_t	ComputeLoadImbalance (graph_t *graph, idx_t nparts, real_t *pijbm)
real_t	ComputeLoadImbalanceDiff (graph_t *graph, idx_t nparts, real_t *pijbm, real_t *ubvec)
real_t	ComputeLoadImbalanceDiffVec (graph_t *graph, idx_t nparts, real_t *pijbm, real_t *ubfactors, real_t *diffvec)
void	ComputeLoadImbalanceVec (graph_t *graph, idx_t nparts, real_t *pijbm, real_t *lbvec)

---

Function Documentation

int rvecle	(	idx_t	n,
		real_t *	x,
		real_t *	y
	)

This function compares two vectors x & y and returns true if i, x[i] <= y[i].

Definition at line 22 of file mcutil.c.

int rvecge	(	idx_t	n,
		real_t *	x,
		real_t *	y
	)

This function compares two vectors x & y and returns true if i, x[i] >= y[i].

Definition at line 38 of file mcutil.c.

int rvecsumle	(	idx_t	n,
		real_t *	x1,
		real_t *	x2,
		real_t *	y
	)

This function compares vectors x1+x2 against y and returns true if i, x1[i]+x2[i] <= y[i].

Definition at line 54 of file mcutil.c.

real_t rvecmaxdiff	(	idx_t	n,
		real_t *	x,
		real_t *	y
	)

This function returns max_i(x[i]-y[i])

Definition at line 68 of file mcutil.c.

References max().

Referenced by Greedy_McKWayCutOptimize(), and Greedy_McKWayVolOptimize().

Here is the call graph for this function:

Here is the caller graph for this function:

int ivecle	(	idx_t	n,
		idx_t *	x,
		idx_t *	z
	)

This function returns true if i, x[i] <= z[i].

Definition at line 86 of file mcutil.c.

Referenced by Match_RM(), and Match_SHEM().

Here is the caller graph for this function:

int ivecge	(	idx_t	n,
		idx_t *	x,
		idx_t *	z
	)

This function returns true if i, x[i] >= z[i].

Definition at line 100 of file mcutil.c.

int ivecaxpylez	(	idx_t	n,
		idx_t	a,
		idx_t *	x,
		idx_t *	y,
		idx_t *	z
	)

This function returns true if i, a*x[i]+y[i] <= z[i].

Definition at line 114 of file mcutil.c.

Referenced by EliminateSubDomainEdges(), Greedy_McKWayCutOptimize(), Greedy_McKWayVolOptimize(), Match_RM(), and Match_SHEM().

Here is the caller graph for this function:

int ivecaxpygez	(	idx_t	n,
		idx_t	a,
		idx_t *	x,
		idx_t *	y,
		idx_t *	z
	)

This function returns true if i, a*x[i]+y[i] >= z[i].

Definition at line 128 of file mcutil.c.

Referenced by Greedy_McKWayCutOptimize(), and Greedy_McKWayVolOptimize().

Here is the caller graph for this function:

int BetterVBalance	(	idx_t	ncon,
		real_t *	invtvwgt,
		idx_t *	v_vwgt,
		idx_t *	u1_vwgt,
		idx_t *	u2_vwgt
	)

This function checks if v+u2 provides a better balance in the weight vector that v+u1

Definition at line 143 of file mcutil.c.

Referenced by Match_SHEM().

Here is the caller graph for this function:

int BetterBalance2Way	(	idx_t	n,
		real_t *	x,
		real_t *	y
	)

This function takes two ubfactor-centered load imbalance vectors x & y, and returns true if y is better balanced than x.

Definition at line 169 of file mcutil.c.

Referenced by FM_Mc2WayCutRefine(), and McGeneral2WayBalance().

Here is the caller graph for this function:

int BetterBalanceKWay	(	idx_t	ncon,
		idx_t *	vwgt,
		real_t *	ubvec,
		idx_t	a1,
		idx_t *	pt1,
		real_t *	bm1,
		idx_t	a2,
		idx_t *	pt2,
		real_t *	bm2
	)

Given a vertex and two weights, this function returns 1, if the second partition will be more balanced than the first after the weighted additional of that vertex. The balance determination takes into account the ideal target weights of the two partitions.

Definition at line 189 of file mcutil.c.

Referenced by EliminateComponents(), Greedy_McKWayCutOptimize(), and Greedy_McKWayVolOptimize().

Here is the caller graph for this function:

real_t ComputeLoadImbalance	(	graph_t *	graph,
		idx_t	nparts,
		real_t *	pijbm
	)

Computes the maximum load imbalance of a partitioning solution over all the constraints.

Definition at line 228 of file mcutil.c.

References max(), graph_t::ncon, ncon, and graph_t::pwgts.

Referenced by FM_Mc2WayCutRefine(), Greedy_KWayCutOptimize(), Greedy_KWayVolOptimize(), Greedy_McKWayCutOptimize(), Greedy_McKWayVolOptimize(), McGeneral2WayBalance(), and Print2WayRefineStats().

Here is the call graph for this function:

Here is the caller graph for this function:

real_t ComputeLoadImbalanceDiff	(	graph_t *	graph,
		idx_t	nparts,
		real_t *	pijbm,
		real_t *	ubvec
	)

Computes the maximum load imbalance difference of a partitioning solution over all the constraints. The difference is defined with respect to the allowed maximum unbalance for the respective constraint.

Definition at line 256 of file mcutil.c.

References max(), graph_t::ncon, ncon, and graph_t::pwgts.

Referenced by Balance2Way(), IsBalanced(), MlevelKWayPartitioning(), and MultilevelBisect().

Here is the call graph for this function:

Here is the caller graph for this function:

real_t ComputeLoadImbalanceDiffVec	(	graph_t *	graph,
		idx_t	nparts,
		real_t *	pijbm,
		real_t *	ubfactors,
		real_t *	diffvec
	)

Computes the difference between load imbalance of each constraint across the partitions minus the desired upper bound on the load imabalnce. It also returns the maximum load imbalance across the partitions & constraints.

Definition at line 284 of file mcutil.c.

References max(), graph_t::ncon, ncon, and graph_t::pwgts.

Referenced by FM_Mc2WayCutRefine(), and McGeneral2WayBalance().

Here is the call graph for this function:

Here is the caller graph for this function:

void ComputeLoadImbalanceVec	(	graph_t *	graph,
		idx_t	nparts,
		real_t *	pijbm,
		real_t *	lbvec
	)

Computes the load imbalance of each constraint across the partitions.

Definition at line 311 of file mcutil.c.

References graph_t::ncon, ncon, and graph_t::pwgts.

Referenced by Greedy_McKWayCutOptimize(), and Greedy_McKWayVolOptimize().

Here is the caller graph for this function: