kwayfm.c File Reference

Routines for k-way refinement. More...

#include "metislib.h"

Functions
void	Greedy_KWayOptimize (ctrl_t *ctrl, graph_t *graph, idx_t niter, real_t ffactor, idx_t omode)
void	Greedy_KWayCutOptimize (ctrl_t *ctrl, graph_t *graph, idx_t niter, real_t ffactor, idx_t omode)
void	Greedy_KWayVolOptimize (ctrl_t *ctrl, graph_t *graph, idx_t niter, real_t ffactor, idx_t omode)
void	Greedy_McKWayCutOptimize (ctrl_t *ctrl, graph_t *graph, idx_t niter, real_t ffactor, idx_t omode)
void	Greedy_McKWayVolOptimize (ctrl_t *ctrl, graph_t *graph, idx_t niter, real_t ffactor, idx_t omode)
idx_t	IsArticulationNode (idx_t i, idx_t *xadj, idx_t *adjncy, idx_t *where, idx_t *bfslvl, idx_t *bfsind, idx_t *bfsmrk)
void	KWayVolUpdate (ctrl_t *ctrl, graph_t *graph, idx_t v, idx_t from, idx_t to, ipq_t *queue, idx_t *vstatus, idx_t *r_nupd, idx_t *updptr, idx_t *updind, idx_t bndtype, idx_t *vmarker, idx_t *pmarker, idx_t *modind)

Detailed Description

Routines for k-way refinement.

Date

Started 7/28/97

Author

George

Copyright 1997-2009, Regents of the University of Minnesota

Version

Id

kwayfm.c 10567 2011-07-13 16:17:07Z karypis

Function Documentation

Greedy_KWayCutOptimize()

void Greedy_KWayCutOptimize	(	ctrl_t *	ctrl,
		graph_t *	graph,
		idx_t	niter,
		real_t	ffactor,
		idx_t	omode
	)

K-way partitioning optimization in which the vertices are visited in decreasing ed/sqrt(nnbrs)-id order. Note this is just an approximation, as the ed is often split across different subdomains and the sqrt(nnbrs) is just a crude approximation.

Parameters

graph	is the graph that is being refined.
niter	is the number of refinement iterations.
ffactor	is the fudge-factor for allowing positive gain moves to violate the max-pwgt constraint.
omode	is the type of optimization that will performed among OMODE_REFINE and OMODE_BALANCE

Greedy_KWayVolOptimize()

void Greedy_KWayVolOptimize	(	ctrl_t *	ctrl,
		graph_t *	graph,
		idx_t	niter,
		real_t	ffactor,
		idx_t	omode
	)

K-way refinement that minimizes the communication volume. This is a greedy routine and the vertices are visited in decreasing gv order.

Parameters

graph	is the graph that is being refined.
niter	is the number of refinement iterations.
ffactor	is the fudge-factor for allowing positive gain moves to violate the max-pwgt constraint.

Greedy_McKWayCutOptimize()

void Greedy_McKWayCutOptimize	(	ctrl_t *	ctrl,
		graph_t *	graph,
		idx_t	niter,
		real_t	ffactor,
		idx_t	omode
	)

K-way partitioning optimization in which the vertices are visited in decreasing ed/sqrt(nnbrs)-id order. Note this is just an approximation, as the ed is often split across different subdomains and the sqrt(nnbrs) is just a crude approximation.

Parameters

graph	is the graph that is being refined.
niter	is the number of refinement iterations.
ffactor	is the fudge-factor for allowing positive gain moves to violate the max-pwgt constraint.
omode	is the type of optimization that will performed among OMODE_REFINE and OMODE_BALANCE

Greedy_McKWayVolOptimize()

void Greedy_McKWayVolOptimize	(	ctrl_t *	ctrl,
		graph_t *	graph,
		idx_t	niter,
		real_t	ffactor,
		idx_t	omode
	)

K-way refinement that minimizes the communication volume. This is a greedy routine and the vertices are visited in decreasing gv order.

Parameters

graph	is the graph that is being refined.
niter	is the number of refinement iterations.
ffactor	is the fudge-factor for allowing positive gain moves to violate the max-pwgt constraint.

IsArticulationNode()

idx_t IsArticulationNode	(	idx_t	i,
		idx_t *	xadj,
		idx_t *	adjncy,
		idx_t *	where,
		idx_t *	bfslvl,
		idx_t *	bfsind,
		idx_t *	bfsmrk
	)

This function performs an approximate articulation vertex test. It assumes that the bfslvl, bfsind, and bfsmrk arrays are initialized appropriately.

KWayVolUpdate()

void KWayVolUpdate	(	ctrl_t *	ctrl,
		graph_t *	graph,
		idx_t	v,
		idx_t	from,
		idx_t	to,
		ipq_t *	queue,
		idx_t *	vstatus,
		idx_t *	r_nupd,
		idx_t *	updptr,
		idx_t *	updind,
		idx_t	bndtype,
		idx_t *	vmarker,
		idx_t *	pmarker,
		idx_t *	modind
	)

This function updates the edge and volume gains due to a vertex movement. v from 'from' to 'to'.

Parameters

ctrl	is the control structure.
graph	is the graph being partitioned.
v	is the vertex that is moving.
from	is the original partition of v.
to	is the new partition of v.
queue	is the priority queue. If the queue is NULL, no priority-queue related updates are performed.
vstatus	is an array that marks the status of the vertex in terms of the priority queue. If queue is NULL, this parameter is ignored.
r_nqupd	is the number of vertices that have been inserted/removed from the queue. If queue is NULL, this parameter is ignored.
updptr	stores the index of each vertex in updind. If queue is NULL, this parameter is ignored.
updind	is the list of vertices that have been inserted/removed from the queue. If queue is NULL, this parameter is ignored.
vmarker	is of size nvtxs and is used internally as a temporary array. On entry and return all of its entries are 0.
pmarker	is of sie nparts and is used internally as a temporary marking array. On entry and return all of its entries are -1.
modind	is an array of size nvtxs and is used to keep track of the list of vertices whose gains need to be updated.