ADR 0010: Batch and graph semantics#

  • Status: Proposed (draft, M1a); accepted with the 0.1 API freeze (M3)

  • Date: 2026-09-27

  • Deciders: S M Shovan (lead maintainer)

Context#

The originals interpret a batch of edge changes in different ways:

  • MOSP-OpenMP / MOSP-CUDA applyChangeBatch() (and the file-based updateGraphCSR()): rows are unsorted; deletions come first and each removes the FIRST remaining (u,v) of row u; insertions follow in file order, an insertion of an existing (u,v) overwrites the weights of the first remaining match (so the last insertion of a pair wins), otherwise the edge is appended to row u; parallel edges and self-loops in the input are kept; surviving edges keep their order. applyChangeBatch() also classifies every insertion per objective as a weight increase (the first (u,v) of row u after the batch against the first before it), which the SOSP update treats like a deletion. updateGraphCSR() writes sorted rows and collapses parallel edges; it agrees with applyChangeBatch() only as an edge set on simple graphs.

  • CycleEnumeration-GPU prepare_batch() keeps sorted rows of a simple graph and normalizes a batch as a set (duplicates removed, no-ops dropped, insert/delete pairs cancelled).

  • LabelPropagation-CUDA applies vertex batches (Ins \ Del, Del ∩ V_t) to slotted rows.

Byte parity with MOSP’s CSR and with CycleEnum’s CSR is only possible if one container can do both row orders and both multigraph rules, and if every result on a graph agrees on how a batch is read.

Decision#

  1. The semantics belong to the graph, not to the batch or the algorithm: graph_properties::semantics (a batch_semantics) is fixed when the graph is created, so all results maintained on one graph see the same net change. edge_batch / edge_batch_view only carry the requested operations, in order.

  2. batch_semantics has the switches of PLAN Section 5.2: on_existing_insert (upsert, error, ignore), on_missing_delete (ignore, error), on_self_loop (keep, drop, error), deletions_first, allow_vertex_growth. The default-constructed value equals batch_semantics::upsert_last_wins(), MOSP’s applyChangeBatch(): upsert, ignore missing deletions, keep self-loops, deletions first, vertex growth.

  3. graph_properties adds row_order (sorted, append) and multi_edges (forbid, allow). The general default is a sorted simple graph (the least surprising for new users). graph_properties::mosp_compatible() = append + allow + upsert_last_wins reproduces MOSP’s CSR byte for byte, edge order and parallel edges included.

  4. Construction (from_edges, from_csr) follows the same rules: rows are grouped by source in input order; sorted sorts rows stably; forbid merges duplicate (u,v) (first position, last weights); self-loops follow on_self_loop. An undirected graph stores both directions, and every batch edge of an undirected graph changes both.

  5. Application on the compact layout is MOSP’s applyChangeBatch() ported straight (a new CSR per batch), with the switches around the unchanged core. It returns an apply_summary (public) and, for the algorithms, a detail::apply_delta with the effective insertions and deletions and the per-(insertion, objective) weight-increase flags (one byte each, lifting MOSP’s K <= 32 limit).

  6. Deferred: the set() preset and cycle_enum_compatible() (M2, with cycle_count), and net_effect() with vertex batches (0.3, with label_propagation). Vertex operations in a batch throw not_supported_error until then. Every algorithm will accept every preset, because Step 0 reduces a batch to its net structural change.

