DrTimothyAldenDavis
commented
1 year ago We have some spanning tree methods in LAGraph (see https://github.com/GraphBLAS/LAGraph, and in particular, the experimental/algorithms folder). Those methods don't explicitly deal with incremental changes to a graph, however.
There are 2 ways to handle dynamic graphs when using graphblas (at least):
(1) SuiteSparse:GraphBLAS itself has a limited dynamic feature, so you can let graphblas handle a graph as a single adjacency matrix, and modify it directly. I can handle lots of updates and then batch them together to do all at once. However, if you add or delete a single edge, and then recompute some graph algorithm, it's nearly certain that I will have to rebuild the whole graph.
(2) you can add/delete edges in different matrices. Redis uses this technique, with a primary matrix, and matrix of graph deletions, and a matrix of graph additions. The work of MIT Lincoln Lab uses a similar technique, with a sequence of matrices, all hypersparse. Changing a matrix with a small number of entries is fast in GraphBLAS.
Does the current scope of graphblas cover the dynamic connectivity problem? Normally when solving the dynamic connectivity problem, we construct a spanning tree (with non-tree edges) and check if two nodes share the same root. Addition and deletion of edges would normally change only a small part of the structure (either removing some non-tree edges or promoting some non-tree edges to tree edges). I am wondering if graphblas is suitable for this type of question, and if yes how it should be implemented. Thanks!