Routines for k-way refinement. More...
#include "metislib.h"
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) |
Routines for k-way refinement.
Definition in file kwayfm.c.
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.
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 |
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.
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. |
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.
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 |
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.
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. |
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'.
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. |