Approximate Diameter

Calculates an approximation for the diameter of an unweighted graph, using a chain of BFS traversals.


size_t pseudo_diameter(G g, size_t k)
  • g: The graph_view over the input graph.
  • k: The maximum amount of asynchrony allowed in each phase.


An approximation of the true diameter.

Usage Example

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

auto diam = stapl::pseudo_diameter(graph, 0);

std::cout << "The diameter is roughly " << diam;

results matching ""

    No results matching ""