LAGraph Graph Algorithm

Abstract

In this thesis, I will discuss a multi-source breadth first search algorithm I wrote for LAGraph. It allows a user to get the BFS parent and level data of a graph for several source nodes at once instead of having to do each source individually. This is not only easier on the user, but because of the parallelization that the matrix representation allows it is also more efficient than looping through each of the nodes of interest. While this is valuable to a user in its own right, a multi-source breadth first search also opens the door to other algorithms. I highlight methods of estimating or directly obtaining diameter and discuss further algorithms that could be added in the future.