libs/ck-libs/metis/GKlib/graph.c File Reference

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

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 graph.c.

Function Documentation

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 graph.c.

References gk_graph_Init(), and gk_malloc().

Referenced by gk_graph_Dup(), gk_graph_ExtractPartition(), gk_graph_ExtractRows(), gk_graph_ExtractSubgraph(), gk_graph_Prune(), gk_graph_Read(), gk_graph_Reorder(), and gk_graph_Split().

Here is the call graph for this function:

Here is the caller graph for this function:

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 graph.c.

References gk_graph_t::nvtxs.

Referenced by gk_graph_Create().

Here is the caller graph for this function:

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 graph.c.

References gk_free(), and gk_graph_FreeContents().

Referenced by gk_graph_Prune(), and main().

Here is the call graph for this function:

Here is the caller graph for this function:

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 graph.c.

References gk_graph_t::adjncy, gk_graph_t::fadjwgt, gk_graph_t::fvsizes, gk_graph_t::fvwgts, gk_free(), gk_graph_t::iadjwgt, gk_graph_t::ivsizes, gk_graph_t::ivwgts, gk_graph_t::vlabels, and gk_graph_t::xadj.

Referenced by gk_graph_Free().

Here is the call graph for this function:

Here is the caller graph for this function:

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 graph.c.

References gk_graph_t::adjncy, gk_graph_t::fadjwgt, float, gk_graph_t::fvsizes, gk_graph_t::fvwgts, gk_errexit(), gk_fclose(), gk_fexists(), gk_fopen(), gk_free(), gk_getline(), gk_graph_Create(), gk_graph_t::iadjwgt, int, int32_t, gk_graph_t::ivsizes, gk_graph_t::ivwgts, PUP::l, ncon, gk_graph_t::nvtxs, and gk_graph_t::xadj.

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

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 graph.c.

References gk_graph_t::adjncy, gk_graph_t::fadjwgt, gk_graph_t::fvsizes, gk_graph_t::fvwgts, gk_errexit(), gk_fclose(), gk_fopen(), gk_graph_t::iadjwgt, gk_graph_t::ivsizes, gk_graph_t::ivwgts, gk_graph_t::nvtxs, xadj, and gk_graph_t::xadj.

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

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 graph.c.

References gk_graph_t::adjncy, gk_graph_t::fadjwgt, gk_graph_t::fvsizes, gk_graph_t::fvwgts, gk_graph_Create(), gk_graph_t::iadjwgt, gk_graph_t::ivsizes, gk_graph_t::ivwgts, gk_graph_t::nvtxs, gk_graph_t::vlabels, and gk_graph_t::xadj.

Here is the call graph for this function:

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 graph.c.

References gk_graph_t::adjncy, gk_graph_t::fadjwgt, gk_graph_t::fvsizes, gk_graph_t::fvwgts, gk_graph_Create(), gk_graph_t::iadjwgt, gk_graph_t::ivsizes, gk_graph_t::ivwgts, gk_graph_t::nvtxs, gk_graph_t::vlabels, and gk_graph_t::xadj.

Here is the call graph for this function:

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 graph.c.

References gk_graph_t::adjncy, adjncy, gk_graph_t::fadjwgt, gk_graph_t::fvsizes, gk_graph_t::fvwgts, gk_free(), gk_graph_Create(), gk_graph_t::iadjwgt, int32_t, gk_graph_t::ivsizes, gk_graph_t::ivwgts, gk_graph_t::nvtxs, PUP::u, gk_graph_t::vlabels, gk_graph_t::xadj, and xadj.

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

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 graph.c.

References gk_graph_t::adjncy, adjncy, gk_free(), int32_t, gk_graph_t::nvtxs, gk_graph_t::xadj, and xadj.

Here is the call graph for this function:

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 graph.c.

References gk_graph_t::adjncy, adjncy, gk_free(), int32_t, gk_graph_t::nvtxs, gk_graph_t::xadj, and xadj.

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

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 graph.c.

References gk_graph_t::adjncy, adjncy, degrees, gk_errexit(), gk_free(), gk_i32pq_t, int32_t, gk_graph_t::nvtxs, Ck::IO::open(), perm, PUP::u, gk_graph_t::xadj, and xadj.

Here is the call graph for this function:

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 graph.c.

References gk_graph_t::adjncy, adjncy, degrees, gk_errexit(), gk_free(), gk_i32pq_t, int32_t, level, gk_graph_t::nvtxs, perm, PUP::u, gk_graph_t::xadj, and xadj.

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

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 graph.c.

