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

#include "metislib.h"

Include dependency graph for contig.c:

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

Function Documentation

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.

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.

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.

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.

idx_t IsConnected	(	graph_t *	graph,
		idx_t	report
	)

This function checks whether a graph is contiguous or not.

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

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

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