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

Functions that deal with eliminating disconnected partitions. More...

Go to the source code of this file.

Functions
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 *ctrl, graph_t *graph, idx_t pid, idx_t report)
idx_t	FindSepInducedComponents (ctrl_t *ctrl, graph_t *graph, idx_t *cptr, idx_t *cind)
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)

---

Detailed Description

Functions that deal with eliminating disconnected partitions.

Date:

Started 7/15/98

Author:

George

Copyright 1997-2009, Regents of the University of Minnesota

Version:

Id

contig.c 10513 2011-07-07 22:06:03Z karypis

Definition in file contig.c.

---

Function Documentation

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: