The Graph Object

The fundamental object in LAGraph is the LAGraph_Graph.

typedef struct LAGraph_Graph_struct *LAGraph_Graph
struct LAGraph_Graph_struct

LAGraph_Graph: a representation of a graph.

The LAGraph_Graph G contains a GrB_Matrix G->A as its primary component. For graphs represented with adjacency matrices, A(i,j) denotes the edge (i,j). Unlike GrB_* objects in GraphBLAS, the LAGraph_Graph data structure is not opaque. User applications have full access to its contents.

An LAGraph_Graph G contains two kinds of components:

  1. Primary components of the graph, which fully define the graph.

  2. Cached properties of the graph, which can be recreated any time.

Primary Components

GrB_Matrix A

the adjacency matrix of the graph

LAGraph_Kind kind

the kind of graph

Cached Properties

All of these components may be deleted or set to ‘unknown’ at any time. For example, if AT is NULL, then the transpose of A has not been computed. A scalar cached property of type LAGraph_Boolean would be set to LAGRAPH_UNKNOWN to denote that its value is unknown.

If present, the cached properties must be valid and accurate. If the graph changes, these cached properties can either be recomputed or deleted to denote the fact that they are unknown. This choice is up to individual LAGraph methods and utilities.

LAGraph methods can set non-scalar cached properties only if they are constructing the graph. They cannot modify them or create them if the graph is declared as a read-only object in the parameter list of the method.

GrB_Matrix AT

AT = A’, the transpose of A, with the same type.

GrB_Vector out_degree

a GrB_INT64 vector of length m, if A is m-by-n. where out_degree(i) is the number of entries in A(i,:). If out_degree is sparse and the entry out_degree(i) is not present, then it is assumed to be zero.

GrB_Vector in_degree

a GrB_INT64 vector of length n, if A is m-by-n. where in_degree(j) is the number of entries in A(:,j). If in_degree is sparse and the entry in_degree(j) is not present, then it is assumed to be zero. If A is known to have a symmetric structure, the convention is that the degree is held in G->out_degree, and in G->in_degree is left as NULL.

LAGraph_Boolean is_symmetric_structure

For an undirected graph, this cached property will always be implicitly true and can be ignored. The matrix A for a directed weighted graph will typically be unsymmetric, but might have a symmetric structure. In that case, this scalar cached property can be set to true. By default, this cached property is set to LAGRAPH_UNKNOWN.

int64_t nself_edges

number of entries on the diagonal of A, or LAGRAPH_UNKNOWN if unknown. For the adjacency matrix of a directed or undirected graph, this is the number of self-edges in the graph.

GrB_Scalar emin

minimum edge weight: value, lower bound, or unknown

LAGraph_State emin_state

  • VALUE: emin is equal to the smallest entry, min(G->A)

  • BOUND: emin <= min(G->A)

  • UNKNOWN: emin is unknown

GrB_Scalar emax

maximum edge weight: value, upper bound, or unknown

LAGraph_State emax_state

  • VALUE: emax is equal to the largest entry, max(G->A)

  • BOUND: emax >= max(G->A)

  • UNKNOWN: emax is unknown

enum LAGraph_Boolean

LAGraph_Boolean: a boolean value (true or false) or unknown (-1).

Values:

enumerator LAGraph_FALSE

the Boolean value is known to be false.

enumerator LAGraph_TRUE

the Boolean value is known to be true.

enumerator LAGraph_BOOLEAN_UNKNOWN

Boolean value is unknown.

enum LAGraph_State

LAGraph_State describes the status of a cached property of a graph. If the cached property is computed in floating-point arithmetic, it may have been computed with roundoff error, but it may still be declared as “value” if the roundoff error is expected to be small, or if the cached property was computed as carefully as possible (to within reasonable roundoff error). The “bound” state indicates that the cached property is an upper or lower bound, depending on the particular cached property. If computed in floating-point arithmetic, an “upper bound” cached property may be actually slightly lower than the actual upper bound, because of floating-point roundoff.

Values:

enumerator LAGraph_VALUE

cached property is a known value.

enumerator LAGraph_BOUND

cached property is a bound. The bound is upper or lower, depending on the particular cached property.

enumerator LAGraph_STATE_UNKNOWN

the property is unknown.

enum LAGraph_Kind

LAGraph_Kind: the kind of a graph. Currently, only two types of graphs are supported: undirected graphs and directed graphs. Edge weights are assumed to be present. Unweighted graphs can be represented by setting all entries present in the sparsity structure to the same value, typically 1. Additional types of graphs will be added in the future.

Values:

enumerator LAGraph_ADJACENCY_UNDIRECTED

undirected graph. G->A is square and symmetric; both upper and lower triangular parts are present. A(i,j) is the edge (i,j). Results are undefined if A is unsymmetric.

enumerator LAGraph_ADJACENCY_DIRECTED

G->A is square; A(i,j) is the edge (i,j).

directed graph.