Consequences#

  • MOSP parity of the updated CSR is a byte comparison (the graph/io fixture tests compare the updated CSR, its transposition and the weight-increase flags with the pinned original on 27 cases). CycleEnum parity will use cycle_enum_compatible().

  • Distances and parents of sssp are canonical, so they do not depend on the row order; only the CSR files do.

  • The struct defaults in the PLAN sketch had on_self_loop = drop; that would have made batch_semantics{} differ from upsert_last_wins() and from MOSP. The default is keep (recorded in the M1a retrospective). Presets that need drop (for example set()) set it.

  • graph_properties::num_weights is used only by constructors without input data (with_capacity, 0.3); from_edges / from_csr take the number of weight columns from their input and store it there.

  • Legacy batch files (added after the M1a review). io::read_legacy_batch() is stricter than MOSP’s readChangeBatch() by default: extra integers on an insertion line (after u v w1 .. wK) or a deletion line (after u v), and a deletion line with a single integer, are io_errors, because a silently ignored token usually means a wrong K or a corrupt file. PLAN Section 8.3 requires the MOSP compatibility path to keep MOSP’s input-rejection semantics, so legacy_batch_options::mosp_lenient restores MOSP’s decisions (extras read and ignored, one-integer deletion lines skipped, ranges checked only on the kept values) and dyng-compat-mosp sets it; a cross-check against bin/mosp on hand-made files gives the same accept/reject decision and the same trees. In both modes a token must be a whole decimal integer; MOSP splits a glued token such as 5-6 into 5 and -6, dynG rejects it (the only remaining difference, for malformed files only).

Amendment (M2a, 2026-09-27): set semantics and the unweighted graph#

Decision 6 deferred set() and cycle_enum_compatible() to M2. They land with the CycleEnum graph pieces of M2a:

  1. batch_semantics gains a switch as_sets (appended, as PLAN Section 5.1 requires for aggregates). With it, Step 0 is CycleEnumeration-GPU@0a976ad’s prepare_batch(): each list is sorted by (source, destination) and deduplicated, self-loops follow on_self_loop, deletions of absent edges and insertions of present edges are no-ops that leave the lists, and the normalized batch is merged into the sorted rows by a port of its apply_batch() (a new CSR per batch, the untouched rows copied in parallel blocks, the offsets shifted by the degree changes of the touched rows; the bytes are those of the original’s sequential loop for every thread count). batch_semantics::set() = as_sets + ignore + ignore + drop + deletions first + vertex growth; graph_properties::cycle_enum_compatible() = sorted + forbid + set() + no weight columns. The algorithms receive the normalized batch as detail::apply_delta (sorted lists; the position of a change in its list is its ownership id in cycle_count).

  2. A delete-then-reinsert pair is kept, not cancelled. The PLAN sketch describes set() as “dedup, drop no-ops, cancel pairs”, and Decision 1’s context above said the same. The original’s prepare_batch() keeps an edge that the batch both deletes and inserts in both lists (the delete phase removes its cycles, the insert phase adds them back), and M2’s parity criterion is “identical normalized batches”. dynG therefore keeps the pair; apply_summary::cancelled_pairs counts such pairs (their structural effects cancel), and deleted_edges / inserted_edges count both halves. Removing the pairs would give the same histograms but not the original’s normalized batch, and no generated batch contains such a pair, so there is no performance cost.

  3. Under as_sets the other switches keep their meaning where they can: on_missing_delete and on_existing_insert = error throw on the no-ops, on_self_loop = keep keeps self-loops as ordinary set members, allow_vertex_growth = false rejects new vertices. Three combinations throw not_supported_error: on_existing_insert = upsert (a weight overwrite of an existing edge is not a structural change and would be invisible in the normalized batch; delete and re-insert the edge instead), deletions_first = false, and rows that are not row_order::sorted + multi_edges::forbid (the merge needs sorted rows of a simple graph). With weights, a new edge takes the weights of the first insertion of its pair in batch order (the first one is the insertion; the later ones are ignored duplicates).

  4. unweighted. graph<V, E, unweighted> is instantiated for (int32, int32) and (int32, int64) (PLAN Section 4.4.3); the graph has no weight columns, edge_batch<V, unweighted> defaults to num_weights = 0 and has insert_edge(u, v), and constructors reject weight columns for it. The tag compares equal to itself (so containers of it compare), and is_unweighted_v<W> names it. graph::from_edges() takes an edge list that is already sorted by (source, destination) without repeats, as io::read_edge_list() returns it, as the CSR in one pass.

  5. batch_semantics::net_effect() (DynLP vertex batches) stays deferred to 0.3 with the vertex operations.