Problem Based Benchmark Suite

Breadth First Search (BFS):

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.

Input and Output File Formats

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.

Default Input Distributions

Each distribution should be run for n=10,000,000. The weights used for average time are given in parentheses.
last modified 15:18, 05 Jun 2012

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.