Algorithms

Algorithms come in two flavors: Basic and Advanced.

Basic

Basic algorithm are meant to be easy to use. A single basic algorithm may encompass many underlying Advanced algorithms, each with various parameters that may be controlled. For the Basic API, these parameters are determined automatically. Cached graph properties may be determined, and as a result, the graph G is both an input and an output of these methods, since they may be modified.

LAGraph Basic algorithms are named with the LAGraph_* prefix.

int LAGraph_TriangleCount(uint64_t *ntriangles, LAGraph_Graph G, char *msg)

LAGraph_TriangleCount: count the triangles in a graph. This is a Basic algorithm (G->nself_edges, G->out_degree, G->is_symmetric_structure are computed, if not present).

Parameters

ntriangles – [out] the number of triangles in G.
G – [inout] the graph, which must by undirected, or directed but with a symmetric structure. No self loops can be present.
msg – [inout] any error messages.

Returns

any GraphBLAS errors that may have been encountered.

Returns

GrB_SUCCESS – if successful.
GrB_NULL_POINTER – if G or ntriangles are NULL.
LAGRAPH_INVALID_GRAPH – if G is invalid ( LAGraph_CheckGraph failed).
LAGRAPH_NO_SELF_EDGES_ALLOWED – if G has any self-edges.
LAGRAPH_SYMMETRIC_STRUCTURE_REQUIRED – if G is directed with an unsymmetric G->A matrix.

Advanced

The Advanced algorithms require the caller to select the algorithm and choose any parameter settings. G is not modified, and so it is an input-only parameter to these methods. If an Advanced algorithm requires a cached graph property to be computed, it must be computed prior to calling the Advanced method.

Advanced algorithms are named with the LAGr_* prefix, to distinguish them from Basic algorithms.

int LAGr_SortByDegree(int64_t **P, const LAGraph_Graph G, bool byout, bool ascending, char *msg)

LAGr_SortByDegree sorts the nodes of a graph by their out or in degrees. The graph G->A itself is not changed. Refer to LAGr_TriangleCount for an example of how to permute G->A after calling this function. The output &P must be freed by LAGraph_Free. This method requires G->out_degree or G->in_degree to already be computed.

Parameters

P – [out] permutation of the integers 0..n-1.
G – [in] graph of n nodes.
byout – [in] if true, sort by out-degree, else sort by in-degree.
ascending – [in] if true, sort in ascending order, else descending.
msg – [inout] any error messages.

Returns

any GraphBLAS errors that may have been encountered.

Returns

GrB_NULL_POINTER – if P or G are NULL.
LAGRAPH_NOT_CACHED – if G->in_degree or G->out_degree is not computed (whichever one is required).
LAGRAPH_INVALID_GRAPH – if G is invalid ( LAGraph_CheckGraph failed).

int LAGr_SampleDegree(double *sample_mean, double *sample_median, const LAGraph_Graph G, bool byout, int64_t nsamples, uint64_t seed, char *msg)

LAGr_SampleDegree computes an estimate of the median and mean of the out or in degree, by randomly sampling the G->out_degree or G->in_degree vector. This method requires G->out_degree or G->in_degree to already be computed.

Parameters

sample_mean – [out] sampled mean of the degree.
sample_median – [out] sampled median of the degree.
G – [in] graph to sample.
byout – [in] if true, sample out-degree, else sample in-degree.
nsamples – [in] number of samples to take.
seed – [in] random number seed.
msg – [inout] any error messages.

Returns

any GraphBLAS errors that may have been encountered.

Returns

GrB_NULL_POINTER – if sample_mean, sample_median, or G are NULL.
LAGRAPH_NOT_CACHED – if G->in_degree or G->out_degree is not computed (whichever one is required).
LAGRAPH_INVALID_GRAPH – if G is invalid ( LAGraph_CheckGraph failed).

int LAGr_BreadthFirstSearch(GrB_Vector *level, GrB_Vector *parent, const LAGraph_Graph G, GrB_Index src, char *msg)

LAGr_BreadthFirstSearch: breadth-first search of a graph, computing the breadth-first-search tree and/or the level of the nodes encountered. This is an Advanced algorithm. G->AT and G->out_degree are required to use the fastest push/pull method when using SuiteSparse:GraphBLAS. If these cached properties are not present, or if a vanilla GraphBLAS library is being used, then a push-only method is used (which can be slower). G is not modified; that is, G->AT and G->out_degree are not computed if not already cached.

Parameters

level – [out] If non-NULL on input, on successful return, it contains the levels of each node reached. The src node is assigned level 0. If a node i is not reached, level(i) is not present. The level vector is not computed if NULL.
parent – [out] If non-NULL on input, on successful return, it contains parent node IDs for each node reached, where parent(i) is the node ID of the parent of node i. The src node will have itself as its parent. If a node i is not reached, parent(i) is not present. The parent vector is not computed if NULL.
G – [in] The graph, directed or undirected.
src – [in] The index of the src node (0-based)
msg – [inout] any error messages.

Returns

any GraphBLAS errors that may have been encountered.

Returns

GrB_SUCCESS – if successful.
GrB_INVALID_INDEX – if src is invalid.
GrB_NULL_POINTER – if both level and parent are NULL, or if G is NULL.
LAGRAPH_INVALID_GRAPH – Graph is invalid ( LAGraph_CheckGraph failed).

int LAGr_ConnectedComponents(GrB_Vector *component, const LAGraph_Graph G, char *msg)

LAGr_ConnectedComponents: connected components of an undirected graph. This is an Advanced algorithm (G->is_symmetric_structure must be known).

Parameters

component – [out] component(i)=s if node i is in the component whose representative node is s. If node i has no edges, it is placed in its own component, and thus the component vector is always dense.
G – [in] input graph to find the components for. The graph must be undirected, or G->is_symmetric_structure must be true.
msg – [inout] any error messages.

Returns

any GraphBLAS errors that may have been encountered.

Returns

GrB_SUCCESS – if successful.
GrB_NULL_POINTER – if G or component are NULL.
LAGRAPH_INVALID_GRAPH – Graph is invalid ( LAGraph_CheckGraph failed).
LAGRAPH_SYMMETRIC_STRUCTURE_REQUIRED – if G is directed with an unsymmetric G->A matrix.

int LAGr_SingleSourceShortestPath(GrB_Vector *path_length, const LAGraph_Graph G, GrB_Index src, GrB_Scalar Delta, char *msg)

LAGr_SingleSourceShortestPath: single-source shortest paths. This is an Advanced algorithm (G->emin is required for best performance). The graph G must have an adjacency matrix of type GrB_INT32, GrB_INT64, GrB_UINT32, GrB_UINT64, GrB_FP32, or GrB_FP64. If G->A has any other type, GrB_NOT_IMPLEMENTED is returned.

Parameters

path_length – [out] path_length (i) is the length of the shortest path from the source node to node i. The path_length vector is dense. If node (i) is not reachable from the src node, then path_length (i) is set to INFINITY for GrB_FP32 and FP32, or the maximum integer for GrB_INT32, INT64, UINT32, or UINT64.
G – [in] input graph.
src – [in] source node.
Delta – [in] for delta stepping.
msg – [inout] any error messages.

Returns

any GraphBLAS errors that may have been encountered.

Returns

GrB_SUCCESS – if successful.
GrB_NULL_POINTER – if G or path_length are NULL.
GrB_INVALID_INDEX – if src is invalid.
GrB_EMPTY_OBJECT – if Delta does not contain a value.
GrB_NOT_IMPLEMENTED – if the type is not supported.
LAGRAPH_INVALID_GRAPH – Graph is invalid ( LAGraph_CheckGraph failed).

int LAGr_Betweenness(GrB_Vector *centrality, const LAGraph_Graph G, const GrB_Index *sources, int32_t ns, char *msg)

LAGr_Betweenness: betweeness centrality metric. This methods computes an approximation of the betweeness-centrality metric of all nodes in the graph. Only a few given source nodes are used for the approximation. This is an Advanced algorithm (G->AT is required).

Parameters

centrality – [out] centrality(i) is the metric for node i.
G – [in] input graph.
sources – [in] source vertices to compute shortest paths, size ns
ns – [in] number of source vertices.
msg – [inout] any error messages.

Returns

any GraphBLAS errors that may have been encountered.

Returns

GrB_SUCCESS – if successful.
GrB_NULL_POINTER – if G, centrality, and/our sources are NULL.
GrB_INVALID_INDEX – if any source node is invalid.
LAGRAPH_INVALID_GRAPH – Graph is invalid ( LAGraph_CheckGraph failed).
LAGRAPH_NOT_CACHED – if G->AT is required but not present.