enumerator LAGraph_KIND_UNKNOWN

unknown kind of graph (-1).

Basic Graph Functions

int LAGraph_New(LAGraph_Graph *G, GrB_Matrix *A, LAGraph_Kind kind, char *msg)

LAGraph_New: creates a new graph G. The cached properties G->AT, G->out_degree, and G->in_degree are set to NULL, and scalar cached properties are set to LAGRAPH_UNKNOWN.

Parameters:

  • G – [out] handle to the newly created graph, as &G.

  • A – [inout] adjacency matrix. A is moved into G as G->A, and A itself is set to NULL to denote that is now a part of G. That is, { G->A = A ; A = NULL ; } is performed. When G is deleted, G->A is freed. If A is NULL, the graph is invalid until G->A is set.

  • kind – [in] the kind of graph to create. This may be LAGRAPH_UNKNOWN, which must then be revised later before the graph can be used.

  • msg – [inout] any error messages.

Return values:

  • GrB_SUCCESS – if successful.

  • GrB_NULL_POINTER – if G is null.

Returns:

any GraphBLAS errors that may have been encountered.

int LAGraph_Delete(LAGraph_Graph *G, char *msg)

LAGraph_Delete: frees a graph G. The adjacency matrix G->A and the cached properties G->AT, G->out_degree, and G->in_degree are all freed.

Parameters:

  • G – [inout] handle to the graph to be free. *G is NULL on output. To keep G->A while deleting the graph G, use: { A = G->A ; G->A = NULL ; LAGraph_Delete (&G, msg) ; }

  • msg – [inout] any error messages.

Return values:

GrB_SUCCESS – if successful.

Returns:

any GraphBLAS errors that may have been encountered.

int LAGraph_DeleteCached(LAGraph_Graph G, char *msg)

LAGraph_DeleteCached: frees all cached properies of a graph G. The graph is still valid. This method should be used if G->A changes, since such changes will normally invalidate G->AT, G->out_degree, and/or G->in_degree.

Parameters:

  • G – [inout] handle to the graph to modified. The graph G remains valid on output, but with all cached properties freed. G may be NULL, in which case nothing is done.

  • msg – [inout] any error messages.

Return values:

GrB_SUCCESS – if successful.

Returns:

any GraphBLAS errors that may have been encountered.

int LAGraph_Cached_AT(LAGraph_Graph G, char *msg)

LAGraph_Cached_AT: constructs G->AT, the transpose of G->A. This matrix is required by some of the algorithms. Basic algorithms may construct G->AT if they require it. The matrix G->AT is then available for subsequent use. If G->A changes, G->AT should be freed and recomputed. If G->AT already exists, it is left unchanged (even if it is not equal to the transpose of G->A). As a result, if G->A changes, G->AT should be explictly freed.

Parameters:

  • G – [inout] graph for which G->AT is computed.

  • msg – [inout] any error messages.

Return values:

  • GrB_SUCCESS – if successful.

  • GrB_NULL_POINTER – if G is NULL.

  • LAGRAPH_CACHE_NOT_NEEDED – if G->kind is LAGraph_ADJACENCY_UNDIRECTED.

  • LAGRAPH_INVALID_GRAPH – if G is invalid (G->A missing, or G->kind not a recognized kind).

Returns:

any GraphBLAS errors that may have been encountered.

int LAGraph_Cached_IsSymmetricStructure(LAGraph_Graph G, char *msg)

LAGraph_Cached_IsSymmetricStructure: determines if the sparsity structure of G->A is symmetric (ignoring its values). If G->kind denotes that the graph is undirected, this cached property is implicitly true (and not checked). Otherwise, this method determines if the structure of G->A for a directed graph G has a symmetric sparsity structure. No work is performed if the cached property is already known.

Parameters:

  • G – [inout] graph for which G->is_symmetric_structure is computed.

  • msg – [inout] any error messages.

Return values:

  • GrB_SUCCESS – if successful.

  • GrB_NULL_POINTER – if G is NULL.

  • LAGRAPH_INVALID_GRAPH – if G is invalid (G->A missing, or G->kind not a recognized kind).

Returns:

any GraphBLAS errors that may have been encountered.

int LAGraph_Cached_OutDegree(LAGraph_Graph G, char *msg)

LAGraph_Cached_OutDegree: computes G->out_degree. No work is performed if it already exists in G.

Parameters:

  • G – [inout] graph for which G->out_degree is computed.

  • msg – [inout] any error messages.

Return values:

  • GrB_SUCCESS – if successful.

  • GrB_NULL_POINTER – if G is NULL.

  • LAGRAPH_INVALID_GRAPH – if G is invalid (G->A missing, or G->kind not a recognized kind).

Returns:

any GraphBLAS errors that may have been encountered.

int LAGraph_Cached_InDegree(LAGraph_Graph G, char *msg)

