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

Functions for the edge-based FM refinement. More...

Go to the source code of this file.

Functions
void	FM_2WayRefine (ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niter)
void	FM_2WayCutRefine (ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niter)
void	FM_Mc2WayCutRefine (ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niter)
void	SelectQueue (graph_t *graph, real_t *pijbm, real_t *ubfactors, rpq_t **queues, idx_t *from, idx_t *cnum)
void	Print2WayRefineStats (ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, real_t deltabal, idx_t mincutorder)

---

Detailed Description

Functions for the edge-based FM refinement.

Date:

Started 7/23/97

Author:

George

Copyright 1997-2011, Regents of the University of Minnesota

Version:

$Id: fm.c 10187 2011-06-13 13:46:57Z karypis $ 

Definition in file fm.c.

---

Function Documentation

void FM_2WayRefine	(	ctrl_t *	ctrl,
		graph_t *	graph,
		real_t *	ntpwgts,
		idx_t	niter
	)

Definition at line 17 of file fm.c.

References FM_2WayCutRefine(), FM_Mc2WayCutRefine(), and graph_t::ncon.

Referenced by GrowBisection(), GrowBisectionNode(), GrowBisectionNode2(), McGrowBisection(), McRandomBisection(), RandomBisection(), and Refine2Way().

Here is the call graph for this function:

Here is the caller graph for this function:

void FM_2WayCutRefine	(	ctrl_t *	ctrl,
		graph_t *	graph,
		real_t *	ntpwgts,
		idx_t	niter
	)

This function performs a cut-focused FM refinement

Definition at line 29 of file fm.c.

References graph_t::adjncy, adjncy, graph_t::adjwgt, adjwgt, graph_t::bndind, graph_t::bndptr, CheckBnd(), ComputeCut(), ctrl_t::dbglvl, graph_t::ed, graph_t::id, iwspacemalloc(), METIS_DBG_MOVEINFO, METIS_DBG_REFINE, graph_t::mincut, graph_t::nbnd, graph_t::nvtxs, perm, Print2WayRefineStats(), graph_t::pwgts, rpq_t, tpwgts, graph_t::tvwgt, graph_t::vwgt, vwgt, graph_t::where, where, graph_t::xadj, and xadj.

Referenced by FM_2WayRefine().

Here is the call graph for this function:

Here is the caller graph for this function:

void FM_Mc2WayCutRefine	(	ctrl_t *	ctrl,
		graph_t *	graph,
		real_t *	ntpwgts,
		idx_t	niter
	)

This function performs a cut-focused multi-constraint FM refinement

Definition at line 207 of file fm.c.

References graph_t::adjncy, adjncy, graph_t::adjwgt, adjwgt, BetterBalance2Way(), graph_t::bndind, graph_t::bndptr, CheckBnd(), ComputeCut(), ComputeLoadImbalance(), ComputeLoadImbalanceDiffVec(), ctrl_t::dbglvl, graph_t::ed, iargmax_nrm(), graph_t::id, graph_t::invtvwgt, iwspacemalloc(), PUP::l, METIS_DBG_MOVEINFO, METIS_DBG_REFINE, graph_t::mincut, graph_t::nbnd, graph_t::ncon, ncon, graph_t::nvtxs, perm, ctrl_t::pijbm, Print2WayRefineStats(), graph_t::pwgts, rpq_t, rwspacemalloc(), SelectQueue(), ctrl_t::ubfactors, graph_t::vwgt, vwgt, graph_t::where, where, wspacemalloc(), graph_t::xadj, and xadj.

Referenced by FM_2WayRefine().

Here is the call graph for this function:

Here is the caller graph for this function:

void SelectQueue	(	graph_t *	graph,
		real_t *	pijbm,
		real_t *	ubfactors,
		rpq_t **	queues,
		idx_t *	from,
		idx_t *	cnum
	)

This function selects the partition number and the queue from which we will move vertices out.

Definition at line 439 of file fm.c.

References max(), graph_t::ncon, ncon, part, 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 Print2WayRefineStats	(	ctrl_t *	ctrl,
		graph_t *	graph,
		real_t *	ntpwgts,
		real_t	deltabal,
		idx_t	mincutorder
	)

Prints statistics about the refinement

Definition at line 515 of file fm.c.

References ComputeLoadImbalance(), graph_t::invtvwgt, graph_t::mincut, graph_t::nbnd, graph_t::ncon, graph_t::nvtxs, ctrl_t::pijbm, and graph_t::pwgts.

Referenced by FM_2WayCutRefine(), and FM_Mc2WayCutRefine().

Here is the call graph for this function:

Here is the caller graph for this function: