Various routines with dealing with sparse graphs. More...
#include <GKlib.h>
Go to the source code of this file.
Macros | |
| #define | OMPMINOPS 50000 |
Detailed Description
Various routines with dealing with sparse graphs.
- Version
$Id: graph.c 13328 2012-12-31 14:57:40Z karypis $
Definition in file GKlib/graph.c.
Macro Definition Documentation
| #define OMPMINOPS 50000 |
Definition at line 12 of file GKlib/graph.c.
Function Documentation
| 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.
| 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.
| 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_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_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_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.
| 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.
| 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.
| 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.
| 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_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_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.
| 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.
| 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.