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

Functions that deal with prunning the number of adjacent subdomains in kmetis. More...

Go to the source code of this file.

Functions
void	ComputeSubDomainGraph (ctrl_t *ctrl, graph_t *graph)
void	UpdateEdgeSubDomainGraph (ctrl_t *ctrl, idx_t u, idx_t v, idx_t ewgt, idx_t *r_maxndoms)
void	EliminateSubDomainEdges (ctrl_t *ctrl, graph_t *graph)
void	MoveGroupMinConnForCut (ctrl_t *ctrl, graph_t *graph, idx_t to, idx_t nind, idx_t *ind)
void	MoveGroupMinConnForVol (ctrl_t *ctrl, graph_t *graph, idx_t to, idx_t nind, idx_t *ind, idx_t *vmarker, idx_t *pmarker, idx_t *modind)
void	PrintSubDomainGraph (graph_t *graph, idx_t nparts, idx_t *where)

---

Detailed Description

Functions that deal with prunning the number of adjacent subdomains in kmetis.

Date:

Started 7/15/98

Author:

George

Copyright 1997-2009, Regents of the University of Minnesota

Version:

Id

minconn.c 10513 2011-07-07 22:06:03Z karypis

Definition in file minconn.c.

---

Function Documentation

void ComputeSubDomainGraph	(	ctrl_t *	ctrl,
		graph_t *	graph
	)

This function computes the subdomain graph storing the result in the pre-allocated worspace arrays

Definition at line 18 of file minconn.c.

References ctrl_t::adids, graph_t::adjncy, adjncy, graph_t::adjwgt, adjwgt, ctrl_t::adwgts, graph_t::ckrinfo, ctrl_t::cnbrpool, cnbr_t::ed, gk_errexit(), vkrinfo_t::inbr, ckrinfo_t::inbr, iwspacemalloc(), ctrl_t::maxnads, METIS_OBJTYPE_CUT, METIS_OBJTYPE_VOL, ctrl_t::nads, vnbr_t::ned, vkrinfo_t::nnbrs, ckrinfo_t::nnbrs, ctrl_t::nparts, nparts, graph_t::nvtxs, ctrl_t::objtype, vnbr_t::pid, cnbr_t::pid, ctrl_t::pvec1, ctrl_t::pvec2, graph_t::vkrinfo, ctrl_t::vnbrpool, graph_t::where, where, graph_t::xadj, and xadj.

Referenced by EliminateSubDomainEdges(), Greedy_KWayCutOptimize(), Greedy_KWayVolOptimize(), Greedy_McKWayCutOptimize(), and Greedy_McKWayVolOptimize().

Here is the call graph for this function:

Here is the caller graph for this function:

void UpdateEdgeSubDomainGraph	(	ctrl_t *	ctrl,
		idx_t	u,
		idx_t	v,
		idx_t	ewgt,
		idx_t *	r_maxndoms
	)

This function updates the weight of an edge in the subdomain graph by adding to it the value of ewgt. The update can either increase or decrease the weight of the subdomain edge based on the value of ewgt.

Parameters:

	u	is the ID of one of the incident subdomains to the edge
	v	is the ID of the other incident subdomains to the edge
	ewgt	is the weight to be added to the subdomain edge
	nparts	is the number of subdomains
	r_maxndoms	is the maximum number of adjacent subdomains and is updated as necessary. The update is skipped if a NULL value is supplied.

Definition at line 134 of file minconn.c.

References ctrl_t::adids, ctrl_t::adwgts, ctrl_t::maxnads, ctrl_t::nads, and ctrl_t::nparts.

Referenced by Greedy_KWayCutOptimize(), Greedy_KWayVolOptimize(), Greedy_McKWayCutOptimize(), Greedy_McKWayVolOptimize(), MoveGroupMinConnForCut(), and MoveGroupMinConnForVol().

Here is the caller graph for this function:

