pygraphblas
pygraphblas copied to clipboard
Graphegon
graph algorithms
theres a rich body of graph algorithsm eg topological sort... if you think it makes sense ill implement and submit a pr :)
@mynameisvinn I like the idea but I have a question. To determine whether the topological sort is possible, you need to check that the graph is a DAG. I have not yet seen a GraphBLAS algorithm that does this, barring some early-stage research on linear algebraic DFS:
D.G. Spampinato et al.: Linear Algebraic Depth-First Search, ARRAYS@PLDI 2019
(Section 5.1 is titled "Linear Algebraic Topological Sort")
Do you have a linear algebraic algorithm for checking acyclicity before performing the topological sort?
cc @michelp
The Spampinato et al paper is a great place to start, I took a stab and implementing one of the methods shown but had to put it down for other work a couple months ago. @mynameisvinn if you want to take stab at it and have any questions you can ping me on IRC Freenode as michelp.
@szarnyasg i think so. a graph G with V vertices is a dag if its adjacency matrix A is nilpontent, ie A^V = 0. so, we can test if graph G is acyclic by evaluating whether A^V = 0.
i put together a toy example here.
@mynameisvinn this seems very expensive to check - especially for graphs that turn out to be cyclic. But I guess we can make this check optional if the user guarantees that the matrix they passed represents a DAG.
Maybe the check can happen inside the toposort algorithm? E.g. Kahn's algorithm performs such a check.
agreed, it will be expensive (in worst case, do k matrix multiplies, where k equals numbers of nodes).
@szarnyasg another way to check for acyclicity is to compute eigenvalues of the adjacency matrix. an acyclic graph has a nilpotent adjacency matrix; the eigenvalues for a nilpotent adjacency matrix are zeros.
so, we could compute eigenvalues for a given graph if we want to check for acyclicity. runtime isnt great - think it's o(n^3) - but it's a possible solution.
what do you think?
@mynameisvinn sorry for dropping the ball on this. It could work but SuiteSparse:GraphBLAS, unlike SuiteSparse, has no built-in support for computing eigenvalues. So you'd have to roll out your own QR/GS implementation which might be a lot of work.