References gk_graph_t::adjncy, adjncy, adjwgt, gk_graph_t::fadjwgt, gk_fpq_t, gk_free(), gk_i32pq_t, gk_graph_t::iadjwgt, int32_t, gk_graph_t::nvtxs, PUP::u, gk_graph_t::xadj, and xadj.

Here is the call graph for this function:

void gk_graph_SortAdjacencies ( gk_graph_t * graph )

Sorts the adjacency lists in increasing vertex order

Parameters:

graph

the graph itself,

Definition at line 1196 of file graph.c.

References gk_errexit(), gk_free(), gk_ikvsorti(), n, and nn.

Here is the call graph for this function:

gk_graph_t* gk_graph_ExtractRows	(	gk_graph_t *	graph,
		int	nrows,
		int *	rind
	)

Returns a subgraphrix containing a certain set of rows.

Parameters:

	graph	is the original graphrix.
	nrows	is the number of rows to extract.
	rind	is the set of row numbers to extract.

Returns:: the row structure of the newly created subgraphrix.

Definition at line 1274 of file graph.c.

References gk_graph_Create().

Here is the call graph for this function:

gk_graph_t* gk_graph_ExtractPartition	(	gk_graph_t *	graph,
		int *	part,
		int	pid
	)

Returns a subgraphrix corresponding to a specified partitioning of rows.

Parameters:

	graph	is the original graphrix.
	part	is the partitioning vector of the rows.
	pid	is the partition ID that will be extracted.

Returns:: the row structure of the newly created subgraphrix.

Definition at line 1313 of file graph.c.

References gk_graph_Create().

Here is the call graph for this function:

gk_graph_t** gk_graph_Split	(	gk_graph_t *	graph,
		int *	color
	)

Splits the graphrix into multiple sub-graphrices based on the provided color array.

Parameters:

	graph	is the original graphrix.
	color	is an array of size equal to the number of non-zeros in the graphrix (row-wise structure). The graphrix is split into as many parts as the number of colors. For meaningfull results, the colors should be numbered consecutively starting from 0.

Returns:: an array of graphrices for each supplied color number.

Definition at line 1360 of file graph.c.

References gk_graph_Create(), and gk_malloc().

Here is the call graph for this function:

gk_graph_t* gk_graph_Prune	(	gk_graph_t *	graph,
		int	what,
		int	minf,
		int	maxf
	)

Prunes certain rows/columns of the graphrix. The prunning takes place by analyzing the row structure of the graphrix. The prunning takes place by removing rows/columns but it does not affect the numbering of the remaining rows/columns.

Parameters:

	graph	the graphrix to be prunned,
	what	indicates if the rows (GK_CSR_ROW) or the columns (GK_CSR_COL) of the graphrix will be prunned,
	minf	is the minimum number of rows (columns) that a column (row) must be present in order to be kept,
	maxf	is the maximum number of rows (columns) that a column (row) must be present at in order to be kept.

Returns:: the prunned graphrix consisting only of its row-based structure. The input graphrix is not modified.

Definition at line 1428 of file graph.c.

References gk_errexit(), gk_free(), gk_graph_Create(), and gk_graph_Free().

Here is the call graph for this function:

void gk_graph_Normalize	(	gk_graph_t *	graph,
		int	what,
		int	norm
	)

Normalizes the rows/columns of the graphrix to be unit length.

Parameters:

	graph	the graphrix itself,
	what	indicates what will be normalized and is obtained by specifying GK_CSR_ROW, GK_CSR_COL, GK_CSR_ROW\|GK_CSR_COL.
	norm	indicates what norm is to normalize to, 1: 1-norm, 2: 2-norm

Definition at line 1511 of file graph.c.

References n.


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)
void	gk_graph_SortAdjacencies (gk_graph_t *graph)
gk_graph_t *	gk_graph_ExtractRows (gk_graph_t graph, int nrows, int rind)
gk_graph_t *	gk_graph_ExtractPartition (gk_graph_t graph, int part, int pid)
gk_graph_t **	gk_graph_Split (gk_graph_t graph, int color)
gk_graph_t *	gk_graph_Prune (gk_graph_t *graph, int what, int minf, int maxf)
void	gk_graph_Normalize (gk_graph_t *graph, int what, int norm)

libs/ck-libs/metis/GKlib/graph.c File Reference

Functions

Detailed Description

Function Documentation