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

#include "metislib.h"

Include dependency graph for coarsen.c:

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

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 10513 2011-07-07 22:06:03Z karypis $

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.

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.

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.

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.

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.

idx_t Match_RM	(	ctrl_t *	ctrl,
		graph_t *	graph
	)

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

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.

void PrintCGraphStats	(	ctrl_t *	ctrl,
		graph_t *	graph
	)

This function prints various stats for each graph during coarsening

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

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

Setup the various arrays for the coarse graph