hp2FEM  0.1
Functions
src/metis-5.0/libmetis/kwayfm.c File Reference

Routines for k-way refinement. More...

#include "metislib.h"
Include dependency graph for kwayfm.c:

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

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:
graphis the graph that is being refined.
niteris the number of refinement iterations.
ffactoris the fudge-factor for allowing positive gain moves to violate the max-pwgt constraint.
omodeis the type of optimization that will performed among OMODE_REFINE and OMODE_BALANCE
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:
graphis the graph that is being refined.
niteris the number of refinement iterations.
ffactoris the fudge-factor for allowing positive gain moves to violate the max-pwgt constraint.
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:
graphis the graph that is being refined.
niteris the number of refinement iterations.
ffactoris the fudge-factor for allowing positive gain moves to violate the max-pwgt constraint.
omodeis the type of optimization that will performed among OMODE_REFINE and OMODE_BALANCE
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:
graphis the graph that is being refined.
niteris the number of refinement iterations.
ffactoris the fudge-factor for allowing positive gain moves to violate the max-pwgt constraint.
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.

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:
ctrlis the control structure.
graphis the graph being partitioned.
vis the vertex that is moving.
fromis the original partition of v.
tois the new partition of v.
queueis the priority queue. If the queue is NULL, no priority-queue related updates are performed.
vstatusis an array that marks the status of the vertex in terms of the priority queue. If queue is NULL, this parameter is ignored.
r_nqupdis the number of vertices that have been inserted/removed from the queue. If queue is NULL, this parameter is ignored.
updptrstores the index of each vertex in updind. If queue is NULL, this parameter is ignored.
updindis the list of vertices that have been inserted/removed from the queue. If queue is NULL, this parameter is ignored.
vmarkeris of size nvtxs and is used internally as a temporary array. On entry and return all of its entries are 0.
pmarkeris of sie nparts and is used internally as a temporary marking array. On entry and return all of its entries are -1.
modindis an array of size nvtxs and is used to keep track of the list of vertices whose gains need to be updated.
 All Classes Files Functions Variables Typedefs Friends Defines