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

#include <GKlib.h>

Include dependency graph for GKlib/graph.c:

Macros
#define	OMPMINOPS 50000

Functions
void	gk_graph_ComputeBestFOrdering (gk_graph_t graph, int v, int type, 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_ComputeBFSOrdering (gk_graph_t graph, int v, int32_t r_perm, int32_t *r_iperm)

gk_graph_t *	gk_graph_Create ()

gk_graph_t *	gk_graph_Dup (gk_graph_t *graph)

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

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

void	gk_graph_Free (gk_graph_t **graph)

void	gk_graph_FreeContents (gk_graph_t *graph)

void	gk_graph_Init (gk_graph_t *graph)

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

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

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

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

Detailed Description

Various routines with dealing with sparse graphs.

Author: George Karypis

Version

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

Definition in file GKlib/graph.c.

Macro Definition Documentation

◆ OMPMINOPS

#define OMPMINOPS 50000

Definition at line 12 of file GKlib/graph.c.

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

[IN]	graph is the graph structure.
[IN]	v is the starting vertex of the best-first traversal.
[IN]	type indicates the criteria to use to measure the 'bestness' of a vertex.
[OUT]	perm[i] stores the ID of vertex i in the re-ordered graph.
[OUT]	iperm[i] stores the ID of the vertex that corresponds to the ith vertex in the re-ordered graph.

Note: The perm or iperm (but not both) can be NULL, at which point, the corresponding arrays are not returned. Though the program works fine when both are NULL, doing that is not smart. The returned arrays should be freed with gk_free().

Definition at line 887 of file GKlib/graph.c.

◆ 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

[IN]	graph is the graph structure.
[IN]	v is the starting vertex of the best-first traversal.
[IN]	type indicates the criteria to use to measure the 'bestness' of a vertex.
[OUT]	perm[i] stores the ID of vertex i in the re-ordered graph.
[OUT]	iperm[i] stores the ID of the vertex that corresponds to the ith vertex in the re-ordered graph.

Note: The perm or iperm (but not both) can be NULL, at which point, the corresponding arrays are not returned. Though the program works fine when both are NULL, doing that is not smart. The returned arrays should be freed with gk_free().

Definition at line 762 of file GKlib/graph.c.

◆ 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

[IN]	graph is the graph structure
[IN]	v is the starting vertex of the BFS
[OUT]	perm[i] stores the ID of vertex i in the re-ordered graph.
[OUT]	iperm[i] stores the ID of the vertex that corresponds to the ith vertex in the re-ordered graph.

Note: The perm or iperm (but not both) can be NULL, at which point, the corresponding arrays are not returned. Though the program works fine when both are NULL, doing that is not smart. The returned arrays should be freed with gk_free().

Definition at line 665 of file GKlib/graph.c.

◆ 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.

Definition at line 19 of file GKlib/graph.c.

◆ 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.

Definition at line 340 of file GKlib/graph.c.

◆ 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.

Definition at line 391 of file GKlib/graph.c.

◆ 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.

Definition at line 572 of file GKlib/graph.c.

◆ 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.

Definition at line 48 of file GKlib/graph.c.

◆ 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.

Definition at line 63 of file GKlib/graph.c.

◆ gk_graph_Init()

void gk_graph_Init ( gk_graph_t * graph )

Initializes the graph.

Parameters

graph is the graph to be initialized.

Definition at line 36 of file GKlib/graph.c.

◆ 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.

Definition at line 85 of file GKlib/graph.c.

◆ 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

[IN]	graph is the graph to be re-ordered.
[IN]	perm is the new ordering of the graph's vertices
[IN]	iperm is the original ordering of the re-ordered graph's vertices

Returns: the newly created copy of the graph.

Note: Either perm or iperm can be NULL but not both.

Definition at line 460 of file GKlib/graph.c.

◆ 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

[IN]	graph is the graph structure.
[IN]	v is the root of the single-source shortest path computations.
[IN]	type indicates the criteria to use to measure the 'bestness' of a vertex.
[OUT]	sps[i] stores the length of the shortest path from v to vertex i. If no such path exists, then it is -1. Note that the returned array will be either an array of int32_t or an array of floats. The specific type is determined by the existance of non NULL iadjwgt and fadjwgt arrays. If both of these arrays exist, then priority is given to iadjwgt.

Note: The returned array should be freed with gk_free().

Definition at line 1084 of file GKlib/graph.c.

◆ 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.

Definition at line 277 of file GKlib/graph.c.

Macros

Functions

Detailed Description

Macro Definition Documentation

◆ OMPMINOPS

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