Macros | Functions
GKlib/graph.c File Reference

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

#include <GKlib.h>
Include dependency graph for GKlib/graph.c:

Go to the source code of this file.

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_tgk_graph_Create ()
 
gk_graph_tgk_graph_Dup (gk_graph_t *graph)
 
gk_graph_tgk_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_tgk_graph_Read (char *filename, int format, int isfewgts, int isfvwgts, int isfvsizes)
 
gk_graph_tgk_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

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

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

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
graphis 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
graphis the original graph.
vstartis the starting vertex.
nvtxsis 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
graphis the graph structure
cptris the ptr structure of the CSR representation of the components. The length of this vector must be graph->nvtxs+1.
cindis 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
graphis 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
graphis 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
graphis 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
filenameis the file that stores the data.
formatis the graph format. The supported values are: GK_GRAPH_FMT_METIS.
isfewgtsis 1 if the edge-weights should be read as floats
isfvwgtsis 1 if the vertex-weights should be read as floats
isfvsizesis 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

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

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
graphis the graph to be written,
filenameis the name of the output file.
formatis one of GK_GRAPH_FMT_METIS specifying the format of the output file.

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



gtsam
Author(s):
autogenerated on Tue Jul 4 2023 02:40:49