Run a breadth first search on a directed graph starting at a specified source vertex and return a bfs-tree. Duplicate input edges are allowed. The input is in adjacency array format with an ordering among the outgoing edges. If the graph is not connected then only the tree over the vertices reachable from the source should be returned.
The input is a graph in the in the adjacency graph format. The graph can be directed but the search will always start at vertex 0 as the source and only search what is reachable from there. The output is a also a graph in the adjacency list format with each vertex only including edges to its children in the BFS-tree.
randLocalGraph -j -d 3 -m <5*n> <n> <filename>
rMatGraph -j -a .5 -b .1 -m <5*n> <n> <filename>
gridGraph -j -d 3 <n> <filename>
This project has been funded by the following sources:
Intel Labs Academic Research Office for the Parallel Algorithms for Non-Numeric Computing Program,
National Science Foundation, and
IBM Research.