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

#include "metislib.h"

Macros
#define	UNMATCHEDFOR2HOP 0.10 /* The fraction of unmatched vertices that triggers 2-hop */

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)

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 $

Function Documentation

§ CoarsenGraph()

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.

§ CoarsenGraphNlevels()

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.

§ CreateCoarseGraph()

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.

§ CreateCoarseGraphNoMask()

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.

§ CreateCoarseGraphPerm()

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.

§ Match_2Hop()

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.

§ Match_2HopAll()

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.

§ Match_2HopAny()

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.

§ Match_RM()

idx_t Match_RM	(	ctrl_t *	ctrl,
		graph_t *	graph
	)

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

§ Match_SHEM()

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.

§ PrintCGraphStats()

void PrintCGraphStats	(	ctrl_t *	ctrl,
		graph_t *	graph
	)

This function prints various stats for each graph during coarsening

§ ReAdjustMemory()

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

§ SetupCoarseGraph()

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

Setup the various arrays for the coarse graph

Macros

Functions