Product Code Database
GraphBLAS () is an API specification that defines standard building blocks for graph algorithms in the language of linear algebra. GraphBLAS is built upon the notion that a sparse matrix can be used to represent graphs as either an adjacency matrix or an incidence matrix. The GraphBLAS specification describes how graph operations (e.g. traversing and transforming graphs) can be efficiently implemented via linear algebraic methods (e.g. matrix multiplication) over different .
The development of GraphBLAS and its various implementations is an ongoing community effort, including representatives from industry, academia, and government research labs.
The GraphBLAS specification (and the various libraries that implement it) provides data structures and Subroutine to compute these linear algebraic operations. In particular, GraphBLAS specifies sparse matrix objects which map well to graphs where vertices are likely connected to relatively few neighbors (i.e. the degree of a vertex is significantly smaller than the total number of vertices in the graph). The specification also allows for the use of different semirings to accomplish operations in a variety of mathematical contexts.
Originally motivated by the need for standardization in graph analytics, similar to its namesake BLAS, the GraphBLAS standard has also begun to interest people outside the graph community, including researchers in machine learning,9781538634721 ISBN 9781538634721 and bioinformatics. GraphBLAS implementations have also been used in high-performance graph database applications such as FalkorDB formerly Redis.
Each graph operation in GraphBLAS operates on a semiring, which is made up of the following elements:
Note that the zero element (i.e. the element that represents the absence of an edge in the graph) can also be reinterpreted. For example, the following algebras can be implemented in GraphBLAS:
| 0 |
| 0 |
| 0 |
| 0 |
All the examples above satisfy the following two conditions in their respective domains:
For instance, a user can specify the min-plus algebra over the domain of double-precision floating point numbers with GrB_Semiring_new(&min_plus_semiring, GrB_MIN_FP64, GrB_PLUS_FP64).
The GraphBLAS specification also prescribes that library implementations be Thread safety.
/*
* Given a boolean n x n adjacency matrix A and a source vertex s, performs a BFS traversal
* of the graph and sets v[i] to the level in which vertex i is visited (v[s] == 1).
* If i is not reachable from s, then v[i] = 0 does not have a stored element.
* Vector v should be uninitialized on input.
*/
GrB_Info BFS(GrB_Vector *v, GrB_Matrix A, GrB_Index s)
{
GrB_Index n;
GrB_Matrix_nrows(&n,A); // n = # of rows of A
GrB_Vector_new(v,GrB_INT32,n); // Vector
GrB_Vector q; // vertices visited in each level
GrB_Vector_new(&q, GrB_BOOL, n); // Vector
/*
* BFS traversal and label the vertices.
*/
int32_t level = 0; // level = depth in BFS traversal
GrB_Index nvals;
do {
++level; // next level (start with 1)
GrB_apply(*v, GrB_NULL, GrB_PLUS_INT32,
GrB_SECOND_INT32, q, level, GrB_NULL); // v[q] = level
GrB_vxm(q, *v, GrB_NULL, GrB_LOR_LAND_SEMIRING_BOOL,
q, A, GrB_DESC_RC); // q[!v] = q ||.&& A; finds all the
// unvisited successors from current q
GrB_Vector_nvals(&nvals, q);
} while (nvals); // if there is no successor in q, we are done.
GrB_free(&q); // q vector no longer needed
return GrB_SUCCESS;
}
|
|
