C’est LAGraph

Writing graph algorithms based on GraphBLAS is like writing matrix algorithms in MATLAB; it's simple once you get the hang of it, but it's a big switch from conventional graph algorithms, where you deal with nodes, edges, and such.

Just like MATLAB for matrix computations, there is often an elegant "one-liner" that does just what you want ... but it can take some thought, and practice, to find it.

So what is really needed is a suite of example graph algorithms that rely on GraphBLAS, so you can see how it's done, and so you can use them as-is if they already solve your problem.  Or perhaps you can start with a graph algorithm and modify it or borrow its approach.

Enter LAGraph.   You can find the latest version here:  https://github.com/GraphBLAS/LAGraph .

It's very much a work in progress, and likely has a few bugs here and there.  There are lots of TODO's sprinkled throughout the code.  We took the decision to write this code in the open, rather than polish it and publish once it's "done".  This is because we invite others to take part in writing it, and we want others to see how different graph algorithms can be written, as soon as we can write them.

The algorithms in LAGraph are not as polished as they will be in a final distribution.  Their API will most likely change, and we will probably make them more fully featured.

Currently, the algorithms in LAGraph include:

  • Bellman-Ford, single-source shortest paths (with and without the tree)
  • connected components
  • a simple breadth-first-search
  • a direction-optimizing push/pull BFS (with and without the BFS tree)
  • K-truss
  • All-K-truss
  • Pagerank
  • Triangle counting

Plus lots of helpful utilities, such as:

  • check if two vectors or two matrices are equal
  • read/write a matrix in Matrix Market format
  • generate a random matrix
  • allocate and free commonly used operators, monoids, and semirings, used in several LAGraph algorithms.

Check it out.  C'est la vie des Graphes!  Et ensuite, pour le prochain blogue, un sonnet de sommets (ahh, Tim, arrêtes-toi les jeu des mots des arêtes!)

Leave a Reply

Your email address will not be published. Required fields are marked *