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

#include "metislib.h"

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

§ ComputeBFSOrdering()

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.

§ EliminateComponents()

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.

§ FindPartitionInducedComponents()

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.

§ FindSepInducedComponents()

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.

§ IsConnected()

idx_t IsConnected	(	graph_t *	graph,
		idx_t	report
	)

This function checks whether a graph is contiguous or not.

§ IsConnectedSubdomain()

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

§ MoveGroupContigForCut()

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

§ MoveGroupContigForVol()

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