A first update in Python#

This program builds a four-vertex graph, computes shortest paths from vertex 0, and then applies a batch with dyng.sssp.update(), which changes the graph and brings the result up to date. It is examples/python/first_update.py, the Python twin of A first update in C++; the test suite runs it on both CPU backends and checks that it prints exactly this:

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

import sys

import dyng


def main(backend: str = "openmp") -> None:
    res = dyng.Resources(backend)  # "sequential" or "openmp" in the CPU wheel

    # Edges 0->1 (4), 0->2 (1), 2->1 (2), 1->3 (1): sources, destinations, weights.
    g = dyng.Graph.from_edges([0, 0, 2, 1], [1, 2, 1, 3], [4, 1, 2, 1], resources=res)
    tree = dyng.sssp.compute(g, source=0)  # the canonical tree: lowest-id ties

    batch = dyng.EdgeBatch(insert=([2], [3], [1]), delete=([2], [1]))  # +2->3 (1), -2->1
    st = dyng.sssp.update(g, batch, tree)  # applies the batch to g and repairs the tree

    print(f"invalidated {st.invalidated}, affected {st.affected}")
    print("distances", *tree.distances.tolist())
    print("parents", *tree.parents.tolist())  # distances 0 4 1 2, parents -1 0 0 2


if __name__ == "__main__":
    main(*sys.argv[1:2])

What happened:

  1. dyng.Resources("openmp") chose the backend (the CPU wheel has "sequential" and "openmp"; Backends and resources). The graph keeps its resources, so the calls below need no resources= argument.

  2. Graph.from_edges(src, dst, weights) built the graph. The id arrays are Python lists, so the vertex ids are int32 (an int64 NumPy array would give int64 ids: dtypes are never narrowed silently; Python API).

  3. dyng.sssp.compute() produced the static result, the canonical shortest-path tree: distances (0, 3, 1, 4), vertex 1 reached through vertex 2.

  4. dyng.sssp.update() applied the batch to g (its version went up by one) and repaired the tree: deleting the tree edge (2, 1) invalidated the subtree below vertex 1 ({1, 3}), and the insertion (2, 3) gave vertex 3 a shorter path. st holds the counters of this update.

  5. tree.distances and tree.parents are dyng.Array views of the result’s memory (no copy); tolist() and to_numpy() copy them. After the next update of tree these views raise StaleResultError: read the properties again (Results and versions).

Keeping several results on one graph current takes one call, which applies the batch once:

import dyng

g = dyng.Graph.from_edges([0, 0, 2, 1, 3], [1, 2, 1, 3, 0], [4, 1, 2, 1, 1])
tree = dyng.sssp.compute(g, source=0)
hist = dyng.cycle_count.compute(g, max_length=4)       # cycles of length 2..4 (weights ignored)
batch = dyng.EdgeBatch(insert=([2], [3], [1]), delete=([2], [1]))
st_tree, st_hist = dyng.update(g, batch, tree, hist)
print(tree.distances.tolist(), hist.counts.tolist(), st_hist.cycles_removed, st_hist.cycles_added)

[0, 4, 1, 2] [0, 0, 0, 2, 0] 1 1

dyng.sssp.update(g, batch, tree) alone would have left hist stale: its next use raises dyng.StaleResultError.

The same steps from the command line, on files in MOSP’s formats, are in Command-line interface (dyng sssp compute and dyng sssp update) and in the tutorial Dynamic shortest paths on MOSP files (C++). The next steps are the algorithm pages, sssp: dynamic single-source shortest paths, mosp: dynamic multi-objective shortest paths (several weights per edge: multi-objective shortest paths) and cycle_count: exact k-bounded directed simple-cycle histograms, which have longer Python and CLI examples; the tutorial algorithms dynamic_bfs: BFS levels under edge batches (tutorial) and triangle_delta: the triangle count under edge batches (tutorial) show how an algorithm is written.