Various routines with dealing with sparse graphs. More...

#include <GKlib.h>

Macros
#define	OMPMINOPS 50000

Functions
gk_graph_t *	gk_graph_Create ()

void	gk_graph_Init (gk_graph_t *graph)

void	gk_graph_Free (gk_graph_t **graph)

void	gk_graph_FreeContents (gk_graph_t *graph)

gk_graph_t *	gk_graph_Read (char *filename, int format, int isfewgts, int isfvwgts, int isfvsizes)

void	gk_graph_Write (gk_graph_t graph, char filename, int format)

gk_graph_t *	gk_graph_Dup (gk_graph_t *graph)

gk_graph_t *	gk_graph_ExtractSubgraph (gk_graph_t *graph, int vstart, int nvtxs)

gk_graph_t *	gk_graph_Reorder (gk_graph_t graph, int32_t perm, int32_t *iperm)

int	gk_graph_FindComponents (gk_graph_t graph, int32_t cptr, int32_t *cind)

void	gk_graph_ComputeBFSOrdering (gk_graph_t graph, int v, int32_t r_perm, int32_t *r_iperm)

void	gk_graph_ComputeBestFOrdering0 (gk_graph_t graph, int v, int type, int32_t r_perm, int32_t *r_iperm)

void	gk_graph_ComputeBestFOrdering (gk_graph_t graph, int v, int type, int32_t r_perm, int32_t *r_iperm)

void	gk_graph_SingleSourceShortestPaths (gk_graph_t graph, int v, void *r_sps)

Detailed Description

Various routines with dealing with sparse graphs.

Author: George Karypis

Version

$Id: graph.c 13328 2012-12-31 14:57:40Z karypis $

Function Documentation

§ gk_graph_ComputeBestFOrdering()

void gk_graph_ComputeBestFOrdering	(	gk_graph_t *	graph,
		int	v,
		int	type,
		int32_t **	r_perm,
		int32_t **	r_iperm
	)

This function computes a permutation of the vertices based on a best-first-traversal. It can be used for re-ordering the graph to reduce its bandwidth for better cache locality.

Parameters

§ gk_graph_ComputeBestFOrdering0()

void gk_graph_ComputeBestFOrdering0	(	gk_graph_t *	graph,
		int	v,
		int	type,
		int32_t **	r_perm,
		int32_t **	r_iperm
	)

This function computes a permutation of the vertices based on a best-first-traversal. It can be used for re-ordering the graph to reduce its bandwidth for better cache locality.

Parameters

§ gk_graph_ComputeBFSOrdering()

void gk_graph_ComputeBFSOrdering	(	gk_graph_t *	graph,
		int	v,
		int32_t **	r_perm,
		int32_t **	r_iperm
	)

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. The algorithm used is a simplified version of the method used to find the connected components.

Parameters

§ gk_graph_Create()

gk_graph_t* gk_graph_Create ( )

Allocate memory for a graph and initializes it

Returns: the allocated graph. The various fields are set to NULL.

§ gk_graph_Dup()

gk_graph_t* gk_graph_Dup ( gk_graph_t * graph )

Returns a copy of a graph.

Parameters

graph is the graph to be duplicated.

Returns: the newly created copy of the graph.

§ gk_graph_ExtractSubgraph()

gk_graph_t* gk_graph_ExtractSubgraph	(	gk_graph_t *	graph,
		int	vstart,
		int	nvtxs
	)

Returns a subgraph containing a set of consecutive vertices.

Parameters

graph	is the original graph.
vstart	is the starting vertex.
nvtxs	is the number of vertices from vstart to extract.

Returns: the newly created subgraph.

§ gk_graph_FindComponents()

int gk_graph_FindComponents	(	gk_graph_t *	graph,
		int32_t *	cptr,
		int32_t *	cind
	)

This function finds the connected components in a graph.

Parameters

graph	is the graph structure
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.

§ gk_graph_Free()

void gk_graph_Free ( gk_graph_t ** graph )

Frees all the memory allocated for a graph.

Parameters

graph is the graph to be freed.

§ gk_graph_FreeContents()

void gk_graph_FreeContents ( gk_graph_t * graph )

Frees only the memory allocated for the graph's different fields and sets them to NULL.

Parameters

graph is the graph whose contents will be freed.

§ gk_graph_Init()

void gk_graph_Init ( gk_graph_t * graph )

Initializes the graph.

Parameters

graph is the graph to be initialized.

§ gk_graph_Read()

gk_graph_t* gk_graph_Read	(	char *	filename,
		int	format,
		int	isfewgts,
		int	isfvwgts,
		int	isfvsizes
	)

Reads a sparse graph from the supplied file

Parameters

filename	is the file that stores the data.
format	is the graph format. The supported values are: GK_GRAPH_FMT_METIS.
isfewgts	is 1 if the edge-weights should be read as floats
isfvwgts	is 1 if the vertex-weights should be read as floats
isfvsizes	is 1 if the vertex-sizes should be read as floats

Returns: the graph that was read.

§ gk_graph_Reorder()

gk_graph_t* gk_graph_Reorder	(	gk_graph_t *	graph,
		int32_t *	perm,
		int32_t *	iperm
	)

Returns a graph that has been reordered according to the permutation.

Parameters

§ gk_graph_SingleSourceShortestPaths()

void gk_graph_SingleSourceShortestPaths	(	gk_graph_t *	graph,
		int	v,
		void **	r_sps
	)

This function computes the single-source shortest path lengths from the root node to all the other nodes in the graph. If the graph is not connected then, the sortest part to the vertices in the other components is -1.

Parameters

§ gk_graph_Write()

void gk_graph_Write	(	gk_graph_t *	graph,
		char *	filename,
		int	format
	)

Writes a graph into a file.

Parameters

graph	is the graph to be written,
filename	is the name of the output file.
format	is one of GK_GRAPH_FMT_METIS specifying the format of the output file.

Macros

Functions

Detailed Description

Function Documentation

§ gk_graph_ComputeBestFOrdering()

§ gk_graph_ComputeBestFOrdering0()

§ gk_graph_ComputeBFSOrdering()

§ gk_graph_Create()

§ gk_graph_Dup()

§ gk_graph_ExtractSubgraph()

§ gk_graph_FindComponents()

§ gk_graph_Free()

§ gk_graph_FreeContents()

§ gk_graph_Init()

§ gk_graph_Read()

§ gk_graph_Reorder()

§ gk_graph_SingleSourceShortestPaths()

§ gk_graph_Write()