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) |
Detailed Description
Routines for k-way refinement.
- Date
- Started 7/28/97
- Version
- Id
- kwayfm.c 10567 2011-07-13 16:17:07Z karypis
Definition in file kwayfm.c.
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
-
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.
- 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.
| 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
| 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.
| 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.