GPU-Accelerated BFS
While taking Dr. Peir's Spring 2012 GPGPU course, one of the assignments was to write a GPU-accelerated breadth-first search code. In addition to testing the sample graphs, I tested my BFS code on some of the matrices in the UF Sparse Matrix Library, maintained by my advisor, Dr. Tim Davis.
Below is a selection of the graphs I used to test my GPU-accelerated BFS. I used graphviz to generate images of the graphs using a 3-dimensional multiscale spring modeling code. The colors in the graphs represent the BFS level (distance from the start node). Think of the BFS as an explosion that starts at a node and radiates along outgoing edges until all vertices in the connected component are visited. I use a linear gradient from red to blue so we can visualize the progress of the BFS.
