Dynamic shortest paths on MOSP files (C++)#

In this tutorial you build and run examples/cpp/sssp_update.cpp. It reads a graph and a change batch in the text formats of the original research code (MOSP-OpenMP), computes a shortest-path tree, updates it with the batch, and writes the result in MOSP’s own output format, so you can compare it byte for byte with the original’s output. It takes about ten minutes and needs no GPU.

1. Build#

From a clone with the development environment active (Install):

cmake --preset dev
cmake --build --preset dev --target dyng_example_sssp_update

2. The input#

The test data has tiny cases in MOSP’s formats (File formats). testCase0 is a graph with five vertices and one weight per edge, stored as three files with the prefix graphCsr (RowPtr, ColInd, Values), plus a batch: insert.txt holds 0 2 2 (insert the edge 0 -> 2 with weight 2, or change its weight if it exists) and delete.txt holds 3 4 (delete the edge 3 -> 4).

3. Read the graph and compute the tree#

The example picks the backend from its last argument and reads the CSR files into a graph with MOSP’s batch semantics (parallel edges and self-loops kept, append row order; ADR 0010):

  const std::string backend = argc > 5 ? argv[5] : "sequential";
  if (backend != "sequential" && backend != "openmp" && backend != "cuda") {
    std::cerr << "sssp_update: unknown backend '" << backend << "' (sequential, openmp, cuda)\n";
    return 2;
  }
  if (backend == "cuda" && !dyng::backend_available(dyng::backend::cuda)) {
    std::cerr << "sssp_update: no CUDA backend or no visible device\n";
    return 77;
  }
  dyng::resources res = backend == "openmp" ? dyng::resources::openmp()
                        : backend == "cuda" ? dyng::resources::cuda()
                                            : dyng::resources::sequential();

  const auto csr = dyng::io::read_csr_triplet<std::int32_t, std::int32_t, std::int32_t>(argv[1]);
  graph_t g = graph_t::from_csr(res, csr.view(), dyng::graph_properties::mosp_compatible());

  auto tree = dyng::sssp::compute(res, g, /*source=*/0);  // canonical tree (lowest-id ties)

compute() returns the canonical tree: every vertex’s parent is its lowest-id in-neighbour on a shortest path, on every backend.

4. Apply the batch#

  dyng::io::legacy_batch_options options;
  options.num_weights = g.num_weights();
  options.num_vertices = g.num_vertices();
  const auto batch =
      dyng::io::read_legacy_batch<std::int32_t, std::int32_t>(argv[2], argv[3], options);

  dyng::profiler prof;
  res.attach_profiler(&prof);
  const dyng::sssp::stats st = dyng::sssp::update(res, g, batch.view(), tree);
  res.attach_profiler(nullptr);

update() does the whole update: it normalizes the batch, applies it to g exactly once, finds the vertices whose shortest paths may have changed, and repairs only those (The update model). The attached profiler records one stage per step of that template (sssp.prepare, sssp.commit, sssp.identify_affected, sssp.seed, sssp.loop, sssp.finalize).

5. Write the result and compare#

  const std::string out = argv[4];
  dyng::io::write_distances(out + "/distancesUpdated.txt", host_distances);
  dyng::io::write_parents(out + "/SSSPTreeUpdated.txt", host_parents);
  prof.write_csv(std::cout);  // sssp.update, sssp.prepare, sssp.commit, sssp.loop, ...

Run it on both CPU backends and compare with the output of the original tool, which is stored next to the case:

case=cpp/tests/data/mosp_graph_io/testCase0
expected=cpp/tests/data/mosp_sssp/testCase0/updated/obj0
for backend in sequential openmp; do
  mkdir -p out/$backend
  build/dev/examples/cpp/sssp_update $case/graphCsr $case/insert.txt $case/delete.txt out/$backend $backend
  cmp out/$backend/SSSPTreeUpdated.txt $expected/SSSPTreeUpdated.txt
  cmp out/$backend/distancesUpdated.txt $expected/distancesUpdated.txt
done

cmp prints nothing: the files are identical. CTest runs the same comparisons, both files on every CPU backend (ctest --preset dev -R example.sssp_update).

With a GPU and a CUDA build (the dev-cuda preset, Install), the same program runs on the cuda backend: the graph and the tree then live in device memory, the fused kernel of the original MOSP-CUDA code runs the update, and the output files are the same bytes:

cmake --build --preset dev-cuda --target dyng_example_sssp_update
mkdir -p out/cuda
build/dev-cuda/examples/cpp/sssp_update $case/graphCsr $case/insert.txt $case/delete.txt out/cuda cuda
cmp out/cuda/SSSPTreeUpdated.txt $expected/SSSPTreeUpdated.txt

What you learned#

  • One resources object selects the backend for every call.

  • compute() gives the static result; update() applies a batch and repairs the result, and the result must match the graph’s version.

  • The profiler’s stage names follow the update template, the same for every algorithm.

Next: Choose a backend, Profile an update, and the sssp: dynamic single-source shortest paths page for the details of the algorithm.