libs/ck-libs/metis/libmetis/coarsen.c File Reference

Functions for computing matchings during graph coarsening. More...

Detailed Description

Functions for computing matchings during graph coarsening.

Date:: Started 7/23/97

Author:: George
Copyright 1997-2011, Regents of the University of Minnesota

Version:

$Id: coarsen.c 13936 2013-03-30 03:59:09Z karypis $

Definition in file coarsen.c.

Function Documentation

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:


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