int LAGr_PageRank(GrB_Vector *centrality, int *iters, const LAGraph_Graph G, float damping, float tol, int itermax, char *msg)

LAGr_PageRank: computes the standard PageRank of a directed graph G. Sinks (nodes with no out-going edges) are properly handled. This method should be used for production, not for the GAP benchmark. This is an Advanced algorithm (G->AT and G->out_degree are required).

Parameters

centrality – [out] centrality(i) is the PageRank of node i.
iters – [out] number of iterations taken.
G – [in] input graph.
damping – [in] damping factor (typically 0.85).
tol – [in] stopping tolerance (typically 1e-4).
itermax – [in] maximum number of iterations (typically 100).
msg – [inout] any error messages.

Returns

any GraphBLAS errors that may have been encountered.

Returns

GrB_SUCCESS – if successful.
GrB_NULL_POINTER – if G, centrality, and/our iters are NULL.
LAGRAPH_NOT_CACHED – if G->AT is required but not present, or if G->out_degree is not present.
LAGRAPH_INVALID_GRAPH – Graph is invalid ( LAGraph_CheckGraph failed).

int LAGr_TriangleCount(uint64_t *ntriangles, const LAGraph_Graph G, LAGr_TriangleCount_Method *method, LAGr_TriangleCount_Presort *presort, char *msg)

LAGr_TriangleCount: count the triangles in a graph (advanced API).

Parameters

ntriangles – [out] the number of triangles in G.
G – [in] The graph, which must be undirected or have G->is_symmetric_structure true, with no self loops. G->nself_edges, G->out_degree, and G->is_symmetric_structure are required.
method – [inout] specifies which algorithm to use, and returns the method chosen. If NULL, the AutoMethod is used, and the method is not reported. Also see the LAGr_TriangleCount_Method enum description.
presort – [inout] controls the presort of the graph, and returns the presort chosen. If NULL, the AutoSort is used, and the presort method is not reported. Also see the description of the LAGr_TriangleCount_Presort enum.
msg – [inout] any error messages.

Returns

any GraphBLAS errors that may have been encountered.

Returns

GrB_SUCCESS – if successful.
GrB_NULL_POINTER – if G or ntriangles are NULL.
LAGRAPH_INVALID_GRAPH – Graph is invalid ( LAGraph_CheckGraph failed).
LAGRAPH_NO_SELF_EDGES_ALLOWED – if G has any self-edges, or if G->nself_edges is not computed.
LAGRAPH_SYMMETRIC_STRUCTURE_REQUIRED – if G is directed with an unsymmetric G->A matrix.
LAGRAPH_NOT_CACHED – if G->out_degree is not present in G.
GrB_INVALID_VALUE – method or presort are invalid.

enum LAGr_TriangleCount_Method

LAGr_TriangleCount_Method: an enum to select the method used to count the number of triangles.

Values:

enumerator LAGr_TriangleCount_AutoMethod: auto selection of method

enumerator LAGr_TriangleCount_Burkhardt: sum (sum ((A^2) .* A)) / 6

enumerator LAGr_TriangleCount_Cohen: sum (sum ((L * U) .* A)) / 2

enumerator LAGr_TriangleCount_Sandia_LL: sum (sum ((L * L) .* L))

enumerator LAGr_TriangleCount_Sandia_UU: sum (sum ((U * U) .* U))

enumerator LAGr_TriangleCount_Sandia_LUT: sum (sum ((L * U’) .* L))

enumerator LAGr_TriangleCount_Sandia_ULT: sum (sum ((U * L’) .* U))

enum LAGr_TriangleCount_Presort

LAGr_TriangleCount_Presort: an enum to control if/how the matrix is sorted prior to counting triangles.

Values:

enumerator LAGr_TriangleCount_NoSort: no sort

enumerator LAGr_TriangleCount_Ascending: sort by degree, ascending.

enumerator LAGr_TriangleCount_Descending: sort by degree, descending.

enumerator LAGr_TriangleCount_AutoSort: auto selection of presort: No presort is done for the Burkhardt or Cohen methods, and no sort is done for the Sandia_* methods if the sampled mean out-degree is <= 4 * the sample median out-degree. Otherwise: sort in ascending order for Sandia_LL and Sandia_LUT, descending ordering for Sandia_UU and Sandia_ULT. On output, presort is modified to reflect the sorting method used (NoSort, Ascending, or Descending).