search

Graphegon / pygraphblas

GraphBLAS for Python
https://graphegon.github.io/pygraphblas/pygraphblas/index.html
Apache License 2.0
343 stars 27 forks source link

graph algorithms #51

Open mynameisvinn opened 4 years ago

mynameisvinn commented 4 years ago

theres a rich body of graph algorithsm eg topological sort... if you think it makes sense ill implement and submit a pr :)

szarnyasg commented 4 years ago

@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

michelp commented 4 years ago

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.

mynameisvinn commented 4 years ago

@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.

szarnyasg commented 4 years ago

@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.

mynameisvinn commented 4 years ago

agreed, it will be expensive (in worst case, do k matrix multiplies, where k equals numbers of nodes).

mynameisvinn commented 4 years ago

@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?

szarnyasg commented 4 years ago

@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.