Breadth-first Search

Performs a breadth-first search on the input graph and creates a BFS tree by storing the the tree-level and tree-parent on each reachable vertex from the source.


size_t breadth_first_search(G g, Descriptor source, size_t k)
  • g: The graph_view over the input graph.
  • source: The descriptor of the source vertex for this traversal.
  • k: The maximum amount of asynchrony allowed in each phase. 0 <= k <= inf. k == 0 implies level-sync BFS. k >= D implies fully asynchronous (D is diameter of graph).


The number of iterations performed by the paradigm.

Usage Example

auto graph = stapl::load_edge_list<stapl::properties::bfs_property>(argv[1]);

std::size_t iters = stapl::breadth_first_search(graph, 0, 10);

std::size_t hops = graph[10].property().distance();

std::cout << "vertex 10 is " << hops << " hops away from vertex 0";

results matching ""

    No results matching ""