LAGraph_Cached_InDegree computes G->in_degree. No work is performed if it already exists in G. If G is undirected, G->in_degree is never computed and remains NULL (the method returns LAGRAPH_CACHE_NOT_NEEDED). No work is performed if it is already exists in G.

Performance note: for SuiteSparse:GraphBLAS, if G->A is held by row (the default format), then computing G->in_degree is fastest if G->AT is known. If G->AT will be needed anyway, compute it first with LAGraph_Cached_AT, and then call LAGraph_Cached_Indegree. This is optional; if G->AT is not known, then G->in_degree is computed from G->A instead.

Parameters:

  • G – [inout] graph for which G->in_degree is computed.

  • msg – [inout] any error messages.

Return values:

  • GrB_SUCCESS – if successful.

  • GrB_NULL_POINTER – if G is NULL.

  • LAGRAPH_CACHE_NOT_NEEDED – if G->kind is LAGraph_ADJACENCY_UNDIRECTED.

  • LAGRAPH_INVALID_GRAPH – if G is invalid (G->A missing, or G->kind not a recognized kind).

Returns:

any GraphBLAS errors that may have been encountered.

int LAGraph_Cached_NSelfEdges(LAGraph_Graph G, char *msg)

LAGraph_Cached_NSelfEdges: computes G->nself_edges, the number of diagonal entries that appear in the G->A matrix. For an undirected or directed graph with an adjacency matrix G->A, these are the number of self-edges in G. No work is performed it is already computed.

Parameters:

  • G – [inout] graph for which G->nself_edges is computed.

  • msg – [inout] any error messages.

Return values:

  • GrB_SUCCESS – if successful.

  • GrB_NULL_POINTER – if G is NULL.

  • LAGRAPH_INVALID_GRAPH – if G is invalid (G->A missing, or G->kind not a recognized kind).

Returns:

any GraphBLAS errors that may have been encountered.

int LAGraph_Cached_EMin(LAGraph_Graph G, char *msg)

LAGraph_Cached_EMin: computes the G->emin, the smallest entry in G->A. Not computed if G->emin already exists.

Parameters:

  • G – [inout] graph for which G->emin is computed.

  • msg – [inout] any error messages.

Return values:

  • GrB_SUCCESS – if successful.

  • GrB_NOT_IMPLEMENTED – if G does not have a built-in real type: GrB_(BOOL, INT8, INT16, INT32, INT64, UINT8, UINT16, UINT32, UINT64, FP32, OR FP64).

  • GrB_NULL_POINTER – if G is NULL.

  • LAGRAPH_INVALID_GRAPH – if G is invalid (G->A missing, or G->kind not a recognized kind).

Returns:

any GraphBLAS errors that may have been encountered.

int LAGraph_Cached_EMax(LAGraph_Graph G, char *msg)

LAGraph_Cached_EMax: computes the G->emax, the largest entry in G->A. Not computed if G->emax already exists.

Parameters:

  • G – [inout] graph for which G->emax is computed.

  • msg – [inout] any error messages.

Return values:

  • GrB_SUCCESS – if successful.

  • GrB_NOT_IMPLEMENTED – if G does not have a built-in real type: GrB_(BOOL, INT8, INT16, INT32, INT64, UINT8, UINT16, UINT32, UINT64, FP32, OR FP64).

  • GrB_NULL_POINTER – if G is NULL.

  • LAGRAPH_INVALID_GRAPH – if G is invalid (G->A missing, or G->kind not a recognized kind).

Returns:

any GraphBLAS errors that may have been encountered.

int LAGraph_DeleteSelfEdges(LAGraph_Graph G, char *msg)

LAGraph_DeleteSelfEdges: removes any diagonal entries from G->A. Most cached properties are cleared or set to LAGRAPH_UNKNOWN. G->nself_edges is set to zero, and G->is_symmetric_structure is left unchanged.

Parameters:

  • G – [inout] graph for which G->A is modified.

  • msg – [inout] any error messages.

Return values:

  • GrB_SUCCESS – if successful.

  • GrB_NULL_POINTER – if G is NULL.

  • LAGRAPH_INVALID_GRAPH – if G is invalid (G->A missing, or G->kind not a recognized kind).

Returns:

any GraphBLAS errors that may have been encountered.

int LAGraph_CheckGraph(LAGraph_Graph G, char *msg)

LAGraph_CheckGraph: determines if a graph is valid. Only basic checks are performed on the cached properties, taking O(1) time.

Parameters:

  • G – [in] graph to check.

  • msg – [inout] any error messages.

Return values:

  • GrB_SUCCESS – if successful.

  • GrB_NULL_POINTER – if G is NULL.

  • LAGRAPH_INVALID_GRAPH – if G is invalid: G->A missing, G->kind not a recognized kind, G->AT present but has the wrong dimensions or its type does not match G->A, G->in_degree/out_degree present but with the wrong dimension or type (in/out_degree must be GrB_INT64).

Returns:

any GraphBLAS errors that may have been encountered.