Approximate Breadth-First Search

Performs an approximate breadth-first search on the input graph and creates an approximate BFS tree by storing the the tree-level and tree-parent on each reachable vertex from the source. The tree-level discovered is at most k times the true tree-level.


size_t approximate_breadth_first_search(G g, Descriptor source, size_t k, double tau)
  • 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).
  • tau: A parameter that controls the amount of error allowed upon a visitation.


The number of iterations performed by the paradigm.

Usage Example

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

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

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

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

1 Adam Fidel, Francisco Coral, Colton Riedel, Nancy M. Amato, Lawrence Rauchwerger, "Fast Approximate Distance Queries in Unweighted Graphs using Bounded Asynchrony," In Wkshp. on Lang. and Comp. for Par. Comp. (LCPC), Sep 2016.

results matching ""

    No results matching ""