Functions
kwayfm.c File Reference

Routines for k-way refinement. More...

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

Go to the source code of this file.

Functions

void Greedy_KWayCutOptimize (ctrl_t *ctrl, graph_t *graph, idx_t niter, real_t ffactor, idx_t omode)
 
void Greedy_KWayOptimize (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

Definition in file kwayfm.c.

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
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

Definition at line 60 of file kwayfm.c.

◆ Greedy_KWayOptimize()

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

Definition at line 20 of file kwayfm.c.

◆ 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
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.

Definition at line 370 of file kwayfm.c.

◆ 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
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

Definition at line 684 of file kwayfm.c.

◆ 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
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.

Definition at line 1026 of file kwayfm.c.

◆ 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.

Definition at line 1361 of file kwayfm.c.

◆ 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
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.

Definition at line 1460 of file kwayfm.c.



gtsam
Author(s):
autogenerated on Tue Jul 4 2023 02:40:49