Incremental directed graph inputs and legal insertion prefixes
DefinitionDecrAlmostLinearSSSP_Decremental_Supplement_InputLet be a finite nonempty vertex set, let be the source, and give each original directed edge its own identifier in . Its tail, head and real weight are fixed. The initial graph is a duplicate-free list ; a legal insertion list has no repeated identifier and is disjoint from . At that prefix the active graph and its distance are
Validity means , , , and for every identifier. A separate integrality predicate requires integer edge weights only when used; the numerical upper bound remains real. Source membership supplies nonemptiness. Parallel edges, loops, edges entering the source, arbitrary initial reachability and empty insertion lists remain admissible.
These incremental wrappers reuse the published general directed graph, walk, extended distance and reachability definitions. They do not use any deletion-specific legality or live-edge convention. Extended nonnegative distances give infinity exactly when no walk exists for valid finite weights. The full future graph is specification data; the execution protocol exposes only initially active edges and then the current inserted edge.
import Definitions.Def_DecrAlmostLinearSSSP_Decremental_Graph set_option autoImplicit false open scoped ENNReal NNReal namespace DecrAlmostLinearSSSP.Decremental.Supplement /-- Specification of an incremental instance. The graph includes potential future identifiers, but the initialization tape below exposes only `initial`. Parallel edges and loops are allowed. Real weights are needed by the black-box Lemma 5.1. -/ structure Instance where n : ℕ k : ℕ graph : Digraph n k source : Fin n weight : Fin k → ℝ initial : List (Fin k) size : ℕ W : ℝ accuracy : ℝ def Instance.Valid (i : Instance) : Prop := i.n ≤ i.size ∧ i.k ≤ i.size ∧ i.initial.Nodup ∧ 1 ≤ i.W ∧ 0 < i.accuracy ∧ i.accuracy ≤ 1 ∧ ∀ e, 1 ≤ i.weight e ∧ i.weight e ≤ i.W /-- Integrality concerns edge lengths only; the numerical upper bound W may be real. -/ def Instance.Integral (i : Instance) : Prop := ∀ e, ∃ w : ℕ, i.weight e = (w : ℝ) def Instance.Legal (i : Instance) (es : List (Fin i.k)) : Prop := (i.initial ++ es).Nodup def Instance.active (i : Instance) (es : List (Fin i.k)) : Finset (Fin i.k) := (i.initial ++ es).toFinset noncomputable def Instance.dist (i : Instance) (es : List (Fin i.k)) (v : Fin i.n) : ℝ≥0∞ := distance i.graph (i.active es) (fun e => ENNReal.ofReal (i.weight e)) i.source v def Instance.reachable (i : Instance) (es : List (Fin i.k)) (v : Fin i.n) : Prop := Reachable i.graph (i.active es) i.source v end DecrAlmostLinearSSSP.Decremental.Supplement