void EliminateSubDomainEdges	(	ctrl_t *	ctrl,
		graph_t *	graph
	)

This function computes the subdomain graph

Definition at line 192 of file minconn.c.

References ctrl_t::adids, graph_t::adjncy, adjncy, graph_t::adjwgt, adjwgt, ctrl_t::adwgts, ComputeSubDomainGraph(), ctrl_t::dbglvl, gk_errexit(), ikvsortd(), ikvsorti(), ikvwspacemalloc(), ivecaxpylez(), iwspacemalloc(), key, max(), METIS_DBG_CONNINFO, METIS_OBJTYPE_CUT, METIS_OBJTYPE_VOL, min(), MoveGroupMinConnForCut(), MoveGroupMinConnForVol(), ctrl_t::nads, graph_t::ncon, ncon, ctrl_t::nparts, nparts, graph_t::nvtxs, ctrl_t::objtype, ctrl_t::pvec1, ctrl_t::pvec2, graph_t::pwgts, ctrl_t::tpwgts, tpwgts, graph_t::tvwgt, ctrl_t::ubfactors, graph_t::vwgt, vwgt, graph_t::where, where, graph_t::xadj, and xadj.

Referenced by RefineKWay().

Here is the call graph for this function:

Here is the caller graph for this function:

void MoveGroupMinConnForCut	(	ctrl_t *	ctrl,
		graph_t *	graph,
		idx_t	to,
		idx_t	nind,
		idx_t *	ind
	)

This function moves a collection of vertices and updates their rinfo

Definition at line 477 of file minconn.c.

References graph_t::adjncy, adjncy, graph_t::adjwgt, adjwgt, graph_t::bndind, graph_t::bndptr, graph_t::ckrinfo, ctrl_t::cnbrpool, cnbrpoolGetNext(), ComputeCut(), cnbr_t::ed, ckrinfo_t::id, ckrinfo_t::inbr, PUP::l, graph_t::mincut, graph_t::nbnd, graph_t::ncon, ckrinfo_t::nnbrs, graph_t::nvtxs, cnbr_t::pid, graph_t::pwgts, UpdateEdgeSubDomainGraph(), graph_t::vwgt, graph_t::where, where, graph_t::xadj, and xadj.

Referenced by EliminateSubDomainEdges().

Here is the call graph for this function:

Here is the caller graph for this function:

void MoveGroupMinConnForVol	(	ctrl_t *	ctrl,
		graph_t *	graph,
		idx_t	to,
		idx_t	nind,
		idx_t *	ind,
		idx_t *	vmarker,
		idx_t *	pmarker,
		idx_t *	modind
	)

This function moves a collection of vertices and updates their rinfo

Definition at line 561 of file minconn.c.

References graph_t::adjncy, adjncy, ComputeCut(), ComputeVolume(), vnbr_t::gv, vkrinfo_t::inbr, KWayVolUpdate(), PUP::l, graph_t::mincut, graph_t::minvol, graph_t::ncon, vnbr_t::ned, vkrinfo_t::ned, vkrinfo_t::nid, vkrinfo_t::nnbrs, graph_t::nvtxs, graph_t::pwgts, UpdateEdgeSubDomainGraph(), graph_t::vkrinfo, ctrl_t::vnbrpool, vnbrpoolGetNext(), graph_t::vsize, vsize, graph_t::vwgt, graph_t::where, where, graph_t::xadj, and xadj.

Referenced by EliminateSubDomainEdges().

Here is the call graph for this function:

Here is the caller graph for this function:

void PrintSubDomainGraph	(	graph_t *	graph,
		idx_t	nparts,
		idx_t *	where
	)

This function computes the subdomain graph. For deubuging purposes.

Definition at line 683 of file minconn.c.

References graph_t::adjncy, adjncy, graph_t::adjwgt, adjwgt, gk_free(), max(), graph_t::nvtxs, graph_t::xadj, and xadj.

Here is the call graph for this function: