libs/ck-libs/metis/libmetis/proto.h File Reference

Function Documentation

void Balance2Way	(	ctrl_t *	ctrl,
		graph_t *	graph,
		real_t *	ntpwgts
	)

Definition at line 16 of file balance.c.

References Bnd2WayBalance(), ComputeLoadImbalanceDiff(), General2WayBalance(), McGeneral2WayBalance(), graph_t::nbnd, graph_t::ncon, graph_t::nvtxs, ctrl_t::pijbm, graph_t::pwgts, graph_t::tvwgt, and ctrl_t::ubfactors.

Referenced by GrowBisection(), GrowBisectionNode(), McGrowBisection(), McRandomBisection(), RandomBisection(), and Refine2Way().

Here is the call graph for this function:

Here is the caller graph for this function:

void Bnd2WayBalance	(	ctrl_t *	ctrl,
		graph_t *	graph,
		real_t *	ntpwgts
	)

Definition at line 41 of file balance.c.

References graph_t::adjncy, adjncy, graph_t::adjwgt, adjwgt, graph_t::bndind, graph_t::bndptr, CheckBnd(), ComputeCut(), ctrl_t::dbglvl, graph_t::ed, graph_t::id, iwspacemalloc(), METIS_DBG_MOVEINFO, METIS_DBG_REFINE, graph_t::mincut, graph_t::nbnd, graph_t::nvtxs, perm, graph_t::pwgts, rpq_t, tpwgts, graph_t::tvwgt, graph_t::vwgt, vwgt, graph_t::where, where, graph_t::xadj, and xadj.

Referenced by Balance2Way().

Here is the call graph for this function:

Here is the caller graph for this function:

void General2WayBalance	(	ctrl_t *	ctrl,
		graph_t *	graph,
		real_t *	ntpwgts
	)

Definition at line 169 of file balance.c.

References graph_t::adjncy, adjncy, graph_t::adjwgt, adjwgt, graph_t::bndind, graph_t::bndptr, CheckBnd(), ComputeCut(), ctrl_t::dbglvl, graph_t::ed, graph_t::id, iwspacemalloc(), METIS_DBG_MOVEINFO, METIS_DBG_REFINE, graph_t::mincut, graph_t::nbnd, graph_t::nvtxs, perm, graph_t::pwgts, rpq_t, tpwgts, graph_t::tvwgt, graph_t::vwgt, vwgt, graph_t::where, where, graph_t::xadj, and xadj.

Referenced by Balance2Way(), and GrowBisectionNode2().

Here is the call graph for this function:

Here is the caller graph for this function:

void McGeneral2WayBalance	(	ctrl_t *	ctrl,
		graph_t *	graph,
		real_t *	ntpwgts
	)

Definition at line 281 of file balance.c.

References graph_t::adjncy, adjncy, graph_t::adjwgt, adjwgt, BetterBalance2Way(), graph_t::bndind, graph_t::bndptr, CheckBnd(), ComputeCut(), ComputeLoadImbalance(), ComputeLoadImbalanceDiffVec(), ctrl_t::dbglvl, graph_t::ed, iargmax2_nrm(), iargmax_nrm(), graph_t::id, graph_t::invtvwgt, iwspacemalloc(), PUP::l, METIS_DBG_MOVEINFO, METIS_DBG_REFINE, graph_t::mincut, graph_t::nbnd, graph_t::ncon, ncon, graph_t::nvtxs, perm, ctrl_t::pijbm, graph_t::pwgts, rpq_t, rwspacemalloc(), SelectQueue(), ctrl_t::ubfactors, graph_t::vwgt, vwgt, graph_t::where, where, wspacemalloc(), graph_t::xadj, and xadj.

Referenced by Balance2Way().

Here is the call graph for this function:

Here is the caller graph for this function:

void BucketSortKeysInc	(	ctrl_t *	ctrl,
		idx_t	n,
		idx_t	max,
		idx_t *	keys,
		idx_t *	tperm,
		idx_t *	perm
	)

Definition at line 23 of file bucketsort.c.

References iwspacemalloc().

Referenced by Match_SHEM().

Here is the call graph for this function:

Here is the caller graph for this function:

int CheckGraph	(	graph_t *	graph,
		int	numflag,
		int	verbose
	)

This function checks if a graph is valid. A valid graph must satisfy the following constraints:

It should contain no self-edges.
It should be undirected; i.e., (u,v) and (v,u) should be present.
The adjacency list should not contain multiple edges to the same other vertex.

Parameters:

	graph	is the graph to be checked, whose numbering starts from 0.
	numflag	is 0 if error reporting will be done using 0 as the numbering, or 1 if the reporting should be done using 1.
	verbose	is 1 the identified errors will be displayed, or 0, if it should run silently.

Definition at line 32 of file checkgraph.c.

References graph_t::adjncy, adjncy, graph_t::adjwgt, adjwgt, gk_free(), PUP::l, graph_t::nvtxs, graph_t::xadj, and xadj.

Referenced by CoarsenGraph(), CoarsenGraphNlevels(), main(), METIS_NodeND(), and SetupGraph().

Here is the call graph for this function:

Here is the caller graph for this function:

int CheckInputGraphWeights	(	idx_t	nvtxs,
		idx_t	ncon,
		idx_t *	xadj,
		idx_t *	adjncy,
		idx_t *	vwgt,
		idx_t *	vsize,
		idx_t *	adjwgt
	)

This function performs a quick check of the weights of the graph

Definition at line 120 of file checkgraph.c.

graph_t* FixGraph ( graph_t * graph )

This function creates a graph whose topology is consistent with Metis' requirements that:

There are no self-edges.
It is undirected; i.e., (u,v) and (v,u) should be present and of the same weight.
The adjacency list should not contain multiple edges to the same other vertex.

Any of the above errors are fixed by performing the following operations:

Self-edges are removed.
The undirected graph is formed by the union of edges.
One of the duplicate edges is selected.

The routine does not change the provided vertex weights.

Definition at line 176 of file checkgraph.c.

References graph_t::adjncy, adjncy, graph_t::adjwgt, adjwgt, CreateGraph(), edges, gk_free(), gk_malloc(), PUP::l, graph_t::ncon, graph_t::nvtxs, PUP::u, uvw_t::u, uvwsorti(), uvw_t::v, graph_t::vsize, graph_t::vwgt, uvw_t::w, graph_t::xadj, and xadj.

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

graph_t* CoarsenGraph	(	ctrl_t *	ctrl,
		graph_t *	graph
	)

This function takes a graph and creates a sequence of coarser graphs. It implements the coarsening phase of the multilevel paradigm.

Definition at line 22 of file coarsen.c.

References graph_t::adjwgt, CheckGraph(), graph_t::cmap, ctrl_t::CoarsenTmr, ctrl_t::CoarsenTo, graph_t::coarser, ctrl_t::ctype, ctrl_t::dbglvl, gk_errexit(), level, Match_RM(), Match_SHEM(), ctrl_t::maxvwgt, METIS_CTYPE_RM, METIS_CTYPE_SHEM, METIS_DBG_COARSEN, METIS_DBG_TIME, graph_t::ncon, graph_t::nedges, graph_t::nvtxs, PrintCGraphStats(), and graph_t::tvwgt.

Referenced by MlevelKWayPartitioning(), MlevelNodeBisectionL1(), and MultilevelBisect().

Here is the call graph for this function:

Here is the caller graph for this function:

graph_t* CoarsenGraphNlevels	(	ctrl_t *	ctrl,
		graph_t *	graph,
		idx_t	nlevels
	)

This function takes a graph and creates a sequence of nlevels coarser graphs, where nlevels is an input parameter.

Definition at line 85 of file coarsen.c.

References graph_t::adjwgt, CheckGraph(), graph_t::cmap, ctrl_t::CoarsenTmr, ctrl_t::CoarsenTo, graph_t::coarser, ctrl_t::ctype, ctrl_t::dbglvl, graph_t::finer, gk_errexit(), level, Match_RM(), Match_SHEM(), ctrl_t::maxvwgt, METIS_CTYPE_RM, METIS_CTYPE_SHEM, METIS_DBG_COARSEN, METIS_DBG_TIME, graph_t::ncon, graph_t::nedges, graph_t::nvtxs, PrintCGraphStats(), and graph_t::tvwgt.

Referenced by MlevelNodeBisectionL2().

Here is the call graph for this function:

Here is the caller graph for this function:

idx_t Match_RM	(	ctrl_t *	ctrl,
		graph_t *	graph
	)

This function finds a matching by randomly selecting one of the unmatched adjacent vertices.

Definition at line 149 of file coarsen.c.

References graph_t::adjncy, adjncy, graph_t::adjwgt, adjwgt, graph_t::cmap, CreateCoarseGraph(), ctrl_t::dbglvl, ivecaxpylez(), ivecle(), iwspacemalloc(), match(), Match_2Hop(), ctrl_t::MatchTmr, ctrl_t::maxvwgt, METIS_DBG_TIME, graph_t::ncon, ncon, ctrl_t::no2hop, graph_t::nvtxs, perm, graph_t::vwgt, vwgt, graph_t::xadj, and xadj.

Referenced by CoarsenGraph(), and CoarsenGraphNlevels().

Here is the call graph for this function:

Here is the caller graph for this function:

idx_t Match_SHEM	(	ctrl_t *	ctrl,
		graph_t *	graph
	)

This function finds a matching using the HEM heuristic. The vertices are visited based on increasing degree to ensure that all vertices are given a chance to match with something.

Definition at line 276 of file coarsen.c.

References graph_t::adjncy, adjncy, graph_t::adjwgt, adjwgt, BetterVBalance(), BucketSortKeysInc(), graph_t::cmap, CreateCoarseGraph(), ctrl_t::dbglvl, degrees, graph_t::invtvwgt, ivecaxpylez(), ivecle(), iwspacemalloc(), match(), Match_2Hop(), ctrl_t::MatchTmr, ctrl_t::maxvwgt, METIS_DBG_TIME, graph_t::ncon, ncon, ctrl_t::no2hop, graph_t::nvtxs, perm, graph_t::vwgt, vwgt, graph_t::xadj, and xadj.

Referenced by CoarsenGraph(), and CoarsenGraphNlevels().

Here is the call graph for this function:

Here is the caller graph for this function:

idx_t Match_2Hop	(	ctrl_t *	ctrl,
		graph_t *	graph,
		idx_t *	perm,
		idx_t *	match,
		idx_t	cnvtxs,
		size_t	nunmatched
	)

This function matches the unmatched vertices using a 2-hop matching that involves vertices that are two hops away from each other.

Definition at line 415 of file coarsen.c.

References Match_2HopAll(), Match_2HopAny(), and graph_t::nvtxs.

Referenced by Match_RM(), and Match_SHEM().

Here is the call graph for this function:

Here is the caller graph for this function:

idx_t Match_2HopAny	(	ctrl_t *	ctrl,
		graph_t *	graph,
		idx_t *	perm,
		idx_t *	match,
		idx_t	cnvtxs,
		size_t *	r_nunmatched,
		size_t	maxdegree
	)

This function matches the unmatched vertices whose degree is less than maxdegree using a 2-hop matching that involves vertices that are two hops away from each other. The requirement of the 2-hop matching is a simple non-empty overlap between the adjancency lists of the vertices.

Definition at line 437 of file coarsen.c.

References graph_t::adjncy, adjncy, ctrl_t::Aux3Tmr, graph_t::cmap, ctrl_t::dbglvl, iwspacemalloc(), METIS_DBG_TIME, graph_t::nvtxs, graph_t::xadj, and xadj.

Referenced by Match_2Hop().

Here is the call graph for this function:

Here is the caller graph for this function:

idx_t Match_2HopAll	(	ctrl_t *	ctrl,
		graph_t *	graph,
		idx_t *	perm,
		idx_t *	match,
		idx_t	cnvtxs,
		size_t *	r_nunmatched,
		size_t	maxdegree
	)

This function matches the unmatched vertices whose degree is less than maxdegree using a 2-hop matching that involves vertices that are two hops away from each other. The requirement of the 2-hop matching is that of identical adjacency lists.

Definition at line 516 of file coarsen.c.

References graph_t::adjncy, adjncy, ctrl_t::Aux3Tmr, graph_t::cmap, ctrl_t::dbglvl, ikvsorti(), ikvwspacemalloc(), iwspacemalloc(), key, METIS_DBG_TIME, graph_t::nvtxs, graph_t::xadj, and xadj.

Referenced by Match_2Hop().

Here is the call graph for this function:

Here is the caller graph for this function:

void PrintCGraphStats	(	ctrl_t *	ctrl,
		graph_t *	graph
	)

This function prints various stats for each graph during coarsening

Definition at line 601 of file coarsen.c.

References graph_t::adjwgt, ctrl_t::CoarsenTo, ctrl_t::maxvwgt, graph_t::ncon, graph_t::nedges, graph_t::nvtxs, and graph_t::tvwgt.

Referenced by CoarsenGraph(), and CoarsenGraphNlevels().

Here is the caller graph for this function:

void CreateCoarseGraph	(	ctrl_t *	ctrl,
		graph_t *	graph,
		idx_t	cnvtxs,
		idx_t *	match
	)

This function creates the coarser graph. It uses a simple hash-table for identifying the adjacent vertices that get collapsed to the same node. The hash-table can have conflicts, which are handled via a linear scan.

Definition at line 621 of file coarsen.c.

References graph_t::adjncy, adjncy, graph_t::adjwgt, adjwgt, graph_t::cmap, ctrl_t::ContractTmr, CreateCoarseGraphNoMask(), ctrl_t::dbglvl, graph_t::invtvwgt, iwspacemalloc(), PUP::l, PUP::m, METIS_DBG_TIME, METIS_OBJTYPE_VOL, graph_t::ncon, ncon, graph_t::nedges, graph_t::nvtxs, ctrl_t::objtype, ReAdjustMemory(), SetupCoarseGraph(), graph_t::tvwgt, PUP::u, graph_t::vsize, vsize, graph_t::vwgt, vwgt, graph_t::xadj, and xadj.

Referenced by Match_RM(), and Match_SHEM().

Here is the call graph for this function:

Here is the caller graph for this function:

void CreateCoarseGraphNoMask	(	ctrl_t *	ctrl,
		graph_t *	graph,
		idx_t	cnvtxs,
		idx_t *	match
	)

This function creates the coarser graph. It uses a full-size array (htable) for identifying the adjacent vertices that get collapsed to the same node.

Definition at line 800 of file coarsen.c.

References graph_t::adjncy, adjncy, graph_t::adjwgt, adjwgt, graph_t::cmap, ctrl_t::ContractTmr, ctrl_t::dbglvl, graph_t::invtvwgt, iwspacemalloc(), PUP::m, METIS_DBG_TIME, METIS_OBJTYPE_VOL, graph_t::ncon, ncon, graph_t::nedges, graph_t::nvtxs, ctrl_t::objtype, ReAdjustMemory(), SetupCoarseGraph(), graph_t::tvwgt, PUP::u, graph_t::vsize, vsize, graph_t::vwgt, vwgt, graph_t::xadj, and xadj.

Referenced by CreateCoarseGraph().

Here is the call graph for this function:

Here is the caller graph for this function:

void CreateCoarseGraphPerm	(	ctrl_t *	ctrl,
		graph_t *	graph,
		idx_t	cnvtxs,
		idx_t *	match,
		idx_t *	perm
	)

This function creates the coarser graph. It uses a simple hash-table for identifying the adjacent vertices that get collapsed to the same node. The hash-table can have conflicts, which are handled via a linear scan. It relies on the perm[] array to visit the vertices in increasing cnvtxs order.

Definition at line 932 of file coarsen.c.

References graph_t::adjncy, adjncy, graph_t::adjwgt, adjwgt, graph_t::cmap, ctrl_t::ContractTmr, ctrl_t::dbglvl, graph_t::invtvwgt, iwspacemalloc(), PUP::l, PUP::m, METIS_DBG_TIME, METIS_OBJTYPE_VOL, graph_t::ncon, ncon, graph_t::nedges, graph_t::nvtxs, ctrl_t::objtype, ReAdjustMemory(), SetupCoarseGraph(), graph_t::tvwgt, PUP::u, graph_t::vsize, vsize, graph_t::vwgt, vwgt, graph_t::xadj, and xadj.

Here is the call graph for this function:

graph_t* SetupCoarseGraph	(	graph_t *	graph,
		idx_t	cnvtxs,
		idx_t	dovsize
	)

Setup the various arrays for the coarse graph

Definition at line 1093 of file coarsen.c.

References graph_t::adjncy, graph_t::adjwgt, graph_t::coarser, CreateGraph(), graph_t::finer, graph_t::invtvwgt, graph_t::ncon, graph_t::nedges, graph_t::nvtxs, graph_t::tvwgt, graph_t::vsize, graph_t::vwgt, and graph_t::xadj.

Referenced by CreateCoarseGraph(), CreateCoarseGraphNoMask(), and CreateCoarseGraphPerm().

Here is the call graph for this function:

Here is the caller graph for this function:

void ReAdjustMemory	(	ctrl_t *	ctrl,
		graph_t *	graph,
		graph_t *	cgraph
	)

This function re-adjusts the amount of memory that was allocated if it will lead to significant savings

Definition at line 1126 of file coarsen.c.

References graph_t::adjncy, graph_t::adjwgt, and graph_t::nedges.

Referenced by CreateCoarseGraph(), CreateCoarseGraphNoMask(), and CreateCoarseGraphPerm().

Here is the caller graph for this function:

graph_t* CompressGraph	(	ctrl_t *	ctrl,
		idx_t	nvtxs,
		idx_t *	xadj,
		idx_t *	adjncy,
		idx_t *	vwgt,
		idx_t *	cptr,
		idx_t *	cind
	)

This function compresses a graph by merging identical vertices The compression should lead to at least 10% reduction.

The compressed graph that is generated has its adjwgts set to 1.

Returns:: 1 if compression was performed, otherwise it returns 0.

Definition at line 25 of file compress.c.

References graph_t::adjncy, graph_t::adjwgt, CreateGraph(), ctrl_t::dbglvl, gk_free(), ikvsorti(), key, PUP::l, METIS_DBG_INFO, graph_t::ncon, graph_t::nedges, graph_t::nvtxs, SetupGraph_label(), SetupGraph_tvwgt(), graph_t::vwgt, and graph_t::xadj.

Referenced by METIS_NodeND(), and METIS_NodeNDP().

Here is the call graph for this function:

Here is the caller graph for this function:

graph_t* PruneGraph	(	ctrl_t *	ctrl,
		idx_t	nvtxs,
		idx_t *	xadj,
		idx_t *	adjncy,
		idx_t *	vwgt,
		idx_t *	iperm,
		real_t	factor
	)

This function prunes all the vertices in a graph with degree greater than factor*average.

Returns:: the number of vertices that were prunned.

Definition at line 150 of file compress.c.

References graph_t::adjncy, graph_t::adjwgt, CreateGraph(), ctrl_t::dbglvl, gk_free(), PUP::l, METIS_DBG_INFO, graph_t::ncon, graph_t::nedges, graph_t::nvtxs, perm, SetupGraph_label(), SetupGraph_tvwgt(), graph_t::vwgt, and graph_t::xadj.

Referenced by METIS_NodeND().

Here is the call graph for this function:

Here is the caller graph for this function:

idx_t FindPartitionInducedComponents	(	graph_t *	graph,
		idx_t *	where,
		idx_t *	cptr,
		idx_t *	cind
	)

This function finds the connected components induced by the partitioning vector.

Parameters:

	graph	is the graph structure
	where	is the partitioning vector. If this is NULL, then the entire graph is treated to belong into a single partition.
	cptr	is the ptr structure of the CSR representation of the components. The length of this vector must be graph->nvtxs+1.
	cind	is the indices structure of the CSR representation of the components. The length of this vector must be graph->nvtxs.

Returns:: the number of components that it found.

Note:: The cptr and cind parameters can be NULL, in which case only the number of connected components is returned.

Definition at line 32 of file contig.c.

References graph_t::adjncy, adjncy, gk_free(), graph_t::nvtxs, perm, graph_t::xadj, and xadj.

Referenced by ComputePartitionInfo(), EliminateComponents(), IsConnected(), and RefineKWay().

Here is the call graph for this function:

Here is the caller graph for this function:

void ComputeBFSOrdering	(	ctrl_t *	ctrl,
		graph_t *	graph,
		idx_t *	bfsperm
	)

This function computes a permutation of the vertices based on a breadth-first-traversal. It can be used for re-ordering the graph to reduce its bandwidth for better cache locality.

Parameters:

	ctrl	is the control structure
	graph	is the graph structure
	perm	is the array that upon completion, perm[i] will store the ID of the vertex that corresponds to the ith vertex in the re-ordered graph.

Definition at line 115 of file contig.c.

References graph_t::adjncy, adjncy, iwspacemalloc(), graph_t::nvtxs, perm, graph_t::xadj, and xadj.

Here is the call graph for this function:

idx_t IsConnected	(	graph_t *	graph,
		idx_t	report
	)

This function checks whether a graph is contiguous or not.

Definition at line 167 of file contig.c.

References FindPartitionInducedComponents().

Referenced by ComputePartitionInfo(), main(), and METIS_PartGraphKway().

Here is the call graph for this function:

Here is the caller graph for this function:

idx_t IsConnectedSubdomain	(	ctrl_t *	ctrl,
		graph_t *	graph,
		idx_t	pid,
		idx_t	report
	)

This function checks whether or not partition pid is contigous

Definition at line 184 of file contig.c.

References graph_t::adjncy, adjncy, gk_free(), graph_t::nvtxs, graph_t::vwgt, graph_t::where, where, graph_t::xadj, and xadj.

Here is the call graph for this function:

idx_t FindSepInducedComponents	(	ctrl_t *	ctrl,
		graph_t *	graph,
		idx_t *	cptr,
		idx_t *	cind
	)

This function identifies the number of connected components in a graph that result after removing the vertices that belong to the vertex separator (i.e., graph->where[i] == 2). The connected component memberships are returned in the CSR-style pair of arrays cptr, cind.

Definition at line 267 of file contig.c.

References graph_t::adjncy, adjncy, graph_t::bndind, gk_free(), graph_t::nbnd, graph_t::nvtxs, graph_t::where, where, graph_t::xadj, and xadj.

Referenced by MlevelNestedDissectionCC().

Here is the call graph for this function:

Here is the caller graph for this function:

void EliminateComponents	(	ctrl_t *	ctrl,
		graph_t *	graph
	)

This function finds all the connected components induced by the partitioning vector in graph->where and tries to push them around to remove some of them.

Definition at line 336 of file contig.c.

References graph_t::adjncy, adjncy, graph_t::adjwgt, adjwgt, BetterBalanceKWay(), ctrl_t::dbglvl, FindPartitionInducedComponents(), gk_errexit(), iwspacemalloc(), key, METIS_DBG_CONTIGINFO, METIS_OBJTYPE_CUT, METIS_OBJTYPE_VOL, MoveGroupContigForCut(), MoveGroupContigForVol(), graph_t::ncon, ncon, ctrl_t::nparts, nparts, graph_t::nvtxs, ctrl_t::objtype, ctrl_t::pijbm, graph_t::pwgts, rkvsortd(), ctrl_t::tpwgts, tpwgts, ctrl_t::ubfactors, graph_t::vwgt, vwgt, graph_t::where, where, wspacemalloc(), graph_t::xadj, and xadj.

Referenced by RefineKWay().

Here is the call graph for this function:

Here is the caller graph for this function:

void MoveGroupContigForCut	(	ctrl_t *	ctrl,
		graph_t *	graph,
		idx_t	to,
		idx_t	gid,
		idx_t *	ptr,
		idx_t *	ind
	)

This function moves a collection of vertices and updates their rinfo

Definition at line 531 of file contig.c.

References graph_t::adjncy, adjncy, graph_t::adjwgt, adjwgt, graph_t::bndind, graph_t::bndptr, CheckRInfo(), graph_t::ckrinfo, ctrl_t::cnbrpool, cnbrpoolGetNext(), cnbr_t::ed, ckrinfo_t::id, ckrinfo_t::inbr, PUP::l, graph_t::mincut, graph_t::nbnd, graph_t::ncon, ckrinfo_t::nnbrs, graph_t::nvtxs, cnbr_t::pid, graph_t::pwgts, graph_t::vwgt, graph_t::where, where, graph_t::xadj, and xadj.

Referenced by EliminateComponents().

Here is the call graph for this function:

Here is the caller graph for this function:

void MoveGroupContigForVol	(	ctrl_t *	ctrl,
		graph_t *	graph,
		idx_t	to,
		idx_t	gid,
		idx_t *	ptr,
		idx_t *	ind,
		idx_t *	vmarker,
		idx_t *	pmarker,
		idx_t *	modind
	)

This function moves a collection of vertices and updates their rinfo

Definition at line 601 of file contig.c.

References graph_t::adjncy, adjncy, ComputeCut(), ComputeVolume(), vnbr_t::gv, vkrinfo_t::inbr, KWayVolUpdate(), PUP::l, graph_t::mincut, graph_t::minvol, graph_t::ncon, vnbr_t::ned, vkrinfo_t::ned, vkrinfo_t::nid, vkrinfo_t::nnbrs, graph_t::nvtxs, graph_t::pwgts, graph_t::vkrinfo, ctrl_t::vnbrpool, vnbrpoolGetNext(), graph_t::vsize, vsize, graph_t::vwgt, graph_t::where, where, graph_t::xadj, and xadj.

Referenced by EliminateComponents().

Here is the call graph for this function:

Here is the caller graph for this function:

idx_t ComputeCut	(	graph_t *	graph,
		idx_t *	where
	)

This function computes the total edgecut

Definition at line 21 of file debug.c.

References graph_t::adjncy, graph_t::adjwgt, graph_t::nvtxs, xadj, and graph_t::xadj.

Referenced by Bnd2WayBalance(), ComputePartitionInfo(), ComputePartitionInfoBipartite(), FM_2WayCutRefine(), FM_Mc2WayCutRefine(), General2WayBalance(), Greedy_KWayCutOptimize(), Greedy_McKWayCutOptimize(), McGeneral2WayBalance(), MoveGroupContigForVol(), MoveGroupMinConnForCut(), and MoveGroupMinConnForVol().

Here is the caller graph for this function:

idx_t ComputeVolume	(	graph_t *	graph,
		idx_t *	where
	)

This function computes the total volume

Definition at line 48 of file debug.c.

References graph_t::adjncy, adjncy, gk_free(), nparts, graph_t::nvtxs, graph_t::vsize, vsize, graph_t::xadj, and xadj.

Referenced by ComputeKWayPartitionParams(), ComputePartitionInfo(), ComputePartitionInfoBipartite(), Greedy_KWayCutOptimize(), Greedy_KWayVolOptimize(), Greedy_McKWayCutOptimize(), Greedy_McKWayVolOptimize(), InitKWayPartitioning(), MoveGroupContigForVol(), MoveGroupMinConnForVol(), and ProjectKWayPartition().

Here is the call graph for this function:

Here is the caller graph for this function:

idx_t ComputeMaxCut	(	graph_t *	graph,
		idx_t	nparts,
		idx_t *	where
	)

This function computes the cut given the graph and a where vector

Definition at line 85 of file debug.c.

References graph_t::adjncy, graph_t::adjwgt, gk_free(), graph_t::nvtxs, xadj, and graph_t::xadj.

Here is the call graph for this function:

idx_t CheckBnd ( graph_t * graph )

This function checks whether or not the boundary information is correct

Definition at line 121 of file debug.c.

References graph_t::adjncy, adjncy, graph_t::bndind, graph_t::bndptr, graph_t::nbnd, graph_t::nvtxs, graph_t::where, where, graph_t::xadj, and xadj.

Referenced by Bnd2WayBalance(), FM_2WayCutRefine(), FM_Mc2WayCutRefine(), General2WayBalance(), McGeneral2WayBalance(), and Refine2Way().

Here is the caller graph for this function:

idx_t CheckBnd2 ( graph_t * graph )

This function checks whether or not the boundary information is correct

Definition at line 158 of file debug.c.

References graph_t::adjncy, adjncy, graph_t::adjwgt, graph_t::bndind, graph_t::bndptr, graph_t::nbnd, graph_t::nvtxs, graph_t::where, where, graph_t::xadj, and xadj.

Referenced by ComputeKWayPartitionParams(), and ProjectKWayPartition().

Here is the caller graph for this function:

idx_t CheckNodeBnd	(	graph_t *	graph,
		idx_t	onbnd
	)

This function checks whether or not the boundary information is correct

Definition at line 195 of file debug.c.

References graph_t::adjncy, adjncy, graph_t::bndind, graph_t::bndptr, graph_t::nvtxs, graph_t::where, where, graph_t::xadj, and xadj.

Referenced by Compute2WayNodePartitionParams(), FM_2WayNodeBalance(), FM_2WayNodeRefine1Sided(), FM_2WayNodeRefine1SidedP(), FM_2WayNodeRefine2Sided(), and FM_2WayNodeRefine2SidedP().

Here is the caller graph for this function:

idx_t CheckRInfo	(	ctrl_t *	ctrl,
		ckrinfo_t *	rinfo
	)

This function checks whether or not the rinfo of a vertex is consistent

Definition at line 232 of file debug.c.

References ctrl_t::cnbrpool, ckrinfo_t::inbr, and ckrinfo_t::nnbrs.

Referenced by MoveGroupContigForCut().

Here is the caller graph for this function:

idx_t CheckNodePartitionParams ( graph_t * graph )

This function checks the correctness of the NodeFM data structures

Definition at line 255 of file debug.c.

References graph_t::adjncy, adjncy, graph_t::adjwgt, adjwgt, nrinfo_t::edegrees, PUP::l, graph_t::nrinfo, graph_t::nvtxs, graph_t::pwgts, graph_t::vwgt, vwgt, graph_t::where, where, graph_t::xadj, and xadj.

Referenced by ConstructMinCoverSeparator(), ConstructSeparator(), FM_2WayNodeBalance(), FM_2WayNodeRefine1Sided(), FM_2WayNodeRefine1SidedP(), FM_2WayNodeRefine2Sided(), FM_2WayNodeRefine2SidedP(), and Refine2WayNode().

Here is the caller graph for this function:

idx_t IsSeparable ( graph_t * graph )

This function checks if the separator is indeed a separator

Definition at line 309 of file debug.c.

References graph_t::adjncy, adjncy, graph_t::nvtxs, graph_t::where, where, graph_t::xadj, and xadj.

Referenced by ConstructMinCoverSeparator(), and ConstructSeparator().

Here is the caller graph for this function:

void CheckKWayVolPartitionParams	(	ctrl_t *	ctrl,
		graph_t *	graph
	)

This function recomputes the vrinfo fields and checks them against those in the graph->vrinfo structure

Definition at line 339 of file debug.c.

References graph_t::adjncy, adjncy, vnbr_t::gv, vkrinfo_t::inbr, PUP::l, vkrinfo_t::ned, vkrinfo_t::nid, vkrinfo_t::nnbrs, ctrl_t::nparts, graph_t::nvtxs, vnbr_t::pid, graph_t::vkrinfo, ctrl_t::vnbrpool, graph_t::vsize, vsize, graph_t::where, where, wspacemalloc(), graph_t::xadj, and xadj.

Here is the call graph for this function:

void FM_2WayRefine	(	ctrl_t *	ctrl,
		graph_t *	graph,
		real_t *	ntpwgts,
		idx_t	niter
	)

Definition at line 17 of file fm.c.

References FM_2WayCutRefine(), FM_Mc2WayCutRefine(), and graph_t::ncon.

Referenced by GrowBisection(), GrowBisectionNode(), GrowBisectionNode2(), McGrowBisection(), McRandomBisection(), RandomBisection(), and Refine2Way().

Here is the call graph for this function:

Here is the caller graph for this function:

void FM_2WayCutRefine	(	ctrl_t *	ctrl,
		graph_t *	graph,
		real_t *	ntpwgts,
		idx_t	niter
	)

This function performs a cut-focused FM refinement

Definition at line 29 of file fm.c.

References graph_t::adjncy, adjncy, graph_t::adjwgt, adjwgt, graph_t::bndind, graph_t::bndptr, CheckBnd(), ComputeCut(), ctrl_t::dbglvl, graph_t::ed, graph_t::id, iwspacemalloc(), METIS_DBG_MOVEINFO, METIS_DBG_REFINE, graph_t::mincut, graph_t::nbnd, graph_t::nvtxs, perm, Print2WayRefineStats(), graph_t::pwgts, rpq_t, tpwgts, graph_t::tvwgt, graph_t::vwgt, vwgt, graph_t::where, where, graph_t::xadj, and xadj.

Referenced by FM_2WayRefine().

Here is the call graph for this function:

Here is the caller graph for this function:

void FM_Mc2WayCutRefine	(	ctrl_t *	ctrl,
		graph_t *	graph,
		real_t *	ntpwgts,
		idx_t	niter
	)

This function performs a cut-focused multi-constraint FM refinement

Definition at line 207 of file fm.c.

References graph_t::adjncy, adjncy, graph_t::adjwgt, adjwgt, BetterBalance2Way(), graph_t::bndind, graph_t::bndptr, CheckBnd(), ComputeCut(), ComputeLoadImbalance(), ComputeLoadImbalanceDiffVec(), ctrl_t::dbglvl, graph_t::ed, iargmax_nrm(), graph_t::id, graph_t::invtvwgt, iwspacemalloc(), PUP::l, METIS_DBG_MOVEINFO, METIS_DBG_REFINE, graph_t::mincut, graph_t::nbnd, graph_t::ncon, ncon, graph_t::nvtxs, perm, ctrl_t::pijbm, Print2WayRefineStats(), graph_t::pwgts, rpq_t, rwspacemalloc(), SelectQueue(), ctrl_t::ubfactors, graph_t::vwgt, vwgt, graph_t::where, where, wspacemalloc(), graph_t::xadj, and xadj.

Referenced by FM_2WayRefine().

Here is the call graph for this function:

Here is the caller graph for this function:

void SelectQueue	(	graph_t *	graph,
		real_t *	pijbm,
		real_t *	ubfactors,
		rpq_t **	queues,
		idx_t *	from,
		idx_t *	cnum
	)

This function selects the partition number and the queue from which we will move vertices out.

Definition at line 439 of file fm.c.

References max(), graph_t::ncon, ncon, part, and graph_t::pwgts.

Referenced by FM_Mc2WayCutRefine(), and McGeneral2WayBalance().

Here is the call graph for this function:

Here is the caller graph for this function:

void Print2WayRefineStats	(	ctrl_t *	ctrl,
		graph_t *	graph,
		real_t *	ntpwgts,
		real_t	deltabal,
		idx_t	mincutorder
	)

Prints statistics about the refinement

Definition at line 515 of file fm.c.

References ComputeLoadImbalance(), graph_t::invtvwgt, graph_t::mincut, graph_t::nbnd, graph_t::ncon, graph_t::nvtxs, ctrl_t::pijbm, and graph_t::pwgts.

Referenced by FM_2WayCutRefine(), and FM_Mc2WayCutRefine().

Here is the call graph for this function:

Here is the caller graph for this function:

void Change2CNumbering	(	idx_t	nvtxs,
		idx_t *	xadj,
		idx_t *	adjncy
	)

This function changes the numbering to start from 0 instead of 1

Definition at line 19 of file fortran.c.

Referenced by METIS_NodeND(), METIS_PartGraphKway(), and METIS_PartGraphRecursive().

Here is the caller graph for this function:

void Change2FNumbering	(	idx_t	nvtxs,
		idx_t *	xadj,
		idx_t *	adjncy,
		idx_t *	vector
	)

This function changes the numbering to start from 1 instead of 0

Definition at line 34 of file fortran.c.

Referenced by METIS_PartGraphKway(), and METIS_PartGraphRecursive().

Here is the caller graph for this function:

void Change2FNumbering2	(	idx_t	nvtxs,
		idx_t *	xadj,
		idx_t *	adjncy
	)

This function changes the numbering to start from 1 instead of 0

Definition at line 51 of file fortran.c.

void Change2FNumberingOrder	(	idx_t	nvtxs,
		idx_t *	xadj,
		idx_t *	adjncy,
		idx_t *	v1,
		idx_t *	v2
	)

This function changes the numbering to start from 1 instead of 0

Definition at line 68 of file fortran.c.

Referenced by METIS_NodeND().

Here is the caller graph for this function:

void ChangeMesh2CNumbering	(	idx_t	n,
		idx_t *	ptr,
		idx_t *	ind
	)

This function changes the numbering to start from 0 instead of 1

Definition at line 92 of file fortran.c.

Referenced by METIS_MeshToDual(), METIS_MeshToNodal(), METIS_PartMeshDual(), and METIS_PartMeshNodal().

Here is the caller graph for this function:

void ChangeMesh2FNumbering	(	idx_t	n,
		idx_t *	ptr,
		idx_t *	ind,
		idx_t	nvtxs,
		idx_t *	xadj,
		idx_t *	adjncy
	)

This function changes the numbering to start from 1 instead of 0

Definition at line 106 of file fortran.c.

Referenced by METIS_MeshToDual(), and METIS_MeshToNodal().

Here is the caller graph for this function:

void ChangeMesh2FNumbering2	(	idx_t	ne,
		idx_t	nn,
		idx_t *	ptr,
		idx_t *	ind,
		idx_t *	epart,
		idx_t *	npart
	)

This function changes the numbering to start from 1 instead of 0

Definition at line 126 of file fortran.c.

Referenced by METIS_PartMeshDual(), and METIS_PartMeshNodal().

Here is the caller graph for this function:

graph_t* SetupGraph	(	ctrl_t *	ctrl,
		idx_t	nvtxs,
		idx_t	ncon,
		idx_t *	xadj,
		idx_t *	adjncy,
		idx_t *	vwgt,
		idx_t *	vsize,
		idx_t *	adjwgt
	)

This function sets up the graph from the user input

Definition at line 17 of file graph.c.

References graph_t::adjncy, graph_t::adjwgt, CheckGraph(), CreateGraph(), graph_t::free_adjncy, graph_t::free_adjwgt, graph_t::free_vsize, graph_t::free_vwgt, graph_t::free_xadj, graph_t::invtvwgt, METIS_OBJTYPE_VOL, METIS_OP_OMETIS, METIS_OP_PMETIS, graph_t::ncon, graph_t::nedges, ctrl_t::numflag, graph_t::nvtxs, ctrl_t::objtype, ctrl_t::optype, SetupGraph_label(), SetupGraph_tvwgt(), graph_t::tvwgt, graph_t::vsize, graph_t::vwgt, and graph_t::xadj.

Referenced by METIS_ComputeVertexSeparator(), METIS_NodeND(), METIS_NodeNDP(), METIS_NodeRefine(), METIS_PartGraphKway(), and METIS_PartGraphRecursive().

Here is the call graph for this function:

Here is the caller graph for this function:

void SetupGraph_tvwgt ( graph_t * graph )

Set's up the tvwgt/invtvwgt info

Definition at line 99 of file graph.c.

References graph_t::invtvwgt, graph_t::ncon, graph_t::nvtxs, graph_t::tvwgt, and graph_t::vwgt.

Referenced by CompressGraph(), PruneGraph(), SetupGraph(), SplitGraphOrder(), SplitGraphOrderCC(), and SplitGraphPart().

Here is the caller graph for this function:

void SetupGraph_label ( graph_t * graph )

Set's up the label info

Definition at line 118 of file graph.c.

References graph_t::label, and graph_t::nvtxs.

Referenced by CompressGraph(), PruneGraph(), and SetupGraph().

Here is the caller graph for this function:

graph_t* SetupSplitGraph	(	graph_t *	graph,
		idx_t	snvtxs,
		idx_t	snedges
	)

Setup the various arrays for the splitted graph

Definition at line 133 of file graph.c.

References graph_t::adjncy, graph_t::adjwgt, CreateGraph(), graph_t::invtvwgt, graph_t::label, graph_t::ncon, graph_t::nedges, graph_t::nvtxs, graph_t::tvwgt, graph_t::vsize, graph_t::vwgt, and graph_t::xadj.

Referenced by SplitGraphOrder(), SplitGraphOrderCC(), and SplitGraphPart().

Here is the call graph for this function:

Here is the caller graph for this function:

graph_t* CreateGraph ( void )

This function creates and initializes a graph_t data structure

Definition at line 162 of file graph.c.

References gk_malloc(), and InitGraph().

Referenced by CompressGraph(), FixGraph(), main(), PruneGraph(), ReadGraph(), SetupCoarseGraph(), SetupGraph(), and SetupSplitGraph().

Here is the call graph for this function:

Here is the caller graph for this function:

void InitGraph ( graph_t * graph )

This function initializes a graph_t data structure

Definition at line 177 of file graph.c.

Referenced by CreateGraph().

Here is the caller graph for this function:

void FreeRData ( graph_t * graph )

This function frees the refinement/partition memory stored in a graph

Definition at line 228 of file graph.c.

References graph_t::bndind, graph_t::bndptr, graph_t::ckrinfo, graph_t::ed, gk_free(), graph_t::id, graph_t::nrinfo, graph_t::pwgts, graph_t::vkrinfo, and graph_t::where.

Referenced by ConstructMinCoverSeparator(), ConstructSeparator(), FreeGraph(), MlevelKWayPartitioning(), MlevelNodeBisectionL2(), MlevelNodeBisectionMultiple(), and MultilevelBisect().

Here is the call graph for this function:

Here is the caller graph for this function:

void FreeGraph ( graph_t ** r_graph )

This function deallocates any memory stored in a graph

Definition at line 247 of file graph.c.

References graph_t::adjncy, graph_t::adjwgt, graph_t::cmap, graph_t::free_adjncy, graph_t::free_adjwgt, graph_t::free_vsize, graph_t::free_vwgt, graph_t::free_xadj, FreeRData(), gk_free(), graph_t::invtvwgt, graph_t::label, graph_t::tvwgt, graph_t::vsize, graph_t::vwgt, and graph_t::xadj.

Referenced by main(), METIS_ComputeVertexSeparator(), METIS_NodeRefine(), MlevelKWayPartitioning(), MlevelNestedDissection(), MlevelNestedDissectionCC(), MlevelNestedDissectionP(), MlevelRecursiveBisection(), Project2WayNodePartition(), Project2WayPartition(), and ProjectKWayPartition().

Here is the call graph for this function:

Here is the caller graph for this function:

void Init2WayPartition	(	ctrl_t *	ctrl,
		graph_t *	graph,
		real_t *	ntpwgts,
		idx_t	niparts
	)

This function computes the initial bisection of the coarsest graph

Definition at line 19 of file initpart.c.

References ctrl_t::dbglvl, gk_errexit(), GrowBisection(), ctrl_t::InitPartTmr, ctrl_t::iptype, McGrowBisection(), McRandomBisection(), METIS_DBG_IPART, METIS_DBG_MOVEINFO, METIS_DBG_REFINE, METIS_DBG_TIME, METIS_IPTYPE_GROW, METIS_IPTYPE_RANDOM, graph_t::mincut, graph_t::ncon, graph_t::nedges, RandomBisection(), and graph_t::tvwgt.

Referenced by MultilevelBisect().

Here is the call graph for this function:

Here is the caller graph for this function:

void InitSeparator	(	ctrl_t *	ctrl,
		graph_t *	graph,
		idx_t	niparts
	)

This function computes the initial separator of the coarsest graph

Definition at line 67 of file initpart.c.

References Compute2WayPartitionParams(), ConstructSeparator(), ctrl_t::dbglvl, gk_errexit(), GrowBisection(), GrowBisectionNode(), ctrl_t::InitPartTmr, ctrl_t::iptype, METIS_DBG_IPART, METIS_DBG_MOVEINFO, METIS_DBG_REFINE, METIS_DBG_TIME, METIS_IPTYPE_EDGE, METIS_IPTYPE_NODE, graph_t::mincut, graph_t::nedges, RandomBisection(), and Setup2WayBalMultipliers().

Referenced by MlevelNodeBisectionL1().

Here is the call graph for this function:

Here is the caller graph for this function:

void RandomBisection	(	ctrl_t *	ctrl,
		graph_t *	graph,
		real_t *	ntpwgts,
		idx_t	niparts
	)

This function computes a bisection of a graph by randomly assigning the vertices followed by a bisection refinement. The resulting partition is returned in graph->where.

Definition at line 114 of file initpart.c.

References graph_t::adjncy, adjncy, graph_t::adjwgt, adjwgt, Allocate2WayPartitionMemory(), Balance2Way(), Compute2WayPartitionParams(), FM_2WayRefine(), iwspacemalloc(), graph_t::mincut, graph_t::nvtxs, perm, graph_t::tvwgt, ctrl_t::ubfactors, graph_t::vwgt, vwgt, graph_t::where, where, graph_t::xadj, and xadj.

Referenced by Init2WayPartition(), and InitSeparator().

Here is the call graph for this function:

Here is the caller graph for this function:

void GrowBisection	(	ctrl_t *	ctrl,
		graph_t *	graph,
		real_t *	ntpwgts,
		idx_t	niparts
	)

This function takes a graph and produces a bisection by using a region growing algorithm. The resulting bisection is refined using FM. The resulting partition is returned in graph->where.

Definition at line 189 of file initpart.c.

References graph_t::adjncy, adjncy, graph_t::adjwgt, adjwgt, Allocate2WayPartitionMemory(), Balance2Way(), Compute2WayPartitionParams(), FM_2WayRefine(), iwspacemalloc(), graph_t::mincut, ctrl_t::niter, graph_t::nvtxs, graph_t::tvwgt, ctrl_t::ubfactors, graph_t::vwgt, vwgt, graph_t::where, where, graph_t::xadj, and xadj.

Referenced by Init2WayPartition(), and InitSeparator().

Here is the call graph for this function:

Here is the caller graph for this function:

void McRandomBisection	(	ctrl_t *	ctrl,
		graph_t *	graph,
		real_t *	ntpwgts,
		idx_t	niparts
	)

This function takes a multi-constraint graph and computes a bisection by randomly assigning the vertices and then refining it. The resulting partition is returned in graph->where.

Definition at line 325 of file initpart.c.

References Allocate2WayPartitionMemory(), Balance2Way(), Compute2WayPartitionParams(), FM_2WayRefine(), iwspacemalloc(), graph_t::mincut, graph_t::ncon, ncon, ctrl_t::niter, graph_t::nvtxs, perm, graph_t::vwgt, vwgt, graph_t::where, and where.

Referenced by Init2WayPartition().

Here is the call graph for this function:

Here is the caller graph for this function:

void McGrowBisection	(	ctrl_t *	ctrl,
		graph_t *	graph,
		real_t *	ntpwgts,
		idx_t	niparts
	)

This function takes a multi-constraint graph and produces a bisection by using a region growing algorithm. The resulting partition is returned in graph->where.

Definition at line 385 of file initpart.c.

References Allocate2WayPartitionMemory(), Balance2Way(), Compute2WayPartitionParams(), FM_2WayRefine(), iwspacemalloc(), graph_t::mincut, ncon, ctrl_t::niter, graph_t::nvtxs, graph_t::where, and where.

Referenced by Init2WayPartition().

Here is the call graph for this function:

Here is the caller graph for this function:

void GrowBisectionNode	(	ctrl_t *	ctrl,
		graph_t *	graph,
		real_t *	ntpwgts,
		idx_t	niparts
	)

Definition at line 433 of file initpart.c.

References graph_t::adjncy, adjncy, graph_t::adjwgt, adjwgt, Balance2Way(), graph_t::bndind, graph_t::bndptr, Compute2WayNodePartitionParams(), Compute2WayPartitionParams(), graph_t::ed, FM_2WayNodeRefine1Sided(), FM_2WayNodeRefine2Sided(), FM_2WayRefine(), gk_malloc(), graph_t::id, iwspacemalloc(), graph_t::mincut, graph_t::nbnd, graph_t::nrinfo, graph_t::nvtxs, graph_t::pwgts, graph_t::tvwgt, ctrl_t::ubfactors, graph_t::vwgt, vwgt, graph_t::where, where, graph_t::xadj, and xadj.

Referenced by InitSeparator().

Here is the call graph for this function:

Here is the caller graph for this function:

void GrowBisectionNode2	(	ctrl_t *	ctrl,
		graph_t *	graph,
		real_t *	ntpwgts,
		idx_t	niparts
	)

Definition at line 570 of file initpart.c.

References graph_t::bndind, graph_t::bndptr, Compute2WayNodePartitionParams(), Compute2WayPartitionParams(), graph_t::ed, FM_2WayNodeRefine2Sided(), FM_2WayRefine(), General2WayBalance(), gk_malloc(), graph_t::id, iwspacemalloc(), graph_t::mincut, graph_t::nbnd, ctrl_t::niter, graph_t::nrinfo, graph_t::nvtxs, graph_t::pwgts, graph_t::where, where, graph_t::xadj, and xadj.

Here is the call graph for this function:

idx_t MlevelKWayPartitioning	(	ctrl_t *	ctrl,
		graph_t *	graph,
		idx_t *	part
	)

This function computes a k-way partitioning of a graph that minimizes the specified objective function.

Parameters:

	ctrl	is the control structure
	graph	is the graph to be partitioned
	part	is the vector that on return will store the partitioning

Returns:: the objective value of the partitoning. The partitioning itself is stored in the part vector.

Definition at line 103 of file kmetis.c.

References AllocateKWayPartitionMemory(), AllocateRefinementWorkSpace(), AllocateWorkSpace(), CoarsenGraph(), ComputeLoadImbalanceDiff(), ctrl_t::dbglvl, FreeGraph(), FreeRData(), FreeWorkSpace(), gk_errexit(), InitKWayPartitioning(), ctrl_t::InitPartTmr, METIS_DBG_IPART, METIS_DBG_TIME, METIS_OBJTYPE_CUT, METIS_OBJTYPE_VOL, graph_t::mincut, graph_t::minvol, ctrl_t::ncuts, graph_t::nedges, ctrl_t::nparts, graph_t::nvtxs, ctrl_t::objtype, objval, ctrl_t::pijbm, RefineKWay(), status, ctrl_t::ubfactors, and graph_t::where.

Referenced by METIS_PartGraphKway().

Here is the call graph for this function:

Here is the caller graph for this function:

void InitKWayPartitioning	(	ctrl_t *	ctrl,
		graph_t *	graph
	)

This function computes the initial k-way partitioning using PMETIS

Definition at line 172 of file kmetis.c.

References graph_t::adjncy, graph_t::adjwgt, ComputeVolume(), gk_errexit(), gk_free(), METIS_OBJTYPE_CUT, METIS_OBJTYPE_VOL, METIS_OK, METIS_OPTION_NCUTS, METIS_OPTION_NITER, METIS_OPTION_NO2HOP, METIS_OPTION_OBJTYPE, METIS_PartGraphRecursive(), METIS_SetDefaultOptions(), graph_t::ncon, ctrl_t::nIparts, ctrl_t::no2hop, ctrl_t::nparts, graph_t::nvtxs, ctrl_t::objtype, status, ctrl_t::tpwgts, ctrl_t::ubfactors, ubvec, graph_t::vsize, graph_t::vwgt, graph_t::where, and graph_t::xadj.

Referenced by MlevelKWayPartitioning().

Here is the call graph for this function:

Here is the caller graph for this function:

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.

References gk_errexit(), Greedy_KWayCutOptimize(), Greedy_KWayVolOptimize(), Greedy_McKWayCutOptimize(), Greedy_McKWayVolOptimize(), METIS_OBJTYPE_CUT, METIS_OBJTYPE_VOL, graph_t::ncon, and ctrl_t::objtype.

Referenced by RefineKWay().

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 60 of file kwayfm.c.

References ctrl_t::adids, graph_t::adjncy, adjncy, graph_t::adjwgt, adjwgt, ctrl_t::adwgts, graph_t::bndind, graph_t::bndptr, graph_t::ckrinfo, ctrl_t::cnbrpool, ComputeCut(), ComputeLoadImbalance(), ComputeSubDomainGraph(), ComputeVolume(), ctrl_t::contig, ctrl_t::dbglvl, cnbr_t::ed, ckrinfo_t::ed, ckrinfo_t::id, ckrinfo_t::inbr, IsArticulationNode(), iwspacemalloc(), PUP::l, METIS_DBG_MOVEINFO, METIS_DBG_REFINE, ctrl_t::minconn, graph_t::mincut, ctrl_t::nads, graph_t::nbnd, ckrinfo_t::nnbrs, ctrl_t::nparts, nparts, graph_t::nvtxs, perm, cnbr_t::pid, ctrl_t::pijbm, ctrl_t::pvec1, graph_t::pwgts, rpq_t, ctrl_t::tpwgts, graph_t::tvwgt, ctrl_t::ubfactors, UpdateEdgeSubDomainGraph(), graph_t::vwgt, vwgt, graph_t::where, where, graph_t::xadj, and xadj.

Referenced by Greedy_KWayOptimize().

Here is the call graph for this function:

Here is the caller graph for this function:

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.

Definition at line 370 of file kwayfm.c.

References ctrl_t::adids, graph_t::adjncy, adjncy, ctrl_t::adwgts, graph_t::bndind, graph_t::bndptr, ComputeLoadImbalance(), ComputeSubDomainGraph(), ComputeVolume(), ctrl_t::contig, ctrl_t::dbglvl, vnbr_t::gv, vkrinfo_t::gv, vkrinfo_t::inbr, IsArticulationNode(), iwspacemalloc(), KWayVolUpdate(), PUP::l, METIS_DBG_MOVEINFO, METIS_DBG_REFINE, ctrl_t::minconn, graph_t::mincut, graph_t::minvol, ctrl_t::nads, graph_t::nbnd, vnbr_t::ned, vkrinfo_t::ned, vkrinfo_t::nid, vkrinfo_t::nnbrs, ctrl_t::nparts, nparts, graph_t::nvtxs, perm, vnbr_t::pid, ctrl_t::pijbm, ctrl_t::pvec1, graph_t::pwgts, ctrl_t::tpwgts, graph_t::tvwgt, ctrl_t::ubfactors, UpdateEdgeSubDomainGraph(), graph_t::vkrinfo, ctrl_t::vnbrpool, graph_t::vsize, graph_t::vwgt, vwgt, graph_t::where, where, graph_t::xadj, and xadj.

Referenced by Greedy_KWayOptimize().

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 684 of file kwayfm.c.

References ctrl_t::adids, graph_t::adjncy, adjncy, graph_t::adjwgt, adjwgt, ctrl_t::adwgts, BetterBalanceKWay(), graph_t::bndind, graph_t::bndptr, graph_t::ckrinfo, ctrl_t::cnbrpool, ComputeCut(), ComputeLoadImbalance(), ComputeLoadImbalanceVec(), ComputeSubDomainGraph(), ComputeVolume(), ctrl_t::contig, ctrl_t::dbglvl, cnbr_t::ed, ckrinfo_t::ed, ckrinfo_t::id, ckrinfo_t::inbr, IsArticulationNode(), IsBalanced(), ivecaxpygez(), ivecaxpylez(), iwspacemalloc(), PUP::l, METIS_DBG_MOVEINFO, METIS_DBG_REFINE, ctrl_t::minconn, graph_t::mincut, ctrl_t::nads, graph_t::nbnd, graph_t::ncon, ncon, ckrinfo_t::nnbrs, ctrl_t::nparts, nparts, graph_t::nvtxs, perm, ctrl_t::pijbm, ctrl_t::pvec1, graph_t::pwgts, rpq_t, rvecmaxdiff(), rwspacemalloc(), ctrl_t::tpwgts, graph_t::tvwgt, ctrl_t::ubfactors, UpdateEdgeSubDomainGraph(), graph_t::vwgt, vwgt, graph_t::where, where, graph_t::xadj, and xadj.

Referenced by Greedy_KWayOptimize().

Here is the call graph for this function:

Here is the caller graph for this function:

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.

Definition at line 1026 of file kwayfm.c.

References ctrl_t::adids, graph_t::adjncy, adjncy, ctrl_t::adwgts, BetterBalanceKWay(), graph_t::bndind, graph_t::bndptr, ComputeLoadImbalance(), ComputeLoadImbalanceVec(), ComputeSubDomainGraph(), ComputeVolume(), ctrl_t::contig, ctrl_t::dbglvl, vnbr_t::gv, vkrinfo_t::gv, vkrinfo_t::inbr, IsArticulationNode(), IsBalanced(), ivecaxpygez(), ivecaxpylez(), iwspacemalloc(), KWayVolUpdate(), PUP::l, METIS_DBG_MOVEINFO, METIS_DBG_REFINE, ctrl_t::minconn, graph_t::mincut, graph_t::minvol, ctrl_t::nads, graph_t::nbnd, graph_t::ncon, ncon, vnbr_t::ned, vkrinfo_t::ned, vkrinfo_t::nid, vkrinfo_t::nnbrs, ctrl_t::nparts, nparts, graph_t::nvtxs, perm, ctrl_t::pijbm, ctrl_t::pvec1, graph_t::pwgts, rvecmaxdiff(), rwspacemalloc(), ctrl_t::tpwgts, graph_t::tvwgt, ctrl_t::ubfactors, UpdateEdgeSubDomainGraph(), graph_t::vkrinfo, ctrl_t::vnbrpool, graph_t::vsize, graph_t::vwgt, vwgt, graph_t::where, where, graph_t::xadj, and xadj.

Referenced by Greedy_KWayOptimize().

Here is the call graph for this function:

Here is the caller graph for this function:

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.

Referenced by Greedy_KWayCutOptimize(), Greedy_KWayVolOptimize(), Greedy_McKWayCutOptimize(), and Greedy_McKWayVolOptimize().

Here is the caller graph for this function:

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.

Definition at line 1460 of file kwayfm.c.

References graph_t::adjncy, adjncy, graph_t::bndind, graph_t::bndptr, vkrinfo_t::gv, vnbr_t::gv, vkrinfo_t::inbr, PUP::l, graph_t::nbnd, vkrinfo_t::ned, vnbr_t::ned, vkrinfo_t::nid, vkrinfo_t::nnbrs, vnbr_t::pid, PUP::u, graph_t::vkrinfo, ctrl_t::vnbrpool, vnbrpoolGetNext(), graph_t::vsize, vsize, graph_t::where, where, graph_t::xadj, and xadj.

Referenced by Greedy_KWayVolOptimize(), Greedy_McKWayVolOptimize(), MoveGroupContigForVol(), and MoveGroupMinConnForVol().

Here is the call graph for this function:

Here is the caller graph for this function:

void RefineKWay	(	ctrl_t *	ctrl,
		graph_t *	orggraph,
		graph_t *	graph
	)

This function is the entry point of cut-based refinement

Definition at line 17 of file kwayrefine.c.

References ComputeKWayBoundary(), ComputeKWayPartitionParams(), ctrl_t::contig, ctrl_t::dbglvl, EliminateComponents(), EliminateSubDomainEdges(), FindPartitionInducedComponents(), graph_t::finer, Greedy_KWayOptimize(), IsBalanced(), METIS_DBG_TIME, ctrl_t::minconn, ctrl_t::niter, ctrl_t::nparts, ProjectKWayPartition(), ctrl_t::ProjectTmr, ctrl_t::RefTmr, ctrl_t::UncoarsenTmr, graph_t::vwgt, and graph_t::where.

Referenced by MlevelKWayPartitioning().

Here is the call graph for this function:

Here is the caller graph for this function:

void AllocateKWayPartitionMemory	(	ctrl_t *	ctrl,
		graph_t *	graph
	)

This function allocates memory for the k-way cut-based refinement

Definition at line 116 of file kwayrefine.c.

References graph_t::bndind, graph_t::bndptr, graph_t::ckrinfo, gk_errexit(), gk_malloc(), METIS_OBJTYPE_CUT, METIS_OBJTYPE_VOL, graph_t::ncon, ctrl_t::nparts, graph_t::nvtxs, ctrl_t::objtype, graph_t::pwgts, graph_t::vkrinfo, and graph_t::where.

Referenced by MlevelKWayPartitioning(), and ProjectKWayPartition().

Here is the call graph for this function:

Here is the caller graph for this function:

void ComputeKWayPartitionParams	(	ctrl_t *	ctrl,
		graph_t *	graph
	)

This function computes the initial id/ed for cut-based partitioning

Definition at line 149 of file kwayrefine.c.

References graph_t::adjncy, adjncy, graph_t::adjwgt, adjwgt, graph_t::bndind, graph_t::bndptr, CheckBnd2(), graph_t::ckrinfo, ctrl_t::cnbrpool, cnbrpoolGetNext(), cnbrpoolReset(), ComputeKWayVolGains(), ComputeVolume(), cnbr_t::ed, ckrinfo_t::ed, gk_errexit(), vnbr_t::gv, ckrinfo_t::id, vkrinfo_t::inbr, ckrinfo_t::inbr, PUP::l, METIS_OBJTYPE_CUT, METIS_OBJTYPE_VOL, graph_t::mincut, graph_t::minvol, graph_t::nbnd, graph_t::ncon, ncon, vnbr_t::ned, vkrinfo_t::ned, vkrinfo_t::nid, vkrinfo_t::nnbrs, ckrinfo_t::nnbrs, ctrl_t::nparts, nparts, graph_t::nvtxs, ctrl_t::objtype, vnbr_t::pid, cnbr_t::pid, graph_t::pwgts, graph_t::vkrinfo, ctrl_t::vnbrpool, vnbrpoolGetNext(), vnbrpoolReset(), graph_t::vwgt, vwgt, graph_t::where, where, graph_t::xadj, and xadj.

Referenced by RefineKWay().

Here is the call graph for this function:

Here is the caller graph for this function:

void ProjectKWayPartition	(	ctrl_t *	ctrl,
		graph_t *	graph
	)

This function projects a partition, and at the same time computes the parameters for refinement.

Definition at line 315 of file kwayrefine.c.

References graph_t::adjncy, adjncy, graph_t::adjwgt, adjwgt, AllocateKWayPartitionMemory(), graph_t::bndind, graph_t::bndptr, CheckBnd2(), graph_t::ckrinfo, graph_t::cmap, ctrl_t::cnbrpool, cnbrpoolGetNext(), cnbrpoolReset(), graph_t::coarser, ComputeKWayVolGains(), ComputeVolume(), cnbr_t::ed, ckrinfo_t::ed, FreeGraph(), gk_errexit(), vnbr_t::gv, ckrinfo_t::id, vkrinfo_t::inbr, ckrinfo_t::inbr, iwspacemalloc(), METIS_OBJTYPE_CUT, METIS_OBJTYPE_VOL, graph_t::mincut, graph_t::minvol, graph_t::nbnd, ctrl_t::nbrpoolcpos, graph_t::ncon, vnbr_t::ned, vkrinfo_t::ned, vkrinfo_t::nid, vkrinfo_t::nnbrs, ckrinfo_t::nnbrs, ctrl_t::nparts, nparts, graph_t::nvtxs, ctrl_t::objtype, vnbr_t::pid, cnbr_t::pid, graph_t::pwgts, graph_t::vkrinfo, ctrl_t::vnbrpool, vnbrpoolGetNext(), vnbrpoolReset(), graph_t::where, where, graph_t::xadj, and xadj.

Referenced by RefineKWay().

Here is the call graph for this function:

Here is the caller graph for this function:

void ComputeKWayBoundary	(	ctrl_t *	ctrl,
		graph_t *	graph,
		idx_t	bndtype
	)

This function computes the boundary definition for balancing.

Definition at line 507 of file kwayrefine.c.

References graph_t::bndind, graph_t::bndptr, graph_t::ckrinfo, ckrinfo_t::ed, gk_errexit(), vkrinfo_t::gv, ckrinfo_t::id, METIS_OBJTYPE_CUT, METIS_OBJTYPE_VOL, graph_t::nbnd, vkrinfo_t::ned, graph_t::nvtxs, ctrl_t::objtype, and graph_t::vkrinfo.

Referenced by RefineKWay().

Here is the call graph for this function:

Here is the caller graph for this function:

void ComputeKWayVolGains	(	ctrl_t *	ctrl,
		graph_t *	graph
	)

This function computes the initial gains in the communication volume

Definition at line 562 of file kwayrefine.c.

References graph_t::adjncy, adjncy, graph_t::adjwgt, adjwgt, graph_t::bndind, graph_t::bndptr, vnbr_t::gv, vkrinfo_t::gv, vkrinfo_t::inbr, iwspacemalloc(), PUP::l, graph_t::minvol, graph_t::nbnd, vkrinfo_t::ned, vkrinfo_t::nid, vkrinfo_t::nnbrs, ctrl_t::nparts, nparts, graph_t::nvtxs, graph_t::vkrinfo, ctrl_t::vnbrpool, graph_t::vsize, vsize, graph_t::where, where, graph_t::xadj, and xadj.

Referenced by ComputeKWayPartitionParams(), and ProjectKWayPartition().

Here is the call graph for this function:

Here is the caller graph for this function:

int IsBalanced	(	ctrl_t *	ctrl,
		graph_t *	graph,
		real_t	ffactor
	)

This function checks if the partition weights are within the balance contraints

Definition at line 666 of file kwayrefine.c.

References ComputeLoadImbalanceDiff(), ctrl_t::nparts, ctrl_t::pijbm, and ctrl_t::ubfactors.

Referenced by Greedy_McKWayCutOptimize(), Greedy_McKWayVolOptimize(), and RefineKWay().

Here is the call graph for this function:

Here is the caller graph for this function:

int rvecle	(	idx_t	n,
		real_t *	x,
		real_t *	y
	)

This function compares two vectors x & y and returns true if i, x[i] <= y[i].

Definition at line 22 of file mcutil.c.

int rvecge	(	idx_t	n,
		real_t *	x,
		real_t *	y
	)

This function compares two vectors x & y and returns true if i, x[i] >= y[i].

Definition at line 38 of file mcutil.c.

int rvecsumle	(	idx_t	n,
		real_t *	x1,
		real_t *	x2,
		real_t *	y
	)

This function compares vectors x1+x2 against y and returns true if i, x1[i]+x2[i] <= y[i].

Definition at line 54 of file mcutil.c.

real_t rvecmaxdiff	(	idx_t	n,
		real_t *	x,
		real_t *	y
	)

This function returns max_i(x[i]-y[i])

Definition at line 68 of file mcutil.c.

References max().

Referenced by Greedy_McKWayCutOptimize(), and Greedy_McKWayVolOptimize().

Here is the call graph for this function:

Here is the caller graph for this function:

int ivecle	(	idx_t	n,
		idx_t *	x,
		idx_t *	z
	)

This function returns true if i, x[i] <= z[i].

Definition at line 86 of file mcutil.c.

Referenced by Match_RM(), and Match_SHEM().

Here is the caller graph for this function:

int ivecge	(	idx_t	n,
		idx_t *	x,
		idx_t *	z
	)

This function returns true if i, x[i] >= z[i].

Definition at line 100 of file mcutil.c.

int ivecaxpylez	(	idx_t	n,
		idx_t	a,
		idx_t *	x,
		idx_t *	y,
		idx_t *	z
	)

This function returns true if i, a*x[i]+y[i] <= z[i].

Definition at line 114 of file mcutil.c.

Referenced by EliminateSubDomainEdges(), Greedy_McKWayCutOptimize(), Greedy_McKWayVolOptimize(), Match_RM(), and Match_SHEM().

Here is the caller graph for this function:

int ivecaxpygez	(	idx_t	n,
		idx_t	a,
		idx_t *	x,
		idx_t *	y,
		idx_t *	z
	)

This function returns true if i, a*x[i]+y[i] >= z[i].

Definition at line 128 of file mcutil.c.

Referenced by Greedy_McKWayCutOptimize(), and Greedy_McKWayVolOptimize().

Here is the caller graph for this function:

int BetterVBalance	(	idx_t	ncon,
		real_t *	invtvwgt,
		idx_t *	v_vwgt,
		idx_t *	u1_vwgt,
		idx_t *	u2_vwgt
	)

This function checks if v+u2 provides a better balance in the weight vector that v+u1

Definition at line 143 of file mcutil.c.

Referenced by Match_SHEM().

Here is the caller graph for this function:

int BetterBalance2Way	(	idx_t	n,
		real_t *	x,
		real_t *	y
	)

This function takes two ubfactor-centered load imbalance vectors x & y, and returns true if y is better balanced than x.

Definition at line 169 of file mcutil.c.

Referenced by FM_Mc2WayCutRefine(), and McGeneral2WayBalance().

Here is the caller graph for this function:

int BetterBalanceKWay	(	idx_t	ncon,
		idx_t *	vwgt,
		real_t *	ubvec,
		idx_t	a1,
		idx_t *	pt1,
		real_t *	bm1,
		idx_t	a2,
		idx_t *	pt2,
		real_t *	bm2
	)

Given a vertex and two weights, this function returns 1, if the second partition will be more balanced than the first after the weighted additional of that vertex. The balance determination takes into account the ideal target weights of the two partitions.

Definition at line 189 of file mcutil.c.

Referenced by EliminateComponents(), Greedy_McKWayCutOptimize(), and Greedy_McKWayVolOptimize().

Here is the caller graph for this function:

real_t ComputeLoadImbalance	(	graph_t *	graph,
		idx_t	nparts,
		real_t *	pijbm
	)

Computes the maximum load imbalance of a partitioning solution over all the constraints.

Definition at line 228 of file mcutil.c.

References max(), graph_t::ncon, ncon, and graph_t::pwgts.

Referenced by FM_Mc2WayCutRefine(), Greedy_KWayCutOptimize(), Greedy_KWayVolOptimize(), Greedy_McKWayCutOptimize(), Greedy_McKWayVolOptimize(), McGeneral2WayBalance(), and Print2WayRefineStats().

Here is the call graph for this function:

Here is the caller graph for this function:

real_t ComputeLoadImbalanceDiff	(	graph_t *	graph,
		idx_t	nparts,
		real_t *	pijbm,
		real_t *	ubvec
	)

Computes the maximum load imbalance difference of a partitioning solution over all the constraints. The difference is defined with respect to the allowed maximum unbalance for the respective constraint.

Definition at line 256 of file mcutil.c.

References max(), graph_t::ncon, ncon, and graph_t::pwgts.

Referenced by Balance2Way(), IsBalanced(), MlevelKWayPartitioning(), and MultilevelBisect().

Here is the call graph for this function:

Here is the caller graph for this function:

real_t ComputeLoadImbalanceDiffVec	(	graph_t *	graph,
		idx_t	nparts,
		real_t *	pijbm,
		real_t *	ubfactors,
		real_t *	diffvec
	)

Computes the difference between load imbalance of each constraint across the partitions minus the desired upper bound on the load imabalnce. It also returns the maximum load imbalance across the partitions & constraints.

Definition at line 284 of file mcutil.c.

References max(), graph_t::ncon, ncon, and graph_t::pwgts.

Referenced by FM_Mc2WayCutRefine(), and McGeneral2WayBalance().

Here is the call graph for this function:

Here is the caller graph for this function:

void ComputeLoadImbalanceVec	(	graph_t *	graph,
		idx_t	nparts,
		real_t *	pijbm,
		real_t *	lbvec
	)

Computes the load imbalance of each constraint across the partitions.

Definition at line 311 of file mcutil.c.

References graph_t::ncon, ncon, and graph_t::pwgts.

Referenced by Greedy_McKWayCutOptimize(), and Greedy_McKWayVolOptimize().

Here is the caller graph for this function:

void CreateGraphDual	(	idx_t	ne,
		idx_t	nn,
		idx_t *	eptr,
		idx_t *	eind,
		idx_t	ncommon,
		idx_t **	r_xadj,
		idx_t **	r_adjncy
	)

This function creates the dual of a finite element mesh

Definition at line 162 of file mesh.c.

References adjncy, FindCommonElements(), free(), gk_errexit(), gk_free(), malloc(), and xadj.

Referenced by METIS_MeshToDual().

Here is the call graph for this function:

Here is the caller graph for this function:

idx_t FindCommonElements	(	idx_t	qid,
		idx_t	elen,
		idx_t *	eind,
		idx_t *	nptr,
		idx_t *	nind,
		idx_t *	eptr,
		idx_t	ncommon,
		idx_t *	marker,
		idx_t *	nbrs
	)

This function finds all elements that share at least ncommon nodes with the ``query'' element.

Definition at line 237 of file mesh.c.

References PUP::l.

Referenced by CreateGraphDual().

Here is the caller graph for this function:

void CreateGraphNodal	(	idx_t	ne,
		idx_t	nn,
		idx_t *	eptr,
		idx_t *	eind,
		idx_t **	r_xadj,
		idx_t **	r_adjncy
	)

This function creates the (almost) nodal of a finite element mesh

Definition at line 277 of file mesh.c.

References adjncy, FindCommonNodes(), free(), gk_errexit(), gk_free(), malloc(), and xadj.

Referenced by METIS_MeshToNodal().

Here is the call graph for this function:

Here is the caller graph for this function:

idx_t FindCommonNodes	(	idx_t	qid,
		idx_t	nelmnts,
		idx_t *	elmntids,
		idx_t *	eptr,
		idx_t *	eind,
		idx_t *	marker,
		idx_t *	nbrs
	)

This function finds the union of nodes that are in the same elements with the ``query'' node.

Definition at line 348 of file mesh.c.

Referenced by CreateGraphNodal().

Here is the caller graph for this function:

mesh_t* CreateMesh ( void )

This function creates and initializes a mesh_t structure

Definition at line 380 of file mesh.c.

References gk_malloc(), InitMesh(), and mesh.

Referenced by ReadMesh().

Here is the call graph for this function:

Here is the caller graph for this function:

void InitMesh ( mesh_t * mesh )

This function initializes a mesh_t data structure

Definition at line 395 of file mesh.c.

Referenced by CreateMesh().

Here is the caller graph for this function:

void FreeMesh ( mesh_t ** r_mesh )

This function deallocates any memory stored in a mesh

Definition at line 404 of file mesh.c.

References mesh_t::eind, mesh_t::eptr, mesh_t::ewgt, gk_free(), and mesh.

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

void InduceRowPartFromColumnPart	(	idx_t	nrows,
		idx_t *	rowptr,
		idx_t *	rowind,
		idx_t *	rpart,
		idx_t *	cpart,
		idx_t	nparts,
		real_t *	tpwgts
	)

Induces a partitioning of the rows based on a a partitioning of the columns. It is used by both the Nodal and Dual routines.

Definition at line 179 of file meshpart.c.

References gk_free().

Referenced by METIS_PartMeshDual(), and METIS_PartMeshNodal().

Here is the call graph for this function:

Here is the caller graph for this function:

void ComputeSubDomainGraph	(	ctrl_t *	ctrl,
		graph_t *	graph
	)

This function computes the subdomain graph storing the result in the pre-allocated worspace arrays

Definition at line 18 of file minconn.c.

References ctrl_t::adids, graph_t::adjncy, adjncy, graph_t::adjwgt, adjwgt, ctrl_t::adwgts, graph_t::ckrinfo, ctrl_t::cnbrpool, cnbr_t::ed, gk_errexit(), vkrinfo_t::inbr, ckrinfo_t::inbr, iwspacemalloc(), ctrl_t::maxnads, METIS_OBJTYPE_CUT, METIS_OBJTYPE_VOL, ctrl_t::nads, vnbr_t::ned, vkrinfo_t::nnbrs, ckrinfo_t::nnbrs, ctrl_t::nparts, nparts, graph_t::nvtxs, ctrl_t::objtype, vnbr_t::pid, cnbr_t::pid, ctrl_t::pvec1, ctrl_t::pvec2, graph_t::vkrinfo, ctrl_t::vnbrpool, graph_t::where, where, graph_t::xadj, and xadj.

Referenced by EliminateSubDomainEdges(), Greedy_KWayCutOptimize(), Greedy_KWayVolOptimize(), Greedy_McKWayCutOptimize(), and Greedy_McKWayVolOptimize().

Here is the call graph for this function:

Here is the caller graph for this function:

void UpdateEdgeSubDomainGraph	(	ctrl_t *	ctrl,
		idx_t	u,
		idx_t	v,
		idx_t	ewgt,
		idx_t *	r_maxndoms
	)

This function updates the weight of an edge in the subdomain graph by adding to it the value of ewgt. The update can either increase or decrease the weight of the subdomain edge based on the value of ewgt.

Parameters:

	u	is the ID of one of the incident subdomains to the edge
	v	is the ID of the other incident subdomains to the edge
	ewgt	is the weight to be added to the subdomain edge
	nparts	is the number of subdomains
	r_maxndoms	is the maximum number of adjacent subdomains and is updated as necessary. The update is skipped if a NULL value is supplied.

Definition at line 134 of file minconn.c.

References ctrl_t::adids, ctrl_t::adwgts, ctrl_t::maxnads, ctrl_t::nads, and ctrl_t::nparts.

Referenced by Greedy_KWayCutOptimize(), Greedy_KWayVolOptimize(), Greedy_McKWayCutOptimize(), Greedy_McKWayVolOptimize(), MoveGroupMinConnForCut(), and MoveGroupMinConnForVol().

Here is the caller graph for this function:

void PrintSubDomainGraph	(	graph_t *	graph,
		idx_t	nparts,
		idx_t *	where
	)

This function computes the subdomain graph. For deubuging purposes.

Definition at line 683 of file minconn.c.

References graph_t::adjncy, adjncy, graph_t::adjwgt, adjwgt, gk_free(), max(), graph_t::nvtxs, graph_t::xadj, and xadj.

Here is the call graph for this function:

void EliminateSubDomainEdges	(	ctrl_t *	ctrl,
		graph_t *	graph
	)

This function computes the subdomain graph

Definition at line 192 of file minconn.c.

References ctrl_t::adids, graph_t::adjncy, adjncy, graph_t::adjwgt, adjwgt, ctrl_t::adwgts, ComputeSubDomainGraph(), ctrl_t::dbglvl, gk_errexit(), ikvsortd(), ikvsorti(), ikvwspacemalloc(), ivecaxpylez(), iwspacemalloc(), key, max(), METIS_DBG_CONNINFO, METIS_OBJTYPE_CUT, METIS_OBJTYPE_VOL, min(), MoveGroupMinConnForCut(), MoveGroupMinConnForVol(), ctrl_t::nads, graph_t::ncon, ncon, ctrl_t::nparts, nparts, graph_t::nvtxs, ctrl_t::objtype, ctrl_t::pvec1, ctrl_t::pvec2, graph_t::pwgts, ctrl_t::tpwgts, tpwgts, graph_t::tvwgt, ctrl_t::ubfactors, graph_t::vwgt, vwgt, graph_t::where, where, graph_t::xadj, and xadj.

Referenced by RefineKWay().

Here is the call graph for this function:

Here is the caller graph for this function:

void MoveGroupMinConnForCut	(	ctrl_t *	ctrl,
		graph_t *	graph,
		idx_t	to,
		idx_t	nind,
		idx_t *	ind
	)

This function moves a collection of vertices and updates their rinfo

Definition at line 477 of file minconn.c.

References graph_t::adjncy, adjncy, graph_t::adjwgt, adjwgt, graph_t::bndind, graph_t::bndptr, graph_t::ckrinfo, ctrl_t::cnbrpool, cnbrpoolGetNext(), ComputeCut(), cnbr_t::ed, ckrinfo_t::id, ckrinfo_t::inbr, PUP::l, graph_t::mincut, graph_t::nbnd, graph_t::ncon, ckrinfo_t::nnbrs, graph_t::nvtxs, cnbr_t::pid, graph_t::pwgts, UpdateEdgeSubDomainGraph(), graph_t::vwgt, graph_t::where, where, graph_t::xadj, and xadj.

Referenced by EliminateSubDomainEdges().

Here is the call graph for this function:

Here is the caller graph for this function:

void MoveGroupMinConnForVol	(	ctrl_t *	ctrl,
		graph_t *	graph,
		idx_t	to,
		idx_t	nind,
		idx_t *	ind,
		idx_t *	vmarker,
		idx_t *	pmarker,
		idx_t *	modind
	)

This function moves a collection of vertices and updates their rinfo

Definition at line 561 of file minconn.c.

References graph_t::adjncy, adjncy, ComputeCut(), ComputeVolume(), vnbr_t::gv, vkrinfo_t::inbr, KWayVolUpdate(), PUP::l, graph_t::mincut, graph_t::minvol, graph_t::ncon, vnbr_t::ned, vkrinfo_t::ned, vkrinfo_t::nid, vkrinfo_t::nnbrs, graph_t::nvtxs, graph_t::pwgts, UpdateEdgeSubDomainGraph(), graph_t::vkrinfo, ctrl_t::vnbrpool, vnbrpoolGetNext(), graph_t::vsize, vsize, graph_t::vwgt, graph_t::where, where, graph_t::xadj, and xadj.

Referenced by EliminateSubDomainEdges().

Here is the call graph for this function:

Here is the caller graph for this function:

void MinCover	(	idx_t *	,
		idx_t *	,
		idx_t	,
		idx_t	,
		idx_t *	,
		idx_t *
	)

Definition at line 42 of file mincover.c.

References flag, gk_free(), level, MinCover_Augment(), and MinCover_Decompose().

Referenced by ConstructMinCoverSeparator().

Here is the call graph for this function:

Here is the caller graph for this function:

idx_t MinCover_Augment	(	idx_t *	,
		idx_t *	,
		idx_t	,
		idx_t *	,
		idx_t *	,
		idx_t *	,
		idx_t
	)

Definition at line 126 of file mincover.c.

References MinCover_Augment(), and status.

Referenced by MinCover(), and MinCover_Augment().

Here is the call graph for this function:

Here is the caller graph for this function:

void MinCover_Decompose	(	idx_t *	,
		idx_t *	,
		idx_t	,
		idx_t	,
		idx_t *	,
		idx_t *	,
		idx_t *
	)

Definition at line 163 of file mincover.c.

References gk_free(), MinCover_ColDFS(), MinCover_RowDFS(), and where.

Referenced by MinCover().

Here is the call graph for this function:

Here is the caller graph for this function:

void MinCover_ColDFS	(	idx_t *	,
		idx_t *	,
		idx_t	,
		idx_t *	,
		idx_t *	,
		idx_t
	)

Definition at line 212 of file mincover.c.

References MinCover_ColDFS().

Referenced by MinCover_ColDFS(), and MinCover_Decompose().

Here is the call graph for this function:

Here is the caller graph for this function:

void MinCover_RowDFS	(	idx_t *	,
		idx_t *	,
		idx_t	,
		idx_t *	,
		idx_t *	,
		idx_t
	)

Definition at line 237 of file mincover.c.

References MinCover_RowDFS().

Referenced by MinCover_Decompose(), and MinCover_RowDFS().

Here is the call graph for this function:

Here is the caller graph for this function:

void genmmd	(	idx_t	,
		idx_t *	,
		idx_t *	,
		idx_t *	,
		idx_t *	,
		idx_t	,
		idx_t *	,
		idx_t *	,
		idx_t *	,
		idx_t *	,
		idx_t	,
		idx_t *
	)

Definition at line 53 of file mmd.c.

References mmdelm(), mmdint(), mmdnum(), mmdupd(), and tag.

Referenced by MMDOrder().

Here is the call graph for this function:

Here is the caller graph for this function:

void mmdelm	(	idx_t	,
		idx_t *	xadj,
		idx_t *	,
		idx_t *	,
		idx_t *	,
		idx_t *	,
		idx_t *	,
		idx_t *	,
		idx_t *	,
		idx_t	,
		idx_t
	)

Definition at line 171 of file mmd.c.

Referenced by genmmd().

Here is the caller graph for this function:

idx_t mmdint	(	idx_t	,
		idx_t *	xadj,
		idx_t *	,
		idx_t *	,
		idx_t *	,
		idx_t *	,
		idx_t *	,
		idx_t *	,
		idx_t *
	)

Definition at line 305 of file mmd.c.

Referenced by genmmd().

Here is the caller graph for this function:

void mmdnum	(	idx_t	,
		idx_t *	,
		idx_t *	,
		idx_t *
	)

Definition at line 348 of file mmd.c.

References root.

Referenced by genmmd().

Here is the caller graph for this function:

void mmdupd	(	idx_t	,
		idx_t	,
		idx_t *	,
		idx_t *	,
		idx_t	,
		idx_t *	,
		idx_t *	,
		idx_t *	,
		idx_t *	,
		idx_t *	,
		idx_t *	,
		idx_t *	,
		idx_t	,
		idx_t *	tag
	)

Definition at line 412 of file mmd.c.

Referenced by genmmd().

Here is the caller graph for this function:

void MlevelNestedDissection	(	ctrl_t *	ctrl,
		graph_t *	graph,
		idx_t *	order,
		idx_t	lastvtx
	)

This is the driver for the recursive tri-section of a graph into the left, separator, and right partitions. The graphs correspond to the left and right parts are further tri-sected in a recursive fashion. The nodes in the separator are ordered at the end of the left & right nodes.

Definition at line 183 of file ometis.c.

References graph_t::bndind, ctrl_t::dbglvl, FreeGraph(), graph_t::label, METIS_DBG_SEPINFO, MlevelNestedDissection(), MlevelNodeBisectionMultiple(), MMDOrder(), graph_t::nbnd, graph_t::nedges, graph_t::nvtxs, graph_t::pwgts, and SplitGraphOrder().

Referenced by METIS_NodeND(), and MlevelNestedDissection().

Here is the call graph for this function:

Here is the caller graph for this function:

void MlevelNestedDissectionCC	(	ctrl_t *	ctrl,
		graph_t *	graph,
		idx_t *	order,
		idx_t	lastvtx
	)

This routine is similar to its non 'CC' counterpart. The difference is that after each tri-section, the connected components of the original graph that result after removing the separator vertises are ordered independently (i.e., this may lead to more than just the left and the right subgraphs).

Definition at line 236 of file ometis.c.

References graph_t::bndind, ctrl_t::dbglvl, FindSepInducedComponents(), FreeGraph(), gk_free(), iwspacemalloc(), graph_t::label, METIS_DBG_INFO, METIS_DBG_SEPINFO, MlevelNestedDissectionCC(), MlevelNodeBisectionMultiple(), MMDOrder(), graph_t::nbnd, graph_t::nvtxs, graph_t::pwgts, and SplitGraphOrderCC().

Referenced by METIS_NodeND(), and MlevelNestedDissectionCC().

Here is the call graph for this function:

Here is the caller graph for this function:

void MlevelNodeBisectionMultiple	(	ctrl_t *	ctrl,
		graph_t *	graph
	)

This function performs multilevel node bisection (i.e., tri-section). It performs multiple bisections and selects the best.

Definition at line 300 of file ometis.c.

References ctrl_t::compress, Compute2WayNodePartitionParams(), FreeRData(), iwspacemalloc(), graph_t::mincut, MlevelNodeBisectionL2(), ctrl_t::nseps, graph_t::nvtxs, graph_t::tvwgt, and graph_t::where.

Referenced by METIS_ComputeVertexSeparator(), MlevelNestedDissection(), MlevelNestedDissectionCC(), and MlevelNestedDissectionP().

Here is the call graph for this function:

Here is the caller graph for this function:

void MlevelNodeBisectionL2	(	ctrl_t *	ctrl,
		graph_t *	graph,
		idx_t	niparts
	)

This function performs multilevel node bisection (i.e., tri-section). It performs multiple bisections and selects the best.

Definition at line 345 of file ometis.c.

References CoarsenGraphNlevels(), ctrl_t::CoarsenTo, FreeRData(), iwspacemalloc(), graph_t::mincut, MlevelNodeBisectionL1(), graph_t::nvtxs, Refine2WayNode(), graph_t::tvwgt, and graph_t::where.

Referenced by MlevelNodeBisectionMultiple().

Here is the call graph for this function:

Here is the caller graph for this function:

void MlevelNodeBisectionL1	(	ctrl_t *	ctrl,
		graph_t *	graph,
		idx_t	niparts
	)

The top-level routine of the actual multilevel node bisection

Definition at line 395 of file ometis.c.

References CoarsenGraph(), ctrl_t::CoarsenTo, InitSeparator(), graph_t::nvtxs, and Refine2WayNode().

Referenced by MlevelNodeBisectionL2().

Here is the call graph for this function:

Here is the caller graph for this function:

void SplitGraphOrder	(	ctrl_t *	ctrl,
		graph_t *	graph,
		graph_t **	r_lgraph,
		graph_t **	r_rgraph
	)

This function takes a graph and a tri-section (left, right, separator) and splits it into two graphs.

This function relies on the fact that adjwgt is all equal to 1.

Definition at line 422 of file ometis.c.

References graph_t::adjncy, adjncy, graph_t::adjwgt, adjwgt, graph_t::bndind, graph_t::bndptr, ctrl_t::dbglvl, iwspacemalloc(), PUP::l, graph_t::label, METIS_DBG_TIME, graph_t::nbnd, graph_t::nedges, graph_t::nvtxs, SetupGraph_tvwgt(), SetupSplitGraph(), ctrl_t::SplitTmr, graph_t::vwgt, vwgt, graph_t::where, where, graph_t::xadj, and xadj.

Referenced by MlevelNestedDissection(), and MlevelNestedDissectionP().

Here is the call graph for this function:

Here is the caller graph for this function:

graph_t** SplitGraphOrderCC	(	ctrl_t *	ctrl,
		graph_t *	graph,
		idx_t	ncmps,
		idx_t *	cptr,
		idx_t *	cind
	)

This function takes a graph and generates a set of graphs, each of which is a connected component in the original graph.

This function relies on the fact that adjwgt is all equal to 1.

Parameters:

	ctrl	stores run state info.
	graph	is the graph to be split.
	ncmps	is the number of connected components.
	cptr	is an array of size ncmps+1 that marks the start and end locations of the vertices in cind that make up the respective components (i.e., cptr, cind is in CSR format).
	cind	is an array of size equal to the number of vertices in the original graph and stores the vertices that belong to each connected component.

Returns:: an array of subgraphs corresponding to the extracted subgraphs.

Definition at line 552 of file ometis.c.

References graph_t::adjncy, adjncy, graph_t::adjwgt, adjwgt, graph_t::bndind, graph_t::bndptr, ctrl_t::dbglvl, gk_malloc(), iwspacemalloc(), PUP::l, graph_t::label, METIS_DBG_TIME, graph_t::nbnd, graph_t::nedges, graph_t::nvtxs, SetupGraph_tvwgt(), SetupSplitGraph(), ctrl_t::SplitTmr, graph_t::vwgt, vwgt, graph_t::where, where, graph_t::xadj, and xadj.

Referenced by MlevelNestedDissectionCC().

Here is the call graph for this function:

Here is the caller graph for this function:

void MMDOrder	(	ctrl_t *	ctrl,
		graph_t *	graph,
		idx_t *	order,
		idx_t	lastvtx
	)

This function uses MMD to order the graph. The vertices are numbered from lastvtx downwards.

Definition at line 655 of file ometis.c.

References graph_t::adjncy, adjncy, genmmd(), iperm, iwspacemalloc(), graph_t::label, list, graph_t::nvtxs, perm, graph_t::xadj, and xadj.

Referenced by MlevelNestedDissection(), MlevelNestedDissectionCC(), and MlevelNestedDissectionP().

Here is the call graph for this function:

Here is the caller graph for this function:

ctrl_t* SetupCtrl	(	moptype_et	optype,
		idx_t *	options,
		idx_t	ncon,
		idx_t	nparts,
		real_t *	tpwgts,
		real_t *	ubvec
	)

This function creates and sets the run parameters (ctrl_t)

Definition at line 17 of file options.c.

References CheckParams(), FreeCtrl(), gk_errexit(), gk_malloc(), InitRandom(), METIS_CTYPE_SHEM, METIS_DBG_INFO, METIS_IPTYPE_EDGE, METIS_IPTYPE_GROW, METIS_IPTYPE_METISRB, METIS_IPTYPE_RANDOM, METIS_OBJTYPE_CUT, METIS_OBJTYPE_NODE, METIS_OP_KMETIS, METIS_OP_OMETIS, METIS_OP_PMETIS, METIS_OPTION_CCORDER, METIS_OPTION_COMPRESS, METIS_OPTION_CONTIG, METIS_OPTION_CTYPE, METIS_OPTION_DBGLVL, METIS_OPTION_IPTYPE, METIS_OPTION_MINCONN, METIS_OPTION_NCUTS, METIS_OPTION_NITER, METIS_OPTION_NO2HOP, METIS_OPTION_NSEPS, METIS_OPTION_NUMBERING, METIS_OPTION_OBJTYPE, METIS_OPTION_PFACTOR, METIS_OPTION_RTYPE, METIS_OPTION_SEED, METIS_OPTION_UFACTOR, METIS_RTYPE_FM, METIS_RTYPE_GREEDY, METIS_RTYPE_SEP1SIDED, and PrintCtrl().

Referenced by METIS_ComputeVertexSeparator(), METIS_NodeND(), METIS_NodeNDP(), METIS_NodeRefine(), METIS_PartGraphKway(), and METIS_PartGraphRecursive().

Here is the call graph for this function:

Here is the caller graph for this function:

void SetupKWayBalMultipliers	(	ctrl_t *	ctrl,
		graph_t *	graph
	)

Computes the per-partition/constraint balance multipliers

Definition at line 140 of file options.c.

References graph_t::invtvwgt, graph_t::ncon, ctrl_t::nparts, ctrl_t::pijbm, and ctrl_t::tpwgts.

Referenced by METIS_PartGraphKway().

Here is the caller graph for this function:

void Setup2WayBalMultipliers	(	ctrl_t *	ctrl,
		graph_t *	graph,
		real_t *	tpwgts
	)

Computes the per-partition/constraint balance multipliers

Definition at line 154 of file options.c.

References graph_t::invtvwgt, graph_t::ncon, and ctrl_t::pijbm.

Referenced by InitSeparator(), and MultilevelBisect().

Here is the caller graph for this function:

void PrintCtrl ( ctrl_t * ctrl )

This function prints the various control fields

Definition at line 168 of file options.c.

References ctrl_t::ccorder, ctrl_t::compress, ctrl_t::contig, ctrl_t::ctype, ctrl_t::iptype, METIS_CTYPE_RM, METIS_CTYPE_SHEM, METIS_IPTYPE_EDGE, METIS_IPTYPE_GROW, METIS_IPTYPE_METISRB, METIS_IPTYPE_NODE, METIS_IPTYPE_RANDOM, METIS_OBJTYPE_CUT, METIS_OBJTYPE_NODE, METIS_OBJTYPE_VOL, METIS_OP_KMETIS, METIS_OP_OMETIS, METIS_RTYPE_FM, METIS_RTYPE_GREEDY, METIS_RTYPE_SEP1SIDED, METIS_RTYPE_SEP2SIDED, ctrl_t::minconn, ctrl_t::ncon, ctrl_t::ncuts, ctrl_t::niter, ctrl_t::no2hop, ctrl_t::nparts, ctrl_t::nseps, ctrl_t::objtype, ctrl_t::optype, ctrl_t::pfactor, ctrl_t::rtype, ctrl_t::seed, ctrl_t::tpwgts, ctrl_t::ubfactors, and ctrl_t::ufactor.

Referenced by SetupCtrl().

Here is the caller graph for this function:

int CheckParams ( ctrl_t * ctrl )

This function checks the validity of user-supplied parameters

Definition at line 287 of file options.c.

References ctrl_t::ccorder, ctrl_t::compress, ctrl_t::contig, ctrl_t::ctype, ctrl_t::iptype, METIS_CTYPE_RM, METIS_CTYPE_SHEM, METIS_DBG_INFO, METIS_IPTYPE_EDGE, METIS_IPTYPE_GROW, METIS_IPTYPE_METISRB, METIS_IPTYPE_NODE, METIS_IPTYPE_RANDOM, METIS_OBJTYPE_CUT, METIS_OBJTYPE_NODE, METIS_OBJTYPE_VOL, METIS_OP_KMETIS, METIS_OP_OMETIS, METIS_OP_PMETIS, METIS_RTYPE_FM, METIS_RTYPE_GREEDY, METIS_RTYPE_SEP1SIDED, METIS_RTYPE_SEP2SIDED, ctrl_t::minconn, ctrl_t::ncon, ctrl_t::ncuts, ctrl_t::niter, ctrl_t::nparts, ctrl_t::nseps, ctrl_t::numflag, ctrl_t::objtype, ctrl_t::optype, ctrl_t::pfactor, ctrl_t::rtype, ctrl_t::tpwgts, ctrl_t::ubfactors, and ctrl_t::ufactor.

Referenced by SetupCtrl().

Here is the caller graph for this function:

void FreeCtrl ( ctrl_t ** r_ctrl )

This function frees the memory associated with a ctrl_t

Definition at line 520 of file options.c.

References FreeWorkSpace(), gk_free(), ctrl_t::maxvwgt, ctrl_t::pijbm, ctrl_t::tpwgts, and ctrl_t::ubfactors.

Referenced by METIS_ComputeVertexSeparator(), METIS_NodeND(), METIS_NodeNDP(), METIS_NodeRefine(), METIS_PartGraphKway(), METIS_PartGraphRecursive(), and SetupCtrl().

Here is the call graph for this function:

Here is the caller graph for this function:

void MlevelNestedDissectionP	(	ctrl_t *	ctrl,
		graph_t *	graph,
		idx_t *	order,
		idx_t	lastvtx,
		idx_t	npes,
		idx_t	cpos,
		idx_t *	sizes
	)

This function is similar to MlevelNestedDissection with the difference that it also records separator sizes for the top log2(npes) levels

Definition at line 105 of file parmetis.c.

References graph_t::bndind, ctrl_t::dbglvl, FreeGraph(), graph_t::label, METIS_DBG_SEPINFO, MlevelNestedDissectionP(), MlevelNodeBisectionMultiple(), MMDOrder(), graph_t::nbnd, graph_t::nedges, graph_t::nvtxs, graph_t::pwgts, and SplitGraphOrder().

Referenced by METIS_NodeNDP(), and MlevelNestedDissectionP().

Here is the call graph for this function:

Here is the caller graph for this function:

void FM_2WayNodeRefine1SidedP	(	ctrl_t *	ctrl,
		graph_t *	graph,
		idx_t *	hmarker,
		real_t	ubfactor,
		idx_t	npasses
	)

This function performs a node-based 1-sided FM refinement that moves only nodes whose hmarker[] == -1. It is used by Parmetis.

Definition at line 237 of file parmetis.c.

References abs(), graph_t::adjncy, adjncy, graph_t::bndind, graph_t::bndptr, CheckNodeBnd(), CheckNodePartitionParams(), ctrl_t::dbglvl, nrinfo_t::edegrees, iwspacemalloc(), METIS_DBG_MOVEINFO, METIS_DBG_REFINE, graph_t::mincut, graph_t::nbnd, graph_t::nrinfo, graph_t::nvtxs, graph_t::pwgts, rpq_t, graph_t::vwgt, vwgt, graph_t::where, where, graph_t::xadj, and xadj.

Referenced by METIS_NodeRefine().

Here is the call graph for this function:

Here is the caller graph for this function:

void FM_2WayNodeRefine2SidedP	(	ctrl_t *	ctrl,
		graph_t *	graph,
		idx_t *	hmarker,
		real_t	ubfactor,
		idx_t	npasses
	)

This function performs a node-based (two-sided) FM refinement that moves only nodes whose hmarker[] == -1. It is used by Parmetis.

Definition at line 467 of file parmetis.c.

References abs(), graph_t::adjncy, adjncy, graph_t::bndind, graph_t::bndptr, CheckNodeBnd(), CheckNodePartitionParams(), ctrl_t::dbglvl, nrinfo_t::edegrees, iwspacemalloc(), METIS_DBG_MOVEINFO, METIS_DBG_REFINE, graph_t::mincut, graph_t::nbnd, graph_t::nrinfo, graph_t::nvtxs, graph_t::pwgts, rpq_t, PUP::u, graph_t::vwgt, vwgt, graph_t::where, where, graph_t::xadj, and xadj.

Here is the call graph for this function:

idx_t MlevelRecursiveBisection	(	ctrl_t *	ctrl,
		graph_t *	graph,
		idx_t	nparts,
		idx_t *	part,
		real_t *	tpwgts,
		idx_t	fpart
	)

This function is the top-level driver of the recursive bisection routine.

Definition at line 157 of file pmetis.c.

References FreeGraph(), graph_t::label, MlevelRecursiveBisection(), MultilevelBisect(), graph_t::ncon, ncon, graph_t::nvtxs, objval, rwspacemalloc(), SplitGraphPart(), graph_t::where, and where.

Referenced by METIS_PartGraphRecursive(), and MlevelRecursiveBisection().

Here is the call graph for this function:

Here is the caller graph for this function:

idx_t MultilevelBisect	(	ctrl_t *	ctrl,
		graph_t *	graph,
		real_t *	tpwgts
	)

This function performs a multilevel bisection

Definition at line 226 of file pmetis.c.

References CoarsenGraph(), ctrl_t::CoarsenTo, Compute2WayPartitionParams(), ComputeLoadImbalanceDiff(), FreeRData(), Init2WayPartition(), iwspacemalloc(), graph_t::mincut, ctrl_t::ncuts, graph_t::nvtxs, ctrl_t::pijbm, Refine2Way(), Setup2WayBalMultipliers(), ctrl_t::ubfactors, and graph_t::where.

Referenced by MlevelRecursiveBisection().

Here is the call graph for this function:

Here is the caller graph for this function:

void SplitGraphPart	(	ctrl_t *	ctrl,
		graph_t *	graph,
		graph_t **	r_lgraph,
		graph_t **	r_rgraph
	)

This function splits a graph into two based on its bisection

Definition at line 280 of file pmetis.c.

References graph_t::adjncy, adjncy, graph_t::adjwgt, adjwgt, graph_t::bndptr, ctrl_t::dbglvl, iwspacemalloc(), PUP::l, graph_t::label, METIS_DBG_TIME, graph_t::ncon, ncon, graph_t::nedges, graph_t::nvtxs, SetupGraph_tvwgt(), SetupSplitGraph(), ctrl_t::SplitTmr, graph_t::vwgt, vwgt, graph_t::where, where, graph_t::xadj, and xadj.

Referenced by MlevelRecursiveBisection().

Here is the call graph for this function:

Here is the caller graph for this function:

void Refine2Way	(	ctrl_t *	ctrl,
		graph_t *	orggraph,
		graph_t *	graph,
		real_t *	tpwgts
	)

This function is the entry point of refinement

Definition at line 17 of file refine.c.

References Balance2Way(), CheckBnd(), Compute2WayPartitionParams(), ctrl_t::dbglvl, graph_t::finer, FM_2WayRefine(), METIS_DBG_TIME, ctrl_t::niter, Project2WayPartition(), ctrl_t::ProjectTmr, ctrl_t::RefTmr, and ctrl_t::UncoarsenTmr.

Referenced by MultilevelBisect().

Here is the call graph for this function:

Here is the caller graph for this function:

void Allocate2WayPartitionMemory	(	ctrl_t *	ctrl,
		graph_t *	graph
	)

This function allocates memory for 2-way edge refinement

Definition at line 52 of file refine.c.

References graph_t::bndind, graph_t::bndptr, graph_t::ed, graph_t::id, graph_t::ncon, ncon, graph_t::nvtxs, graph_t::pwgts, and graph_t::where.

Referenced by GrowBisection(), McGrowBisection(), McRandomBisection(), Project2WayPartition(), and RandomBisection().

Here is the caller graph for this function:

void Compute2WayPartitionParams	(	ctrl_t *	ctrl,
		graph_t *	graph
	)

This function computes the initial id/ed

Definition at line 71 of file refine.c.

References graph_t::adjncy, adjncy, graph_t::adjwgt, adjwgt, graph_t::bndind, graph_t::bndptr, graph_t::ed, graph_t::id, graph_t::mincut, graph_t::nbnd, graph_t::ncon, ncon, graph_t::nvtxs, graph_t::pwgts, graph_t::tvwgt, graph_t::vwgt, vwgt, graph_t::where, where, graph_t::xadj, and xadj.

Referenced by GrowBisection(), GrowBisectionNode(), GrowBisectionNode2(), InitSeparator(), McGrowBisection(), McRandomBisection(), MultilevelBisect(), RandomBisection(), and Refine2Way().

Here is the caller graph for this function:

void Project2WayPartition	(	ctrl_t *	ctrl,
		graph_t *	graph
	)

Projects a partition and computes the refinement params.

Definition at line 141 of file refine.c.

References graph_t::adjncy, adjncy, graph_t::adjwgt, adjwgt, Allocate2WayPartitionMemory(), graph_t::bndind, graph_t::bndptr, graph_t::cmap, graph_t::coarser, graph_t::ed, FreeGraph(), graph_t::id, graph_t::mincut, graph_t::nbnd, graph_t::ncon, graph_t::nvtxs, graph_t::pwgts, graph_t::where, where, graph_t::xadj, and xadj.

Referenced by Refine2Way().

Here is the call graph for this function:

Here is the caller graph for this function:

void ConstructSeparator	(	ctrl_t *	ctrl,
		graph_t *	graph
	)

Definition at line 21 of file separator.c.

References Allocate2WayNodePartitionMemory(), graph_t::bndind, CheckNodePartitionParams(), Compute2WayNodePartitionParams(), FM_2WayNodeRefine1Sided(), FM_2WayNodeRefine2Sided(), FreeRData(), IsSeparable(), iwspacemalloc(), graph_t::nbnd, graph_t::nvtxs, graph_t::where, where, graph_t::xadj, and xadj.

Referenced by InitSeparator().

Here is the call graph for this function:

Here is the caller graph for this function:

void ConstructMinCoverSeparator	(	ctrl_t *	ctrl,
		graph_t *	graph
	)

Definition at line 69 of file separator.c.

References graph_t::adjncy, adjncy, Allocate2WayNodePartitionMemory(), graph_t::bndind, graph_t::bndptr, CheckNodePartitionParams(), Compute2WayNodePartitionParams(), ctrl_t::dbglvl, FM_2WayNodeRefine1Sided(), FreeRData(), IsSeparable(), iwspacemalloc(), PUP::l, METIS_DBG_SEPINFO, MinCover(), graph_t::mincut, graph_t::nbnd, ctrl_t::niter, graph_t::nvtxs, graph_t::pwgts, graph_t::where, where, graph_t::xadj, and xadj.

Here is the call graph for this function:

void FM_2WayNodeRefine2Sided	(	ctrl_t *	ctrl,
		graph_t *	graph,
		idx_t	niter
	)

This function performs a node-based FM refinement

Definition at line 21 of file sfm.c.

References graph_t::adjncy, adjncy, graph_t::bndind, graph_t::bndptr, CheckNodeBnd(), CheckNodePartitionParams(), ctrl_t::compress, ctrl_t::dbglvl, nrinfo_t::edegrees, iwspacemalloc(), METIS_DBG_MOVEINFO, METIS_DBG_REFINE, graph_t::mincut, graph_t::nbnd, graph_t::nrinfo, graph_t::nvtxs, graph_t::pwgts, rpq_t, PUP::u, ctrl_t::ubfactors, graph_t::vwgt, vwgt, graph_t::where, where, graph_t::xadj, and xadj.

Referenced by ConstructSeparator(), GrowBisectionNode(), GrowBisectionNode2(), and Refine2WayNode().

Here is the call graph for this function:

Here is the caller graph for this function:

void FM_2WayNodeRefine1Sided	(	ctrl_t *	ctrl,
		graph_t *	graph,
		idx_t	niter
	)

This function performs a node-based FM refinement. Each refinement iteration is split into two sub-iterations. In each sub-iteration only moves to one of the left/right partitions is allowed; hence, it is one-sided.

Definition at line 263 of file sfm.c.

References graph_t::adjncy, adjncy, ctrl_t::Aux1Tmr, ctrl_t::Aux2Tmr, ctrl_t::Aux3Tmr, graph_t::bndind, graph_t::bndptr, CheckNodeBnd(), CheckNodePartitionParams(), ctrl_t::compress, ctrl_t::dbglvl, nrinfo_t::edegrees, iwspacemalloc(), METIS_DBG_MOVEINFO, METIS_DBG_REFINE, METIS_DBG_TIME, graph_t::mincut, graph_t::nbnd, graph_t::nrinfo, graph_t::nvtxs, graph_t::pwgts, rpq_t, ctrl_t::ubfactors, graph_t::vwgt, vwgt, graph_t::where, where, graph_t::xadj, and xadj.

Referenced by ConstructMinCoverSeparator(), ConstructSeparator(), GrowBisectionNode(), and Refine2WayNode().

Here is the call graph for this function:

Here is the caller graph for this function:

void FM_2WayNodeBalance	(	ctrl_t *	ctrl,
		graph_t *	graph
	)

This function balances the left/right partitions of a separator tri-section

Definition at line 476 of file sfm.c.

References graph_t::adjncy, adjncy, graph_t::bndind, graph_t::bndptr, CheckNodeBnd(), CheckNodePartitionParams(), ctrl_t::dbglvl, nrinfo_t::edegrees, iwspacemalloc(), METIS_DBG_MOVEINFO, METIS_DBG_REFINE, graph_t::mincut, graph_t::nbnd, graph_t::nrinfo, graph_t::nvtxs, perm, graph_t::pwgts, rpq_t, graph_t::tvwgt, ctrl_t::ubfactors, graph_t::vwgt, vwgt, graph_t::where, where, graph_t::xadj, and xadj.

Referenced by Refine2WayNode().

Here is the call graph for this function:

Here is the caller graph for this function:

void Refine2WayNode	(	ctrl_t *	ctrl,
		graph_t *	orggraph,
		graph_t *	graph
	)

This function is the entry point of the separator refinement. It does not perform any refinement on graph, but it starts by first projecting it to the next level finer graph and proceeds from there.

Definition at line 23 of file srefine.c.

References CheckNodePartitionParams(), Compute2WayNodePartitionParams(), ctrl_t::dbglvl, graph_t::finer, FM_2WayNodeBalance(), FM_2WayNodeRefine1Sided(), FM_2WayNodeRefine2Sided(), gk_errexit(), METIS_DBG_TIME, METIS_RTYPE_SEP1SIDED, METIS_RTYPE_SEP2SIDED, ctrl_t::niter, Project2WayNodePartition(), ctrl_t::ProjectTmr, ctrl_t::RefTmr, ctrl_t::rtype, and ctrl_t::UncoarsenTmr.

Referenced by MlevelNodeBisectionL1(), and MlevelNodeBisectionL2().

Here is the call graph for this function:

Here is the caller graph for this function:

void Allocate2WayNodePartitionMemory	(	ctrl_t *	ctrl,
		graph_t *	graph
	)

This function allocates memory for 2-way node-based refinement

Definition at line 66 of file srefine.c.

References graph_t::bndind, graph_t::bndptr, gk_malloc(), graph_t::nrinfo, graph_t::nvtxs, graph_t::pwgts, and graph_t::where.

Referenced by ConstructMinCoverSeparator(), ConstructSeparator(), METIS_NodeRefine(), and Project2WayNodePartition().

Here is the call graph for this function:

Here is the caller graph for this function:

void Compute2WayNodePartitionParams	(	ctrl_t *	ctrl,
		graph_t *	graph
	)

This function computes the edegrees[] to the left & right sides

Definition at line 83 of file srefine.c.

References graph_t::adjncy, adjncy, graph_t::bndind, graph_t::bndptr, CheckNodeBnd(), nrinfo_t::edegrees, graph_t::mincut, graph_t::nbnd, graph_t::nrinfo, graph_t::nvtxs, graph_t::pwgts, graph_t::vwgt, vwgt, graph_t::where, where, graph_t::xadj, and xadj.

Referenced by ConstructMinCoverSeparator(), ConstructSeparator(), GrowBisectionNode(), GrowBisectionNode2(), METIS_NodeRefine(), MlevelNodeBisectionMultiple(), Project2WayNodePartition(), and Refine2WayNode().

Here is the call graph for this function:

Here is the caller graph for this function:

void Project2WayNodePartition	(	ctrl_t *	ctrl,
		graph_t *	graph
	)

This function projects the node-based bisection

Definition at line 137 of file srefine.c.

References Allocate2WayNodePartitionMemory(), graph_t::cmap, graph_t::coarser, Compute2WayNodePartitionParams(), FreeGraph(), graph_t::nvtxs, graph_t::where, and where.

Referenced by Refine2WayNode().

Here is the call graph for this function:

Here is the caller graph for this function:

void ComputePartitionInfoBipartite	(	graph_t *	,
		idx_t	,
		idx_t *
	)

Definition at line 21 of file stat.c.

References graph_t::adjncy, adjncy, graph_t::adjwgt, adjwgt, ComputeCut(), ComputeVolume(), gk_free(), iargmax_strd(), graph_t::ncon, ncon, graph_t::nvtxs, graph_t::vsize, vsize, graph_t::vwgt, vwgt, graph_t::xadj, and xadj.

Here is the call graph for this function:

void ComputePartitionBalance	(	graph_t *	,
		idx_t	,
		idx_t *	,
		real_t *
	)

Definition at line 125 of file stat.c.

References gk_free(), graph_t::ncon, ncon, graph_t::nvtxs, graph_t::vwgt, and vwgt.

Here is the call graph for this function:

real_t ComputeElementBalance	(	idx_t	,
		idx_t	,
		idx_t *
	)

Definition at line 160 of file stat.c.

References gk_free().

Here is the call graph for this function:

void InitTimers ( ctrl_t * )

Definition at line 21 of file timing.c.

References ctrl_t::Aux1Tmr, ctrl_t::Aux2Tmr, ctrl_t::Aux3Tmr, ctrl_t::CoarsenTmr, ctrl_t::ContractTmr, ctrl_t::InitPartTmr, ctrl_t::MatchTmr, ctrl_t::ProjectTmr, ctrl_t::RefTmr, ctrl_t::SplitTmr, ctrl_t::TotalTmr, and ctrl_t::UncoarsenTmr.

Referenced by METIS_NodeND(), METIS_NodeNDP(), METIS_PartGraphKway(), and METIS_PartGraphRecursive().

Here is the caller graph for this function:

void PrintTimers ( ctrl_t * )

Definition at line 42 of file timing.c.

References ctrl_t::CoarsenTmr, ctrl_t::ContractTmr, ctrl_t::InitPartTmr, ctrl_t::MatchTmr, ctrl_t::ProjectTmr, ctrl_t::RefTmr, ctrl_t::SplitTmr, ctrl_t::TotalTmr, and ctrl_t::UncoarsenTmr.

Referenced by METIS_NodeND(), METIS_NodeNDP(), METIS_PartGraphKway(), and METIS_PartGraphRecursive().

Here is the caller graph for this function:

idx_t iargmax_strd	(	size_t	n,
		idx_t *	x,
		idx_t	incx
	)

These functions return the index of the maximum element in a vector

Definition at line 46 of file util.c.

References max().

Referenced by ComputePartitionInfo(), and ComputePartitionInfoBipartite().

Here is the call graph for this function:

Here is the caller graph for this function:

idx_t iargmax_nrm	(	size_t	n,
		idx_t *	x,
		real_t *	y
	)

Returns the highest weight index of x[i]*y[i]

Definition at line 31 of file util.c.

References max().

Referenced by FM_Mc2WayCutRefine(), and McGeneral2WayBalance().

Here is the call graph for this function:

Here is the caller graph for this function:

idx_t iargmax2_nrm	(	size_t	n,
		idx_t *	x,
		real_t *	y
	)

These functions return the index of the second largest elements in the vector formed by x.y where '.' is element-wise multiplication

Definition at line 93 of file util.c.

Referenced by McGeneral2WayBalance().

Here is the caller graph for this function:

idx_t rargmax2	(	size_t	n,
		real_t *	x
	)

These functions return the index of the almost maximum element in a vector

Definition at line 63 of file util.c.

void InitRandom ( idx_t seed )

This function initializes the random number generator

Definition at line 21 of file util.c.

Referenced by METIS_ComputeVertexSeparator(), and SetupCtrl().

Here is the caller graph for this function:

int metis_rcode ( int sigrval )

converts a signal code into a Metis return code

Definition at line 123 of file util.c.

References METIS_ERROR, METIS_ERROR_MEMORY, and METIS_OK.

Referenced by METIS_MeshToDual(), METIS_MeshToNodal(), METIS_NodeND(), METIS_PartGraphKway(), METIS_PartGraphRecursive(), METIS_PartMeshDual(), and METIS_PartMeshNodal().

Here is the caller graph for this function:

void AllocateWorkSpace	(	ctrl_t *	ctrl,
		graph_t *	graph
	)

This function allocates memory for the workspace

Definition at line 17 of file wspace.c.

References gk_mcoreCreate(), ctrl_t::mcore, METIS_OP_PMETIS, ctrl_t::nbrpoolcpos, ctrl_t::nbrpoolsize, graph_t::ncon, ctrl_t::nparts, graph_t::nvtxs, and ctrl_t::optype.

Referenced by METIS_ComputeVertexSeparator(), METIS_NodeND(), METIS_NodeNDP(), METIS_NodeRefine(), METIS_PartGraphKway(), METIS_PartGraphRecursive(), and MlevelKWayPartitioning().

Here is the call graph for this function:

Here is the caller graph for this function:

void AllocateRefinementWorkSpace	(	ctrl_t *	ctrl,
		idx_t	nbrpoolsize
	)

This function allocates refinement-specific memory for the workspace

Definition at line 43 of file wspace.c.

References ctrl_t::adids, ctrl_t::adwgts, ctrl_t::cnbrpool, gk_errexit(), gk_malloc(), ctrl_t::maxnads, METIS_OBJTYPE_CUT, METIS_OBJTYPE_VOL, ctrl_t::minconn, ctrl_t::nads, ctrl_t::nbrpoolcpos, ctrl_t::nbrpoolreallocs, ctrl_t::nbrpoolsize, ctrl_t::nparts, ctrl_t::objtype, ctrl_t::pvec1, ctrl_t::pvec2, and ctrl_t::vnbrpool.

Referenced by MlevelKWayPartitioning().

Here is the call graph for this function:

Here is the caller graph for this function:

void FreeWorkSpace ( ctrl_t * ctrl )

This function frees the workspace

Definition at line 80 of file wspace.c.

References ctrl_t::adids, ctrl_t::adwgts, ctrl_t::cnbrpool, ctrl_t::dbglvl, gk_free(), gk_mcoreDestroy(), ctrl_t::maxnads, ctrl_t::mcore, METIS_DBG_INFO, ctrl_t::minconn, ctrl_t::nads, ctrl_t::nbrpoolcpos, ctrl_t::nbrpoolreallocs, ctrl_t::nbrpoolsize, ctrl_t::nparts, ctrl_t::pvec1, ctrl_t::pvec2, and ctrl_t::vnbrpool.

Referenced by FreeCtrl(), and MlevelKWayPartitioning().

Here is the call graph for this function:

Here is the caller graph for this function:

void* wspacemalloc	(	ctrl_t *	ctrl,
		size_t	nbytes
	)

This function allocate space from the workspace/heap

Definition at line 108 of file wspace.c.

References gk_mcoreMalloc(), and ctrl_t::mcore.

Referenced by CheckKWayVolPartitionParams(), EliminateComponents(), FM_Mc2WayCutRefine(), ikvwspacemalloc(), iwspacemalloc(), McGeneral2WayBalance(), and rwspacemalloc().

Here is the call graph for this function:

Here is the caller graph for this function:

void wspacepush ( ctrl_t * ctrl )

This function sets a marker in the stack of malloc ops to be used subsequently for freeing purposes

Definition at line 118 of file wspace.c.

References gk_mcorePush(), and ctrl_t::mcore.

Here is the call graph for this function:

void wspacepop ( ctrl_t * ctrl )

This function frees all mops since the last push

Definition at line 127 of file wspace.c.

References gk_mcorePop(), and ctrl_t::mcore.

Here is the call graph for this function:

idx_t* iwspacemalloc	(	ctrl_t *	ctrl,
		idx_t	n
	)

This function allocate space from the core

Definition at line 136 of file wspace.c.

References wspacemalloc().

Referenced by Bnd2WayBalance(), BucketSortKeysInc(), ComputeBFSOrdering(), ComputeKWayVolGains(), ComputeSubDomainGraph(), ConstructMinCoverSeparator(), ConstructSeparator(), CreateCoarseGraph(), CreateCoarseGraphNoMask(), CreateCoarseGraphPerm(), EliminateComponents(), EliminateSubDomainEdges(), FM_2WayCutRefine(), FM_2WayNodeBalance(), FM_2WayNodeRefine1Sided(), FM_2WayNodeRefine1SidedP(), FM_2WayNodeRefine2Sided(), FM_2WayNodeRefine2SidedP(), FM_Mc2WayCutRefine(), General2WayBalance(), Greedy_KWayCutOptimize(), Greedy_KWayVolOptimize(), Greedy_McKWayCutOptimize(), Greedy_McKWayVolOptimize(), GrowBisection(), GrowBisectionNode(), GrowBisectionNode2(), Match_2HopAll(), Match_2HopAny(), Match_RM(), Match_SHEM(), McGeneral2WayBalance(), McGrowBisection(), McRandomBisection(), MlevelNestedDissectionCC(), MlevelNodeBisectionL2(), MlevelNodeBisectionMultiple(), MMDOrder(), MultilevelBisect(), ProjectKWayPartition(), RandomBisection(), SplitGraphOrder(), SplitGraphOrderCC(), and SplitGraphPart().

Here is the call graph for this function:

Here is the caller graph for this function:

real_t* rwspacemalloc	(	ctrl_t *	ctrl,
		idx_t	n
	)

This function allocate space from the core

Definition at line 145 of file wspace.c.

References wspacemalloc().

Referenced by FM_Mc2WayCutRefine(), Greedy_McKWayCutOptimize(), Greedy_McKWayVolOptimize(), McGeneral2WayBalance(), and MlevelRecursiveBisection().

Here is the call graph for this function:

Here is the caller graph for this function:

ikv_t* ikvwspacemalloc	(	ctrl_t *	ctrl,
		idx_t	n
	)

This function allocate space from the core

Definition at line 154 of file wspace.c.

References wspacemalloc().

Referenced by EliminateSubDomainEdges(), and Match_2HopAll().

Here is the call graph for this function:

Here is the caller graph for this function:

void cnbrpoolReset ( ctrl_t * ctrl )

This function resets the cnbrpool

Definition at line 163 of file wspace.c.

References ctrl_t::nbrpoolcpos.

Referenced by ComputeKWayPartitionParams(), and ProjectKWayPartition().

Here is the caller graph for this function:

idx_t cnbrpoolGetNext	(	ctrl_t *	ctrl,
		idx_t	nnbrs
	)

This function gets the next free index from cnbrpool

Definition at line 172 of file wspace.c.

References ctrl_t::cnbrpool, gk_realloc(), ctrl_t::nbrpoolcpos, ctrl_t::nbrpoolreallocs, and ctrl_t::nbrpoolsize.

Referenced by ComputeKWayPartitionParams(), MoveGroupContigForCut(), MoveGroupMinConnForCut(), and ProjectKWayPartition().

Here is the call graph for this function:

Here is the caller graph for this function:

void vnbrpoolReset ( ctrl_t * ctrl )

This function resets the vnbrpool

Definition at line 191 of file wspace.c.

References ctrl_t::nbrpoolcpos.

Referenced by ComputeKWayPartitionParams(), and ProjectKWayPartition().

Here is the caller graph for this function:

idx_t vnbrpoolGetNext	(	ctrl_t *	ctrl,
		idx_t	nnbrs
	)

This function gets the next free index from vnbrpool

Definition at line 200 of file wspace.c.

References gk_realloc(), ctrl_t::nbrpoolcpos, ctrl_t::nbrpoolreallocs, ctrl_t::nbrpoolsize, and ctrl_t::vnbrpool.

Referenced by ComputeKWayPartitionParams(), KWayVolUpdate(), MoveGroupContigForVol(), MoveGroupMinConnForVol(), and ProjectKWayPartition().

Here is the call graph for this function:

Here is the caller graph for this function:


Functions
void	Balance2Way (ctrl_t ctrl, graph_t graph, real_t *ntpwgts)
void	Bnd2WayBalance (ctrl_t ctrl, graph_t graph, real_t *ntpwgts)
void	General2WayBalance (ctrl_t ctrl, graph_t graph, real_t *ntpwgts)
void	McGeneral2WayBalance (ctrl_t ctrl, graph_t graph, real_t *ntpwgts)
void	BucketSortKeysInc (ctrl_t ctrl, idx_t n, idx_t max, idx_t keys, idx_t tperm, idx_t perm)
int	CheckGraph (graph_t *graph, int numflag, int verbose)
int	CheckInputGraphWeights (idx_t nvtxs, idx_t ncon, idx_t xadj, idx_t adjncy, idx_t vwgt, idx_t vsize, idx_t *adjwgt)
graph_t *	FixGraph (graph_t *graph)
graph_t *	CoarsenGraph (ctrl_t ctrl, graph_t graph)
graph_t *	CoarsenGraphNlevels (ctrl_t ctrl, graph_t graph, idx_t nlevels)
idx_t	Match_RM (ctrl_t ctrl, graph_t graph)
idx_t	Match_SHEM (ctrl_t ctrl, graph_t graph)
idx_t	Match_2Hop (ctrl_t ctrl, graph_t graph, idx_t perm, idx_t match, idx_t cnvtxs, size_t nunmatched)
idx_t	Match_2HopAny (ctrl_t ctrl, graph_t graph, idx_t perm, idx_t match, idx_t cnvtxs, size_t *r_nunmatched, size_t maxdegree)
idx_t	Match_2HopAll (ctrl_t ctrl, graph_t graph, idx_t perm, idx_t match, idx_t cnvtxs, size_t *r_nunmatched, size_t maxdegree)
void	PrintCGraphStats (ctrl_t ctrl, graph_t graph)
void	CreateCoarseGraph (ctrl_t ctrl, graph_t graph, idx_t cnvtxs, idx_t *match)
void	CreateCoarseGraphNoMask (ctrl_t ctrl, graph_t graph, idx_t cnvtxs, idx_t *match)
void	CreateCoarseGraphPerm (ctrl_t ctrl, graph_t graph, idx_t cnvtxs, idx_t match, idx_t perm)
graph_t *	SetupCoarseGraph (graph_t *graph, idx_t cnvtxs, idx_t dovsize)
void	ReAdjustMemory (ctrl_t ctrl, graph_t graph, graph_t *cgraph)
graph_t *	CompressGraph (ctrl_t ctrl, idx_t nvtxs, idx_t xadj, idx_t adjncy, idx_t vwgt, idx_t cptr, idx_t cind)
graph_t *	PruneGraph (ctrl_t ctrl, idx_t nvtxs, idx_t xadj, idx_t adjncy, idx_t vwgt, idx_t *iperm, real_t factor)
idx_t	FindPartitionInducedComponents (graph_t graph, idx_t where, idx_t cptr, idx_t cind)
void	ComputeBFSOrdering (ctrl_t ctrl, graph_t graph, idx_t *bfsperm)
idx_t	IsConnected (graph_t *graph, idx_t report)
idx_t	IsConnectedSubdomain (ctrl_t , graph_t , idx_t, idx_t)
idx_t	FindSepInducedComponents (ctrl_t , graph_t , idx_t , idx_t )
void	EliminateComponents (ctrl_t ctrl, graph_t graph)
void	MoveGroupContigForCut (ctrl_t ctrl, graph_t graph, idx_t to, idx_t gid, idx_t ptr, idx_t ind)
void	MoveGroupContigForVol (ctrl_t ctrl, graph_t graph, idx_t to, idx_t gid, idx_t ptr, idx_t ind, idx_t vmarker, idx_t pmarker, idx_t *modind)
idx_t	ComputeCut (graph_t graph, idx_t where)
idx_t	ComputeVolume (graph_t , idx_t )
idx_t	ComputeMaxCut (graph_t graph, idx_t nparts, idx_t where)
idx_t	CheckBnd (graph_t *)
idx_t	CheckBnd2 (graph_t *)
idx_t	CheckNodeBnd (graph_t *, idx_t)
idx_t	CheckRInfo (ctrl_t ctrl, ckrinfo_t rinfo)
idx_t	CheckNodePartitionParams (graph_t *)
idx_t	IsSeparable (graph_t *)
void	CheckKWayVolPartitionParams (ctrl_t ctrl, graph_t graph)
void	FM_2WayRefine (ctrl_t ctrl, graph_t graph, real_t *ntpwgts, idx_t niter)
void	FM_2WayCutRefine (ctrl_t ctrl, graph_t graph, real_t *ntpwgts, idx_t niter)
void	FM_Mc2WayCutRefine (ctrl_t ctrl, graph_t graph, real_t *ntpwgts, idx_t niter)
void	SelectQueue (graph_t graph, real_t pijbm, real_t ubfactors, rpq_t queues, idx_t from, idx_t *cnum)
void	Print2WayRefineStats (ctrl_t ctrl, graph_t graph, real_t *ntpwgts, real_t deltabal, idx_t mincutorder)
void	Change2CNumbering (idx_t, idx_t , idx_t )
void	Change2FNumbering (idx_t, idx_t , idx_t , idx_t *)
void	Change2FNumbering2 (idx_t, idx_t , idx_t )
void	Change2FNumberingOrder (idx_t, idx_t , idx_t , idx_t , idx_t )
void	ChangeMesh2CNumbering (idx_t n, idx_t ptr, idx_t ind)
void	ChangeMesh2FNumbering (idx_t n, idx_t ptr, idx_t ind, idx_t nvtxs, idx_t xadj, idx_t adjncy)
void	ChangeMesh2FNumbering2 (idx_t ne, idx_t nn, idx_t ptr, idx_t ind, idx_t epart, idx_t npart)
graph_t *	SetupGraph (ctrl_t ctrl, idx_t nvtxs, idx_t ncon, idx_t xadj, idx_t adjncy, idx_t vwgt, idx_t vsize, idx_t adjwgt)
void	SetupGraph_tvwgt (graph_t *graph)
void	SetupGraph_label (graph_t *graph)
graph_t *	SetupSplitGraph (graph_t *graph, idx_t snvtxs, idx_t snedges)
graph_t *	CreateGraph (void)
void	InitGraph (graph_t *graph)
void	FreeRData (graph_t *graph)
void	FreeGraph (graph_t **graph)
void	Init2WayPartition (ctrl_t ctrl, graph_t graph, real_t *ntpwgts, idx_t niparts)
void	InitSeparator (ctrl_t ctrl, graph_t graph, idx_t niparts)
void	RandomBisection (ctrl_t ctrl, graph_t graph, real_t *ntpwgts, idx_t niparts)
void	GrowBisection (ctrl_t ctrl, graph_t graph, real_t *ntpwgts, idx_t niparts)
void	McRandomBisection (ctrl_t ctrl, graph_t graph, real_t *ntpwgts, idx_t niparts)
void	McGrowBisection (ctrl_t ctrl, graph_t graph, real_t *ntpwgts, idx_t niparts)
void	GrowBisectionNode (ctrl_t ctrl, graph_t graph, real_t *ntpwgts, idx_t niparts)
void	GrowBisectionNode2 (ctrl_t ctrl, graph_t graph, real_t *ntpwgts, idx_t niparts)
idx_t	MlevelKWayPartitioning (ctrl_t ctrl, graph_t graph, idx_t *part)
void	InitKWayPartitioning (ctrl_t ctrl, graph_t graph)
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)
void	RefineKWay (ctrl_t ctrl, graph_t orggraph, graph_t *graph)
void	AllocateKWayPartitionMemory (ctrl_t ctrl, graph_t graph)
void	ComputeKWayPartitionParams (ctrl_t ctrl, graph_t graph)
void	ProjectKWayPartition (ctrl_t ctrl, graph_t graph)
void	ComputeKWayBoundary (ctrl_t ctrl, graph_t graph, idx_t bndtype)
void	ComputeKWayVolGains (ctrl_t ctrl, graph_t graph)
int	IsBalanced (ctrl_t ctrl, graph_t graph, real_t ffactor)
int	rvecle (idx_t n, real_t x, real_t y)
int	rvecge (idx_t n, real_t x, real_t y)
int	rvecsumle (idx_t n, real_t x1, real_t x2, real_t *y)
real_t	rvecmaxdiff (idx_t n, real_t x, real_t y)
int	ivecle (idx_t n, idx_t x, idx_t z)
int	ivecge (idx_t n, idx_t x, idx_t z)
int	ivecaxpylez (idx_t n, idx_t a, idx_t x, idx_t y, idx_t *z)
int	ivecaxpygez (idx_t n, idx_t a, idx_t x, idx_t y, idx_t *z)
int	BetterVBalance (idx_t ncon, real_t itvwgt, idx_t v_vwgt, idx_t u1_vwgt, idx_t u2_vwgt)
int	BetterBalance2Way (idx_t n, real_t x, real_t y)
int	BetterBalanceKWay (idx_t ncon, idx_t vwgt, real_t itvwgt, idx_t a1, idx_t pt1, real_t bm1, idx_t a2, idx_t pt2, real_t bm2)
real_t	ComputeLoadImbalance (graph_t graph, idx_t nparts, real_t pijbm)
real_t	ComputeLoadImbalanceDiff (graph_t graph, idx_t nparts, real_t pijbm, real_t *ubvec)
real_t	ComputeLoadImbalanceDiffVec (graph_t graph, idx_t nparts, real_t pijbm, real_t ubfactors, real_t diffvec)
void	ComputeLoadImbalanceVec (graph_t graph, idx_t nparts, real_t pijbm, real_t *lbvec)
void	CreateGraphDual (idx_t ne, idx_t nn, idx_t eptr, idx_t eind, idx_t ncommon, idx_t r_xadj, idx_t r_adjncy)
idx_t	FindCommonElements (idx_t qid, idx_t elen, idx_t eind, idx_t nptr, idx_t nind, idx_t eptr, idx_t ncommon, idx_t marker, idx_t nbrs)
void	CreateGraphNodal (idx_t ne, idx_t nn, idx_t eptr, idx_t eind, idx_t r_xadj, idx_t r_adjncy)
idx_t	FindCommonNodes (idx_t qid, idx_t nelmnts, idx_t elmntids, idx_t eptr, idx_t eind, idx_t marker, idx_t *nbrs)
mesh_t *	CreateMesh (void)
void	InitMesh (mesh_t *mesh)
void	FreeMesh (mesh_t **mesh)
void	InduceRowPartFromColumnPart (idx_t nrows, idx_t rowptr, idx_t rowind, idx_t rpart, idx_t cpart, idx_t nparts, real_t *tpwgts)
void	ComputeSubDomainGraph (ctrl_t ctrl, graph_t graph)
void	UpdateEdgeSubDomainGraph (ctrl_t ctrl, idx_t u, idx_t v, idx_t ewgt, idx_t r_maxndoms)
void	PrintSubDomainGraph (graph_t graph, idx_t nparts, idx_t where)
void	EliminateSubDomainEdges (ctrl_t ctrl, graph_t graph)
void	MoveGroupMinConnForCut (ctrl_t ctrl, graph_t graph, idx_t to, idx_t nind, idx_t *ind)
void	MoveGroupMinConnForVol (ctrl_t ctrl, graph_t graph, idx_t to, idx_t nind, idx_t ind, idx_t vmarker, idx_t pmarker, idx_t modind)
void	MinCover (idx_t , idx_t , idx_t, idx_t, idx_t , idx_t )
idx_t	MinCover_Augment (idx_t , idx_t , idx_t, idx_t , idx_t , idx_t *, idx_t)
void	MinCover_Decompose (idx_t , idx_t , idx_t, idx_t, idx_t , idx_t , idx_t *)
void	MinCover_ColDFS (idx_t , idx_t , idx_t, idx_t , idx_t , idx_t)
void	MinCover_RowDFS (idx_t , idx_t , idx_t, idx_t , idx_t , idx_t)
void	genmmd (idx_t, idx_t , idx_t , idx_t , idx_t , idx_t, idx_t , idx_t , idx_t , idx_t , idx_t, idx_t *)
void	mmdelm (idx_t, idx_t xadj, idx_t , idx_t , idx_t , idx_t , idx_t , idx_t , idx_t , idx_t, idx_t)
idx_t	mmdint (idx_t, idx_t xadj, idx_t , idx_t , idx_t , idx_t , idx_t , idx_t , idx_t )
void	mmdnum (idx_t, idx_t , idx_t , idx_t *)
void	mmdupd (idx_t, idx_t, idx_t , idx_t , idx_t, idx_t , idx_t , idx_t , idx_t , idx_t , idx_t , idx_t , idx_t, idx_t tag)
void	MlevelNestedDissection (ctrl_t ctrl, graph_t graph, idx_t *order, idx_t lastvtx)
void	MlevelNestedDissectionCC (ctrl_t ctrl, graph_t graph, idx_t *order, idx_t lastvtx)
void	MlevelNodeBisectionMultiple (ctrl_t ctrl, graph_t graph)
void	MlevelNodeBisectionL2 (ctrl_t ctrl, graph_t graph, idx_t niparts)
void	MlevelNodeBisectionL1 (ctrl_t ctrl, graph_t graph, idx_t niparts)
void	SplitGraphOrder (ctrl_t ctrl, graph_t graph, graph_t r_lgraph, graph_t r_rgraph)
graph_t **	SplitGraphOrderCC (ctrl_t ctrl, graph_t graph, idx_t ncmps, idx_t cptr, idx_t cind)
void	MMDOrder (ctrl_t ctrl, graph_t graph, idx_t *order, idx_t lastvtx)
ctrl_t *	SetupCtrl (moptype_et optype, idx_t options, idx_t ncon, idx_t nparts, real_t tpwgts, real_t *ubvec)
void	SetupKWayBalMultipliers (ctrl_t ctrl, graph_t graph)
void	Setup2WayBalMultipliers (ctrl_t ctrl, graph_t graph, real_t *tpwgts)
void	PrintCtrl (ctrl_t *ctrl)
int	CheckParams (ctrl_t *ctrl)
void	FreeCtrl (ctrl_t **r_ctrl)
void	MlevelNestedDissectionP (ctrl_t ctrl, graph_t graph, idx_t order, idx_t lastvtx, idx_t npes, idx_t cpos, idx_t sizes)
void	FM_2WayNodeRefine1SidedP (ctrl_t ctrl, graph_t graph, idx_t *hmarker, real_t ubfactor, idx_t npasses)
void	FM_2WayNodeRefine2SidedP (ctrl_t ctrl, graph_t graph, idx_t *hmarker, real_t ubfactor, idx_t npasses)
idx_t	MlevelRecursiveBisection (ctrl_t ctrl, graph_t graph, idx_t nparts, idx_t part, real_t tpwgts, idx_t fpart)
idx_t	MultilevelBisect (ctrl_t ctrl, graph_t graph, real_t *tpwgts)
void	SplitGraphPart (ctrl_t ctrl, graph_t graph, graph_t r_lgraph, graph_t r_rgraph)
void	Refine2Way (ctrl_t ctrl, graph_t orggraph, graph_t graph, real_t rtpwgts)
void	Allocate2WayPartitionMemory (ctrl_t ctrl, graph_t graph)
void	Compute2WayPartitionParams (ctrl_t ctrl, graph_t graph)
void	Project2WayPartition (ctrl_t ctrl, graph_t graph)
void	ConstructSeparator (ctrl_t ctrl, graph_t graph)
void	ConstructMinCoverSeparator (ctrl_t ctrl, graph_t graph)
void	FM_2WayNodeRefine2Sided (ctrl_t ctrl, graph_t graph, idx_t niter)
void	FM_2WayNodeRefine1Sided (ctrl_t ctrl, graph_t graph, idx_t niter)
void	FM_2WayNodeBalance (ctrl_t ctrl, graph_t graph)
void	Refine2WayNode (ctrl_t ctrl, graph_t orggraph, graph_t *graph)
void	Allocate2WayNodePartitionMemory (ctrl_t ctrl, graph_t graph)
void	Compute2WayNodePartitionParams (ctrl_t ctrl, graph_t graph)
void	Project2WayNodePartition (ctrl_t ctrl, graph_t graph)
void	ComputePartitionInfoBipartite (graph_t , idx_t, idx_t )
void	ComputePartitionBalance (graph_t , idx_t, idx_t , real_t *)
real_t	ComputeElementBalance (idx_t, idx_t, idx_t *)
void	InitTimers (ctrl_t *)
void	PrintTimers (ctrl_t *)
idx_t	iargmax_strd (size_t, idx_t *, idx_t)
idx_t	iargmax_nrm (size_t n, idx_t x, real_t y)
idx_t	iargmax2_nrm (size_t n, idx_t x, real_t y)
idx_t	rargmax2 (size_t, real_t *)
void	InitRandom (idx_t)
int	metis_rcode (int sigrval)
void	AllocateWorkSpace (ctrl_t ctrl, graph_t graph)
void	AllocateRefinementWorkSpace (ctrl_t *ctrl, idx_t nbrpoolsize)
void	FreeWorkSpace (ctrl_t *ctrl)
void *	wspacemalloc (ctrl_t *ctrl, size_t nbytes)
void	wspacepush (ctrl_t *ctrl)
void	wspacepop (ctrl_t *ctrl)
idx_t *	iwspacemalloc (ctrl_t *, idx_t)
real_t *	rwspacemalloc (ctrl_t *, idx_t)
ikv_t *	ikvwspacemalloc (ctrl_t *, idx_t)
void	cnbrpoolReset (ctrl_t *ctrl)
idx_t	cnbrpoolGetNext (ctrl_t *ctrl, idx_t nnbrs)
void	vnbrpoolReset (ctrl_t *ctrl)
idx_t	vnbrpoolGetNext (ctrl_t *ctrl, idx_t nnbrs)

libs/ck-libs/metis/libmetis/proto.h File Reference

Functions

Function Documentation