Rounded nonincreasing distance oracle and exact report batches
DefinitionDecrAlmostLinearSSSP_Decremental_Supplement_OracleFix an initially empty incremental graph and a real parameter . At every completed insertion prefix , an external oracle supplies . Nonsource estimates are infinite exactly at unreachable vertices; every finite one is a nonnegative integral power of , and
Its next batch is precisely the set of nonsource vertices with a strict decrease:
The batch is represented in any duplicate-free order, and includes every newly reachable vertex. Only that batch's identifiers and new finite scalar estimates are delivered to the reduction. The initialization batch is empty. The hierarchy height is .
This is the exact external interface assumed by Lemma 5.1, independent of how the oracle is implemented. It is not a premise of Theorem 1.2. Valid graph inputs give finite positive edge weights, so a reported strict decrease is finite and converting its value to a real input scalar loses no value.
import Definitions.Def_DecrAlmostLinearSSSP_Decremental_Supplement_Execution
set_option autoImplicit false
open scoped ENNReal NNReal
namespace DecrAlmostLinearSSSP.Decremental.Supplement
/-- Completed-state oracle estimates and one duplicate-free batch after each insertion.
There is no assumed implementation or running-time bound in this interface. -/
structure OracleTrace (i : Instance) where
estimate : ℕ → Fin i.n → ℝ≥0∞
reports : ℕ → List (Fin i.n)
def OracleTrace.Valid {i : Instance} (o : OracleTrace i) (es : List (Fin i.k)) : Prop :=
o.reports 0 = [] ∧
(∀ t, t ≤ es.length → o.estimate t i.source = 0 ∧
∀ v, v ≠ i.source →
(o.estimate t v = ⊤ ↔ ¬ i.reachable (es.take t) v) ∧
(o.estimate t v ≠ ⊤ → ∃ k : ℕ,
o.estimate t v = ENNReal.ofReal ((1 + i.accuracy) ^ k)) ∧
i.dist (es.take t) v ≤ o.estimate t v ∧
o.estimate t v ≤ ENNReal.ofReal ((1 + i.accuracy) ^ 2) * i.dist (es.take t) v) ∧
(∀ t, t < es.length → ∀ v, o.estimate (t + 1) v ≤ o.estimate t v) ∧
(∀ t, t < es.length → (o.reports (t + 1)).Nodup ∧
∀ v, v ∈ o.reports (t + 1) ↔ v ≠ i.source ∧ o.estimate (t + 1) v < o.estimate t v)
noncomputable def OracleTrace.batches {i : Instance} (o : OracleTrace i)
(t : ℕ) : List (Report i) :=
(o.reports t).map (fun v => (v, (o.estimate t v).toReal))
noncomputable def height (m : ℕ) : ℕ := ⌈logarithm2 (m + 1)⌉₊
end DecrAlmostLinearSSSP.Decremental.Supplement