A first update in C++

This program builds a four-vertex graph, computes shortest paths from vertex 0, and then applies a batch with sssp::update(), which changes the graph and brings the result up to date. It is examples/cpp/first_update.cpp: the dev build compiles it, and CTest runs it on every backend (the CPU backends, and cuda in a CUDA build with a GPU) and checks that it prints exactly this:

invalidated 2, affected 2
distances 0 4 1 2
parents -1 0 0 2

#include <dyng/dyng.hpp>

#include <cstdint>
#include <cstdio>
#include <string>
#include <vector>

int main(int argc, char** argv) {
  const std::string backend = argc > 1 ? argv[1] : "openmp";
  if (backend == "cuda" && !dyng::backend_available(dyng::backend::cuda)) {
    std::printf("no CUDA device visible\n");
    return 77;
  }
  auto res = backend == "sequential" ? dyng::resources::sequential()
             : backend == "cuda"     ? dyng::resources::cuda()
                                     : dyng::resources::openmp();

  dyng::edge_list<std::int32_t, std::int32_t> edges;
  edges.num_vertices = 4;
  edges.num_weights = 1;
  edges.add_edge(0, 1, {4});
  edges.add_edge(0, 2, {1});
  edges.add_edge(2, 1, {2});
  edges.add_edge(1, 3, {1});
  auto g = dyng::graph<>::from_edges(res, edges.view());  // int32 ids, offsets and weights

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

  dyng::edge_batch<std::int32_t, std::int32_t> batch;
  batch.delete_edge(2, 1);
  batch.insert_edge(2, 3, {1});
  dyng::sssp::stats st = dyng::sssp::update(res, g, batch.view(), tree);  // applies the batch

  std::printf("invalidated %lld, affected %lld\n", static_cast<long long>(st.invalidated),
              static_cast<long long>(st.affected));
  // to_vector() copies a result to the host (from device memory on cuda).
  const std::vector<std::int64_t> distances = dyng::to_vector(res, tree.distances());
  const std::vector<std::int32_t> parents = dyng::to_vector(res, tree.parents());
  std::printf("distances");
  for (auto d : distances) std::printf(" %lld", static_cast<long long>(d));
  std::printf("\nparents");
  for (auto p : parents) std::printf(" %lld", static_cast<long long>(p));
  std::printf("\n");  // distances 0 4 1 2, parents -1 0 0 2
}

What happened:

1. resources chose the backend (Explanation: Backends and resources). On cuda the graph and the tree live in device memory, so the program reads the result with to_vector(), which copies it to the host (on the CPU backends it is a plain copy).

2. compute() produced the static result, the canonical shortest-path tree.

3. update() applied the batch to g (its version went up by one) and repaired the tree: the deletion of the tree edge (2, 1) invalidated the subtree below vertex 1, and the insertion (2, 3) gave vertex 3 a shorter path. The result now matches g again, so a later update() accepts it (Results and versions).

Build it against an installed dynG with find_package(dyng) (Install). The next step is the tutorial Dynamic shortest paths on MOSP files (C++), which runs the same steps on the file formats of the original research code.