Multi-Source Shortest Path

Performs a multi-source shortest path query on the input graph, storing the shortest path distances and parents on each reachable vertex for each traversal. All vertices will be initialized with their distances as infinity (MAX) and their active states as empty, except the source-vertex for each traversal, which will have its distance set to zero (0) and active state set to true for that traversal. Parents of each vertex will be initialized to the vertex's descriptor.

Parameters

size_t msssp(G g, std::vector<Descriptor> sources, size_t k)
  • g: The graph_view over the input graph.
  • sources: The descriptors of the source vertices for this traversal.
  • k: The maximum amount of asynchrony allowed in each phase. 0 <= k <= inf. k == 0 implies level-sync SSSP. k >= D implies fully asynchronous (D is diameter of graph).

Returns

The number of iterations performed by the paradigm.

Usage Example

auto graph =
  stapl::load_weighted_edge_list<stapl::properties::mssp_property, int>(argv[1]);

std::vector<std::size_t> sources{{20,21,22}};

std::size_t iters = stapl::mssp(graph, sources, 10);

int dist = graph[0].property().distance(sources.front());

std::cout << "vertex 0 is distance " << dist
          << " away from vertex " << sources.front();

results matching ""

    No results matching ""