Exact Dijkstra execution and small-accuracy work bound
ProvedDecrAlmostLinearSSSP.Decremental.Certificates.exact_laws_8This collection gives the universally quantified contracts for exact dijkstra execution and small-accuracy work bound. All graph identifiers, queue keys, payloads, registers and addresses are finite natural indices; capacities and arithmetic registers use the scalar RAM types defined in the accompanying interface.
The native Dijkstra loop terminates and computes exact stored source distances, including infinity for unreachable vertices. Initialization and deletion calls satisfy the representation invariant after every legal prefix. With trie height , recomputation costs a constant times . The full legal stream has charged work bounded by . Consequently, for accuracy at most , the fixed program satisfies the mission's maintenance predicate with positive subpolynomial overhead and nine-instruction stored-array queries.
Each listed contract holds for every state and parameter tuple satisfying its explicit representation and domain hypotheses. Together they assert
where are the component queue, execution, representation, frame and work contracts described above. The conjunction preserves their individual quantifiers; it adds no successful-execution or correctness assumption to the external graph input.
These contracts form a reusable verification interface for the charged exact-recomputation branch of the general-domain reduction. Formalization Note The conjunction is balanced to expose component contracts through short projections and keep verification jobs within the service's compilation limit.
import Definitions.Def_DecrAlmostLinearSSSP_RAMFoundation set_option autoImplicit false set_option maxRecDepth 10000 set_option maxHeartbeats 2000000 open scoped ENNReal NNReal attribute [local instance] Classical.propDecidable
theorem DecrAlmostLinearSSSP.Decremental.Certificates.exact_laws_8 : (((((((∀ (s : DecrAlmostLinearSSSP.Decremental.Structured.Data),
DecrAlmostLinearSSSP.Decremental.Structured.Eval
(DecrAlmostLinearSSSP.Decremental.Structured.sequence
(@List.map.{0, 0} DecrAlmostLinearSSSP.Decremental.Structured.Atom DecrAlmostLinearSSSP.Decremental.Structured.Cmd
DecrAlmostLinearSSSP.Decremental.Structured.Cmd.atom
DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.poppedAtoms))
s (@OfNat.ofNat.{0} Nat (nat_lit 4) (instOfNatNat (nat_lit 4)))
(DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.poppedData s)) ∧ (∀
j ∉
@Insert.insert.{0, 0} Nat (Finset.{0} Nat) (@Finset.instInsert.{0} Nat instDecidableEqNat)
(@OfNat.ofNat.{0} Nat (nat_lit 304) (instOfNatNat (nat_lit 304)))
(@Insert.insert.{0, 0} Nat (Finset.{0} Nat) (@Finset.instInsert.{0} Nat instDecidableEqNat)
(@OfNat.ofNat.{0} Nat (nat_lit 306) (instOfNatNat (nat_lit 306)))
(@Insert.insert.{0, 0} Nat (Finset.{0} Nat) (@Finset.instInsert.{0} Nat instDecidableEqNat)
(@OfNat.ofNat.{0} Nat (nat_lit 318) (instOfNatNat (nat_lit 318)))
(@Singleton.singleton.{0, 0} Nat (Finset.{0} Nat) (@Finset.instSingleton.{0} Nat)
(@OfNat.ofNat.{0} Nat (nat_lit 320) (instOfNatNat (nat_lit 320)))))),
DecrAlmostLinearSSSP.Decremental.Structured.NatFrame
(DecrAlmostLinearSSSP.Decremental.Structured.sequence
(@List.map.{0, 0} DecrAlmostLinearSSSP.Decremental.Structured.Atom DecrAlmostLinearSSSP.Decremental.Structured.Cmd
DecrAlmostLinearSSSP.Decremental.Structured.Cmd.atom
DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.poppedAtoms))
j)) ∧ ((∀ (j : Nat),
DecrAlmostLinearSSSP.Decremental.Structured.RealFrame
(DecrAlmostLinearSSSP.Decremental.Structured.sequence
(@List.map.{0, 0} DecrAlmostLinearSSSP.Decremental.Structured.Atom DecrAlmostLinearSSSP.Decremental.Structured.Cmd
DecrAlmostLinearSSSP.Decremental.Structured.Cmd.atom
DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.poppedAtoms))
j) ∧ (∀ {i : DecrAlmostLinearSSSP.Decremental.Input} {deleted : List.{0} (Fin i.k)} {tentative : Fin i.n → Option.{0} Nat}
{settled : Finset.{0} (Fin i.n)}
{tree :
DecrAlmostLinearSSSP.Decremental.Exact.LocatedTrie (DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.heapHeight i)}
{queue : Multiset.{0} (Prod.{0, 0} Nat (Fin i.n))} {s : DecrAlmostLinearSSSP.Decremental.Structured.Data},
DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.Memory i deleted tentative settled tree queue s →
∀ (key : Nat) (v : Fin i.n),
@Eq.{1} Nat (s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 260) (instOfNatNat (nat_lit 260)))) key →
@Eq.{1} Nat (s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 262) (instOfNatNat (nat_lit 262)))) (@Fin.val i.n v) →
And
(DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.Memory i deleted tentative settled tree queue
(DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.poppedData s))
(And
(@Eq.{1} Nat
((DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.poppedData s).natReg
(@OfNat.ofNat.{0} Nat (nat_lit 304) (instOfNatNat (nat_lit 304))))
key)
(And
(@Eq.{1} Nat
((DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.poppedData s).natReg
(@OfNat.ofNat.{0} Nat (nat_lit 306) (instOfNatNat (nat_lit 306))))
(@Fin.val i.n v))
(@Eq.{1} Nat
((DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.poppedData s).natReg
(@OfNat.ofNat.{0} Nat (nat_lit 320) (instOfNatNat (nat_lit 320))))
(@ite.{1} Nat
(@Membership.mem.{0, 0} (Fin i.n) (Finset.{0} (Fin i.n))
(@SetLike.instMembership.{0, 0} (Finset.{0} (Fin i.n)) (Fin i.n)
(@Finset.instSetLike.{0} (Fin i.n)))
settled v)
(@Finset.decidableMem.{0} (Fin i.n) (instDecidableEqFin i.n) v settled)
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))
(@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))))))))) ∧ (((∀ {n k : Nat} (g : DecrAlmostLinearSSSP.Decremental.Digraph n k),
@Eq.{1} Nat
(@DecrAlmostLinearSSSP.Decremental.Exact.remainingDegree n k g
(@EmptyCollection.emptyCollection.{0} (Finset.{0} (Fin n)) (@Finset.instEmptyCollection.{0} (Fin n))))
k) ∧ (∀ {n k : Nat} (g : DecrAlmostLinearSSSP.Decremental.Digraph n k) (settled : Finset.{0} (Fin n)),
∀ v ∉ settled,
@Eq.{1} Nat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@DecrAlmostLinearSSSP.Decremental.Exact.remainingDegree n k g
(@Insert.insert.{0, 0} (Fin n) (Finset.{0} (Fin n)) (@Finset.instInsert.{0} (Fin n) (instDecidableEqFin n)) v
settled))
(@List.length.{0} (Fin k) (@DecrAlmostLinearSSSP.Decremental.Exact.adjacency n k g k v)))
(@DecrAlmostLinearSSSP.Decremental.Exact.remainingDegree n k g settled))) ∧ ((∀ {n k : Nat} (g : DecrAlmostLinearSSSP.Decremental.Digraph n k) (settled : Finset.{0} (Fin n)) (key : Nat) (v : Fin n)
(queue : Multiset.{0} (Prod.{0, 0} Nat (Fin n))),
@Eq.{1} Nat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@DecrAlmostLinearSSSP.Decremental.Exact.queuePotential n k g settled queue)
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(@DecrAlmostLinearSSSP.Decremental.Exact.queuePotential n k g settled
(@Multiset.cons.{0} (Prod.{0, 0} Nat (Fin n)) (@Prod.mk.{0, 0} Nat (Fin n) key v) queue))) ∧ (∀ {n k : Nat} (g : DecrAlmostLinearSSSP.Decremental.Digraph n k) (settled : Finset.{0} (Fin n)) (key : Nat) (v : Fin n)
(queue next : Multiset.{0} (Prod.{0, 0} Nat (Fin n))),
v ∉ settled →
@LE.le.{0} Nat instLENat (@Multiset.card.{0} (Prod.{0, 0} Nat (Fin n)) next)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@Multiset.card.{0} (Prod.{0, 0} Nat (Fin n)) queue)
(@List.length.{0} (Fin k) (@DecrAlmostLinearSSSP.Decremental.Exact.adjacency n k g k v))) →
@LE.le.{0} Nat instLENat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@DecrAlmostLinearSSSP.Decremental.Exact.queuePotential n k g
(@Insert.insert.{0, 0} (Fin n) (Finset.{0} (Fin n))
(@Finset.instInsert.{0} (Fin n) (instDecidableEqFin n)) v settled)
next)
(@List.length.{0} (Fin k) (@DecrAlmostLinearSSSP.Decremental.Exact.adjacency n k g k v)))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(@DecrAlmostLinearSSSP.Decremental.Exact.queuePotential n k g settled
(@Multiset.cons.{0} (Prod.{0, 0} Nat (Fin n)) (@Prod.mk.{0, 0} Nat (Fin n) key v) queue)))))) ∧ ((((∀ {n k : Nat} (g : DecrAlmostLinearSSSP.Decremental.Digraph n k) (source : Fin n),
@Eq.{1} Nat
(@DecrAlmostLinearSSSP.Decremental.Exact.queuePotential n k g
(@EmptyCollection.emptyCollection.{0} (Finset.{0} (Fin n)) (@Finset.instEmptyCollection.{0} (Fin n)))
(@Singleton.singleton.{0, 0} (Prod.{0, 0} Nat (Fin n)) (Multiset.{0} (Prod.{0, 0} Nat (Fin n)))
(@Multiset.instSingleton.{0} (Prod.{0, 0} Nat (Fin n)))
(@Prod.mk.{0, 0} Nat (Fin n) (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))) source)))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) k)
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))) ∧ (∀ {G : Type} (test : DecrAlmostLinearSSSP.Decremental.Structured.Test)
(body : DecrAlmostLinearSSSP.Decremental.Structured.Cmd)
(invariant : G → DecrAlmostLinearSSSP.Decremental.Structured.Data → Prop) (potential : G → Nat) (charge : Nat),
(∀ (g : G) (s : DecrAlmostLinearSSSP.Decremental.Structured.Data),
invariant g s →
test.holds s →
∃ g' t cost,
And (DecrAlmostLinearSSSP.Decremental.Structured.Eval body s cost t)
(And (invariant g' t)
(And (@LT.lt.{0} Nat instLTNat (potential g') (potential g))
(@LE.le.{0} Nat instLENat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) cost
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))))
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) charge
(@HSub.hSub.{0, 0, 0} Nat Nat Nat (@instHSub.{0} Nat instSubNat) (potential g)
(potential g'))))))) →
∀ (g : G) (s : DecrAlmostLinearSSSP.Decremental.Structured.Data),
invariant g s →
∃ g' t cost,
And
(DecrAlmostLinearSSSP.Decremental.Structured.Eval
(DecrAlmostLinearSSSP.Decremental.Structured.Cmd.loop test body) s cost t)
(And (invariant g' t)
(And (Not (test.holds t))
(@LE.le.{0} Nat instLENat cost
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) charge (potential g))
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))))))))) ∧ ((∀ {s u v w t : DecrAlmostLinearSSSP.Decremental.Structured.Data} {cp cs cq : Nat},
DecrAlmostLinearSSSP.Decremental.Structured.Eval DecrAlmostLinearSSSP.Decremental.Exact.TriePop.code s cp u →
DecrAlmostLinearSSSP.Decremental.Structured.Eval
(DecrAlmostLinearSSSP.Decremental.Structured.sequence
(@List.map.{0, 0} DecrAlmostLinearSSSP.Decremental.Structured.Atom
DecrAlmostLinearSSSP.Decremental.Structured.Cmd DecrAlmostLinearSSSP.Decremental.Structured.Cmd.atom
DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.poppedAtoms))
u (@OfNat.ofNat.{0} Nat (nat_lit 4) (instOfNatNat (nat_lit 4))) v →
DecrAlmostLinearSSSP.Decremental.Structured.Eval
(DecrAlmostLinearSSSP.Decremental.Structured.Cmd.branch
(DecrAlmostLinearSSSP.Decremental.Structured.Test.natLess
(@OfNat.ofNat.{0} Nat (nat_lit 320) (instOfNatNat (nat_lit 320)))
(@OfNat.ofNat.{0} Nat (nat_lit 26) (instOfNatNat (nat_lit 26))))
DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.scan DecrAlmostLinearSSSP.Decremental.Structured.Cmd.skip)
v cs w →
DecrAlmostLinearSSSP.Decremental.Structured.Eval DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.queueCount w cq
t →
DecrAlmostLinearSSSP.Decremental.Structured.Eval DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.body s
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) cp
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@OfNat.ofNat.{0} Nat (nat_lit 4) (instOfNatNat (nat_lit 4)))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) cs cq)))
t) ∧ (∀ {i : DecrAlmostLinearSSSP.Decremental.Input} {deleted : List.{0} (Fin i.k)},
i.Valid →
∀ (q : DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.State i deleted)
(s : DecrAlmostLinearSSSP.Decremental.Structured.Data),
@DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.State.memory i deleted q s →
(DecrAlmostLinearSSSP.Decremental.Structured.Test.natLess
(@OfNat.ofNat.{0} Nat (nat_lit 56) (instOfNatNat (nat_lit 56)))
(@OfNat.ofNat.{0} Nat (nat_lit 348) (instOfNatNat (nat_lit 348)))).holds
s →
∃ next t cost,
And
(DecrAlmostLinearSSSP.Decremental.Structured.Eval DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.body s
cost t)
(And (@DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.State.memory i deleted next t)
(And
(@LT.lt.{0} Nat instLTNat
(@DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.State.potential i deleted next)
(@DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.State.potential i deleted q))
(@LE.le.{0} Nat instLENat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) cost
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))))
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 200) (instOfNatNat (nat_lit 200)))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.heapHeight i)
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(@HSub.hSub.{0, 0, 0} Nat Nat Nat (@instHSub.{0} Nat instSubNat)
(@DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.State.potential i deleted q)
(@DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.State.potential i deleted next))))))))) ∧ (((∀ {i : DecrAlmostLinearSSSP.Decremental.Input} {deleted : List.{0} (Fin i.k)},
i.Valid →
∀ (q : DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.State i deleted)
(s : DecrAlmostLinearSSSP.Decremental.Structured.Data),
@DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.State.memory i deleted q s →
∃ next t cost,
And
(DecrAlmostLinearSSSP.Decremental.Structured.Eval DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.loop s
cost t)
(And (@DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.State.memory i deleted next t)
(And
(@Eq.{1} (Multiset.{0} (Prod.{0, 0} Nat (Fin i.n)))
(@DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.State.queue i deleted next)
(@OfNat.ofNat.{0} (Multiset.{0} (Prod.{0, 0} Nat (Fin i.n))) (nat_lit 0)
(@Zero.toOfNat0.{0} (Multiset.{0} (Prod.{0, 0} Nat (Fin i.n)))
(@Multiset.instZero.{0} (Prod.{0, 0} Nat (Fin i.n))))))
(And
(@LE.le.{0} Nat instLENat cost
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 200) (instOfNatNat (nat_lit 200)))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.heapHeight i)
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(@DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.State.potential i deleted q))
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))))
(∀ (v : Fin i.n),
@Eq.{1} ENNReal (DecrAlmostLinearSSSP.Decremental.stored t.machine (@Fin.val i.n v))
(i.dist deleted v)))))) ∧ (∀ {i : DecrAlmostLinearSSSP.Decremental.Input} {deleted : List.{0} (Fin i.k)}
(q : DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.State i deleted)
(s : DecrAlmostLinearSSSP.Decremental.Structured.Data),
DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.Memory i deleted
(@DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.State.tentative i deleted q)
(@DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.State.settled i deleted q)
(@DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.State.tree i deleted q)
(@DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.State.queue i deleted q) s →
And
(@Eq.{1} ENNReal (DecrAlmostLinearSSSP.Decremental.stored s.machine (@Fin.val i.n i.source))
(@OfNat.ofNat.{0} ENNReal (nat_lit 0) (@Zero.toOfNat0.{0} ENNReal ENNReal.instZero)))
(∀ (v : Fin i.n),
And
(@LE.le.{0} Nat instLENat (s.natMem (@Fin.val i.n v))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(@Eq.{1} Nat (s.natMem (@Fin.val i.n v)) (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))) →
@LE.le.{0} Real Real.instLE (@OfNat.ofNat.{0} Real (nat_lit 0) (@Zero.toOfNat0.{0} Real Real.instZero))
(s.realMem (@Fin.val i.n v)))))) ∧ ((∀ {i : DecrAlmostLinearSSSP.Decremental.Input} {deleted : List.{0} (Fin i.k)}
(q : DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.State i deleted)
(s : DecrAlmostLinearSSSP.Decremental.Structured.Data),
DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.Memory i deleted
(@DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.State.tentative i deleted q)
(@DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.State.settled i deleted q)
(@DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.State.tree i deleted q)
(@DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.State.queue i deleted q) s →
@Eq.{1} (Multiset.{0} (Prod.{0, 0} Nat (Fin i.n)))
(@DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.State.queue i deleted q)
(@OfNat.ofNat.{0} (Multiset.{0} (Prod.{0, 0} Nat (Fin i.n))) (nat_lit 0)
(@Zero.toOfNat0.{0} (Multiset.{0} (Prod.{0, 0} Nat (Fin i.n)))
(@Multiset.instZero.{0} (Prod.{0, 0} Nat (Fin i.n))))) →
∀ (v : Fin i.n),
And (@Eq.{1} ENNReal (DecrAlmostLinearSSSP.Decremental.stored s.machine (@Fin.val i.n v)) (i.dist deleted v))
(Iff
(@Eq.{1} ENNReal (DecrAlmostLinearSSSP.Decremental.stored s.machine (@Fin.val i.n v))
(@Top.top.{0} ENNReal ENNReal.instTop))
(Not
(@DecrAlmostLinearSSSP.Decremental.Reachable i.n i.k i.graph
(@DecrAlmostLinearSSSP.Decremental.live i.k deleted) i.source v)))) ∧ ((∀ (s : DecrAlmostLinearSSSP.Decremental.Structured.Data),
DecrAlmostLinearSSSP.Decremental.Structured.Eval DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.resetBody s
(@OfNat.ofNat.{0} Nat (nat_lit 4) (instOfNatNat (nat_lit 4)))
(DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.resetAdvanced s)) ∧ (∀ (s : DecrAlmostLinearSSSP.Decremental.Structured.Data),
@Eq.{1} Nat (s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 56) (instOfNatNat (nat_lit 56))))
(@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))) →
@Eq.{1} Nat (s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 26) (instOfNatNat (nat_lit 26))))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))) →
And
(@Eq.{1} (Nat → Nat) (DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.resetAdvanced s).natMem
(@Function.update.{1, 1} Nat (fun a => Nat) instDecidableEqNat
(@Function.update.{1, 1} Nat (fun a => Nat) instDecidableEqNat s.natMem
(s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 340) (instOfNatNat (nat_lit 340))))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 226) (instOfNatNat (nat_lit 226))))
(s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 340) (instOfNatNat (nat_lit 340)))))
(@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))))
(And
(@Eq.{1} Nat
((DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.resetAdvanced s).natReg
(@OfNat.ofNat.{0} Nat (nat_lit 340) (instOfNatNat (nat_lit 340))))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 340) (instOfNatNat (nat_lit 340))))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(@Eq.{1} (Nat → Real) (DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.resetAdvanced s).realMem s.realMem)))))))) ∧ (((((∀ (j : Nat),
@Ne.{1} Nat j (@OfNat.ofNat.{0} Nat (nat_lit 340) (instOfNatNat (nat_lit 340))) →
@Ne.{1} Nat j (@OfNat.ofNat.{0} Nat (nat_lit 342) (instOfNatNat (nat_lit 342))) →
DecrAlmostLinearSSSP.Decremental.Structured.NatFrame DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.resetBody j) ∧ (∀ (j : Nat),
@Ne.{1} Nat j (@OfNat.ofNat.{0} Nat (nat_lit 340) (instOfNatNat (nat_lit 340))) →
@Ne.{1} Nat j (@OfNat.ofNat.{0} Nat (nat_lit 342) (instOfNatNat (nat_lit 342))) →
DecrAlmostLinearSSSP.Decremental.Structured.NatFrame DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.resetLoop j)) ∧ ((∀ (j : Nat),
DecrAlmostLinearSSSP.Decremental.Structured.RealFrame DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.resetLoop j) ∧ (∀ (bank start remaining : Nat) (s : DecrAlmostLinearSSSP.Decremental.Structured.Data),
@Eq.{1} Nat (s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 56) (instOfNatNat (nat_lit 56))))
(@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))) →
@Eq.{1} Nat (s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 26) (instOfNatNat (nat_lit 26))))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))) →
@Eq.{1} Nat (s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 226) (instOfNatNat (nat_lit 226)))) bank →
@Eq.{1} Nat (s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 340) (instOfNatNat (nat_lit 340)))) start →
@Eq.{1} Nat (s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 66) (instOfNatNat (nat_lit 66))))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) start remaining) →
@LE.le.{0} Nat instLENat (@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) start remaining)
bank →
∃ t,
And
(DecrAlmostLinearSSSP.Decremental.Structured.Eval
DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.resetLoop s
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 6) (instOfNatNat (nat_lit 6))) remaining)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))))
t)
(And
(@Eq.{1} Nat (t.natReg (@OfNat.ofNat.{0} Nat (nat_lit 340) (instOfNatNat (nat_lit 340))))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) start remaining))
(And
(∀ (j : Nat),
@LE.le.{0} Nat instLENat start j →
@LT.lt.{0} Nat instLTNat j
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) start remaining) →
And (@Eq.{1} Nat (t.natMem j) (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(@Eq.{1} Nat
(t.natMem (@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) bank j))
(@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))))
(And (@Eq.{1} (Nat → Real) t.realMem s.realMem)
(∀ (a : Nat),
Or (@LT.lt.{0} Nat instLTNat a start)
(@LE.le.{0} Nat instLENat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) start remaining) a) →
Or
(@LT.lt.{0} Nat instLTNat a
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) bank start))
(@LE.le.{0} Nat instLENat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) bank start)
remaining)
a) →
@Eq.{1} Nat (t.natMem a) (s.natMem a)))))))) ∧ (((∀ {i : DecrAlmostLinearSSSP.Decremental.Input} {deleted : List.{0} (Fin i.k)} {tentative : Fin i.n → Option.{0} Nat}
{settled : Finset.{0} (Fin i.n)}
{tree :
DecrAlmostLinearSSSP.Decremental.Exact.LocatedTrie (DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.heapHeight i)}
{queue : Multiset.{0} (Prod.{0, 0} Nat (Fin i.n))} {s : DecrAlmostLinearSSSP.Decremental.Structured.Data},
DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.Memory i deleted tentative settled tree queue s →
DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.Ready i deleted s) ∧ (∀ {i : DecrAlmostLinearSSSP.Decremental.Input} {deleted : List.{0} (Fin i.k)}
{s t : DecrAlmostLinearSSSP.Decremental.Structured.Data},
DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.Ready i deleted s →
(∀ (j : Nat),
@LE.le.{0} Nat instLENat j (@OfNat.ofNat.{0} Nat (nat_lit 246) (instOfNatNat (nat_lit 246))) →
@Eq.{1} Nat (t.natReg j) (s.natReg j)) →
@Eq.{1} Real (t.realReg (@OfNat.ofNat.{0} Nat (nat_lit 56) (instOfNatNat (nat_lit 56))))
(s.realReg (@OfNat.ofNat.{0} Nat (nat_lit 56) (instOfNatNat (nat_lit 56)))) →
DecrAlmostLinearSSSP.Decremental.Exact.Adjacency.StaticImage i
(DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.layout i) t →
DecrAlmostLinearSSSP.Decremental.Exact.Adjacency.ActiveImage i
(DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.layout i) deleted t →
(∀ (j : Nat),
@LT.lt.{0} Nat instLTNat j (DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.heapHeight i) →
@Eq.{1} Nat
(t.natMem
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.heapBase i) j))
(s.natMem
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.heapBase i) j))) →
DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.Ready i deleted t)) ∧ ((∀ {i : DecrAlmostLinearSSSP.Decremental.Input} {s t : DecrAlmostLinearSSSP.Decremental.Structured.Data},
DecrAlmostLinearSSSP.Decremental.InputCapture.Captured i s →
(∀ (j : Nat),
@LE.le.{0} Nat instLENat j (@OfNat.ofNat.{0} Nat (nat_lit 74) (instOfNatNat (nat_lit 74))) →
@Eq.{1} Nat (t.natReg j) (s.natReg j)) →
(∀ (j : Nat),
@LE.le.{0} Nat instLENat j (@OfNat.ofNat.{0} Nat (nat_lit 64) (instOfNatNat (nat_lit 64))) →
@Eq.{1} Real (t.realReg j) (s.realReg j)) →
DecrAlmostLinearSSSP.Decremental.InputCapture.Captured i t) ∧ ((∀ (s : DecrAlmostLinearSSSP.Decremental.Structured.Data),
DecrAlmostLinearSSSP.Decremental.Structured.Eval DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.install s
(@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3)))
(DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.installed s)) ∧ (∀ (j : Nat),
@Ne.{1} Nat j (@OfNat.ofNat.{0} Nat (nat_lit 236) (instOfNatNat (nat_lit 236))) →
@Ne.{1} Nat j (@OfNat.ofNat.{0} Nat (nat_lit 238) (instOfNatNat (nat_lit 238))) →
@Ne.{1} Nat j (@OfNat.ofNat.{0} Nat (nat_lit 246) (instOfNatNat (nat_lit 246))) →
DecrAlmostLinearSSSP.Decremental.Structured.NatFrame DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.install j))))) ∧ ((((∀ (j : Nat),
DecrAlmostLinearSSSP.Decremental.Structured.RealFrame DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.install j) ∧ (∀ (i : DecrAlmostLinearSSSP.Decremental.Input) (s : DecrAlmostLinearSSSP.Decremental.Structured.Data),
DecrAlmostLinearSSSP.Decremental.InputCapture.Captured i s →
DecrAlmostLinearSSSP.Decremental.Exact.Layout.Image (DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.layout i) s →
DecrAlmostLinearSSSP.Decremental.Exact.Adjacency.StaticImage i
(DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.layout i) s →
DecrAlmostLinearSSSP.Decremental.Exact.Adjacency.ActiveImage i
(DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.layout i) (@List.nil.{0} (Fin i.k)) s →
DecrAlmostLinearSSSP.Decremental.Exact.Powers.Prefix
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) i.n i.W)
(DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.heapBase i)
(DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.heapHeight i) s →
DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.Ready i (@List.nil.{0} (Fin i.k))
(DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.installed s))) ∧ ((∀ (j : Nat),
@LE.le.{0} Nat instLENat j (@OfNat.ofNat.{0} Nat (nat_lit 64) (instOfNatNat (nat_lit 64))) →
DecrAlmostLinearSSSP.Decremental.Structured.RealFrame DecrAlmostLinearSSSP.Decremental.Exact.Powers.code j) ∧ (∀ {i : DecrAlmostLinearSSSP.Decremental.Input} {s : DecrAlmostLinearSSSP.Decremental.Structured.Data},
DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.Preparation i s →
∃ t,
And
(DecrAlmostLinearSSSP.Decremental.Structured.Eval
(DecrAlmostLinearSSSP.Decremental.Exact.Powers.code.seq
DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.install)
s
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7)))
(DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.heapHeight i))
(@OfNat.ofNat.{0} Nat (nat_lit 14) (instOfNatNat (nat_lit 14))))
t)
(DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.Ready i (@List.nil.{0} (Fin i.k)) t)))) ∧ (((∀ (p : DecrAlmostLinearSSSP.Decremental.Program) (i : DecrAlmostLinearSSSP.Decremental.Input),
DecrAlmostLinearSSSP.Decremental.InputCapture.RawInput i
(DecrAlmostLinearSSSP.Decremental.Structured.data (DecrAlmostLinearSSSP.Decremental.initialMachine p i))) ∧ (∀ (i : DecrAlmostLinearSSSP.Decremental.Input) (s : DecrAlmostLinearSSSP.Decremental.Structured.Data),
DecrAlmostLinearSSSP.Decremental.InputCapture.RawInput i s →
DecrAlmostLinearSSSP.Decremental.InputCapture.Captured i (DecrAlmostLinearSSSP.Decremental.InputCapture.result s))) ∧ ((∀ (i : DecrAlmostLinearSSSP.Decremental.Input) (s : DecrAlmostLinearSSSP.Decremental.Structured.Data),
DecrAlmostLinearSSSP.Decremental.InputCapture.RawInput i s →
DecrAlmostLinearSSSP.Decremental.Exact.Adjacency.Tape i s →
∃ t,
And
(DecrAlmostLinearSSSP.Decremental.Structured.Eval DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.prepareGraph
s
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 4) (instOfNatNat (nat_lit 4))) i.n)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 22) (instOfNatNat (nat_lit 22))) i.k))
(@OfNat.ofNat.{0} Nat (nat_lit 37) (instOfNatNat (nat_lit 37))))
t)
(DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.Preparation i t)) ∧ ((∀ {i : DecrAlmostLinearSSSP.Decremental.Input} {deleted : List.{0} (Fin i.k)}
{s t : DecrAlmostLinearSSSP.Decremental.Structured.Data},
DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.Ready i deleted s →
(∀ (j : Nat),
@LE.le.{0} Nat instLENat j (@OfNat.ofNat.{0} Nat (nat_lit 246) (instOfNatNat (nat_lit 246))) →
@Eq.{1} Nat (t.natReg j) (s.natReg j)) →
@Eq.{1} Real (t.realReg (@OfNat.ofNat.{0} Nat (nat_lit 56) (instOfNatNat (nat_lit 56))))
(s.realReg (@OfNat.ofNat.{0} Nat (nat_lit 56) (instOfNatNat (nat_lit 56)))) →
@Eq.{1} (Nat → Nat) t.natMem s.natMem → DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.Ready i deleted t) ∧ (∀ {i : DecrAlmostLinearSSSP.Decremental.Input} {deleted : List.{0} (Fin i.k)}
{s : DecrAlmostLinearSSSP.Decremental.Structured.Data},
DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.Ready i deleted s →
∃ t,
And
(DecrAlmostLinearSSSP.Decremental.Structured.Eval
(DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.resetPrepare.seq
DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.resetLoop)
s
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 6) (instOfNatNat (nat_lit 6))) i.n)
(@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3))))
t)
(And (DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.Ready i deleted t)
(And
(∀ (v : Fin i.n),
And
(@Eq.{1} Nat (t.natMem (@Fin.val i.n v)) (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(@Eq.{1} Nat
(t.natMem
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.layout i).settled (@Fin.val i.n v)))
(@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))))
(@Eq.{1} (Nat → Real) t.realMem s.realMem)))))))))) ∧ ((((((∀ (s : DecrAlmostLinearSSSP.Decremental.Structured.Data),
DecrAlmostLinearSSSP.Decremental.Structured.Eval DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.rootSetup s
(@OfNat.ofNat.{0} Nat (nat_lit 8) (instOfNatNat (nat_lit 8)))
(DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.rootData s)) ∧ (∀ (j : Nat),
@Ne.{1} Nat j (@OfNat.ofNat.{0} Nat (nat_lit 244) (instOfNatNat (nat_lit 244))) →
@Ne.{1} Nat j (@OfNat.ofNat.{0} Nat (nat_lit 260) (instOfNatNat (nat_lit 260))) →
@Ne.{1} Nat j (@OfNat.ofNat.{0} Nat (nat_lit 262) (instOfNatNat (nat_lit 262))) →
@Ne.{1} Nat j (@OfNat.ofNat.{0} Nat (nat_lit 342) (instOfNatNat (nat_lit 342))) →
DecrAlmostLinearSSSP.Decremental.Structured.NatFrame DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.rootSetup
j)) ∧ ((∀ (j : Nat),
DecrAlmostLinearSSSP.Decremental.Structured.RealFrame DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.rootSetup j) ∧ (∀ {i : DecrAlmostLinearSSSP.Decremental.Input} {deleted : List.{0} (Fin i.k)}
{s : DecrAlmostLinearSSSP.Decremental.Structured.Data},
DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.Ready i deleted s →
And
(@Eq.{1} (Nat → Nat) (DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.rootData s).natMem
(@Function.update.{1, 1} Nat (fun a => Nat) instDecidableEqNat
(@Function.update.{1, 1} Nat (fun a => Nat) instDecidableEqNat
(@Function.update.{1, 1} Nat (fun a => Nat) instDecidableEqNat s.natMem
(DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.heapSlot i)
(@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))))
(@Fin.val i.n i.source) (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.layout i).distances (@Fin.val i.n i.source))
(@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))))
(And
(@Eq.{1} (Nat → Real) (DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.rootData s).realMem
(@Function.update.{1, 1} Nat (fun a => Real) instDecidableEqNat s.realMem (@Fin.val i.n i.source)
(@OfNat.ofNat.{0} Real (nat_lit 0) (@Zero.toOfNat0.{0} Real Real.instZero))))
(And
(@Eq.{1} Nat
((DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.rootData s).natReg
(@OfNat.ofNat.{0} Nat (nat_lit 244) (instOfNatNat (nat_lit 244))))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.heapSlot i)
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(And
(@Eq.{1} Nat
((DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.rootData s).natReg
(@OfNat.ofNat.{0} Nat (nat_lit 260) (instOfNatNat (nat_lit 260))))
(@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))))
(@Eq.{1} Nat
((DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.rootData s).natReg
(@OfNat.ofNat.{0} Nat (nat_lit 262) (instOfNatNat (nat_lit 262))))
(@Fin.val i.n i.source)))))))) ∧ (((∀ {i : DecrAlmostLinearSSSP.Decremental.Input} {deleted : List.{0} (Fin i.k)}
{s : DecrAlmostLinearSSSP.Decremental.Structured.Data},
DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.Ready i deleted s →
(∀ (v : Fin i.n),
And (@Eq.{1} Nat (s.natMem (@Fin.val i.n v)) (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(@Eq.{1} Nat
(s.natMem
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.layout i).settled (@Fin.val i.n v)))
(@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))))) →
DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.Memory i deleted
(@DecrAlmostLinearSSSP.Decremental.Exact.initialTentative i.n i.source)
(@EmptyCollection.emptyCollection.{0} (Finset.{0} (Fin i.n)) (@Finset.instEmptyCollection.{0} (Fin i.n)))
(@DecrAlmostLinearSSSP.Decremental.Exact.LocatedTrie.empty
(DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.heapHeight i))
(@OfNat.ofNat.{0} (Multiset.{0} (Prod.{0, 0} Nat (Fin i.n))) (nat_lit 0)
(@Zero.toOfNat0.{0} (Multiset.{0} (Prod.{0, 0} Nat (Fin i.n)))
(@Multiset.instZero.{0} (Prod.{0, 0} Nat (Fin i.n)))))
(DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.rootData s)) ∧ (∀ {i : DecrAlmostLinearSSSP.Decremental.Input} {deleted : List.{0} (Fin i.k)}
{s : DecrAlmostLinearSSSP.Decremental.Structured.Data},
DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.Ready i deleted s →
(∀ (v : Fin i.n),
And (@Eq.{1} Nat (s.natMem (@Fin.val i.n v)) (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(@Eq.{1} Nat
(s.natMem
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.layout i).settled (@Fin.val i.n v)))
(@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))))) →
∃ cost t q,
And
(DecrAlmostLinearSSSP.Decremental.Structured.Eval
(DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.rootSetup.seq
(DecrAlmostLinearSSSP.Decremental.Exact.TriePush.code.seq
DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.queueCount))
s cost t)
(And
(@LE.le.{0} Nat instLENat cost
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 43) (instOfNatNat (nat_lit 43)))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.heapHeight i)
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(@OfNat.ofNat.{0} Nat (nat_lit 12) (instOfNatNat (nat_lit 12)))))
(And (@DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.State.memory i deleted q t)
(@Eq.{1} Nat (@DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.State.potential i deleted q)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) i.k)
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))))))) ∧ ((∀ {s u v t : DecrAlmostLinearSSSP.Decremental.Structured.Data} {cr cb cl : Nat},
DecrAlmostLinearSSSP.Decremental.Structured.Eval
(DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.resetPrepare.seq
DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.resetLoop)
s cr u →
DecrAlmostLinearSSSP.Decremental.Structured.Eval
(DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.rootSetup.seq
(DecrAlmostLinearSSSP.Decremental.Exact.TriePush.code.seq
DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.queueCount))
u cb v →
DecrAlmostLinearSSSP.Decremental.Structured.Eval DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.loop v cl t →
DecrAlmostLinearSSSP.Decremental.Structured.Eval DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.code s
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) cr cb) cl)
t) ∧ (∀ {i : DecrAlmostLinearSSSP.Decremental.Input} {deleted : List.{0} (Fin i.k)}
{s : DecrAlmostLinearSSSP.Decremental.Structured.Data},
i.Valid →
DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.Ready i deleted s →
∃ cost t q,
And
(DecrAlmostLinearSSSP.Decremental.Structured.Eval DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.code s cost
t)
(And
(@LE.le.{0} Nat instLENat cost
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 600) (instOfNatNat (nat_lit 600)))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) i.n i.k)
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.heapHeight i)
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))))
(And (@DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.State.memory i deleted q t)
(And
(@Eq.{1} (Multiset.{0} (Prod.{0, 0} Nat (Fin i.n)))
(@DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.State.queue i deleted q)
(@OfNat.ofNat.{0} (Multiset.{0} (Prod.{0, 0} Nat (Fin i.n))) (nat_lit 0)
(@Zero.toOfNat0.{0} (Multiset.{0} (Prod.{0, 0} Nat (Fin i.n)))
(@Multiset.instZero.{0} (Prod.{0, 0} Nat (Fin i.n))))))
(And (DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.Ready i deleted t)
(And
(@Eq.{1} ENNReal (DecrAlmostLinearSSSP.Decremental.stored t.machine (@Fin.val i.n i.source))
(@OfNat.ofNat.{0} ENNReal (nat_lit 0) (@Zero.toOfNat0.{0} ENNReal ENNReal.instZero)))
(And
(∀ (v : Fin i.n),
And
(@LE.le.{0} Nat instLENat (t.natMem (@Fin.val i.n v))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(@Eq.{1} Nat (t.natMem (@Fin.val i.n v))
(@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))) →
@LE.le.{0} Real Real.instLE
(@OfNat.ofNat.{0} Real (nat_lit 0) (@Zero.toOfNat0.{0} Real Real.instZero))
(t.realMem (@Fin.val i.n v))))
(∀ (v : Fin i.n),
And
(@Eq.{1} ENNReal (DecrAlmostLinearSSSP.Decremental.stored t.machine (@Fin.val i.n v))
(i.dist deleted v))
(Iff
(@Eq.{1} ENNReal (DecrAlmostLinearSSSP.Decremental.stored t.machine (@Fin.val i.n v))
(@Top.top.{0} ENNReal ENNReal.instTop))
(Not
(@DecrAlmostLinearSSSP.Decremental.Reachable i.n i.k i.graph
(@DecrAlmostLinearSSSP.Decremental.live i.k deleted) i.source v)))))))))))))) ∧ ((((∀ (s : DecrAlmostLinearSSSP.Decremental.Structured.Data),
DecrAlmostLinearSSSP.Decremental.Structured.Eval DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.deleteCode s
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))
(DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.deletedData s)) ∧ (∀ (j : Nat),
@Ne.{1} Nat j (@OfNat.ofNat.{0} Nat (nat_lit 350) (instOfNatNat (nat_lit 350))) →
DecrAlmostLinearSSSP.Decremental.Structured.NatFrame DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.deleteCode j)) ∧ ((∀ (j : Nat),
DecrAlmostLinearSSSP.Decremental.Structured.RealFrame DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.deleteCode j) ∧ (∀ {i : DecrAlmostLinearSSSP.Decremental.Input} {deleted : List.{0} (Fin i.k)}
{s : DecrAlmostLinearSSSP.Decremental.Structured.Data},
DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.Ready i deleted s →
∀ (e : Fin i.k),
@Eq.{1} Nat (s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 5) (instOfNatNat (nat_lit 5)))) (@Fin.val i.k e) →
DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.Ready i
(@HAppend.hAppend.{0, 0, 0} (List.{0} (Fin i.k)) (List.{0} (Fin i.k)) (List.{0} (Fin i.k))
(@instHAppendOfAppend.{0} (List.{0} (Fin i.k)) (@List.instAppend.{0} (Fin i.k))) deleted
(@List.cons.{0} (Fin i.k) e (@List.nil.{0} (Fin i.k))))
(DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.deletedData s)))) ∧ (((∀ (i : DecrAlmostLinearSSSP.Decremental.Input),
i.Valid →
∀ (s : DecrAlmostLinearSSSP.Decremental.Structured.Data),
DecrAlmostLinearSSSP.Decremental.InputCapture.RawInput i s →
DecrAlmostLinearSSSP.Decremental.Exact.Adjacency.Tape i s →
∃ cost t q,
And
(DecrAlmostLinearSSSP.Decremental.Structured.Eval
DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.initializeCode s cost t)
(And
(@LE.le.{0} Nat instLENat cost
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 700) (instOfNatNat (nat_lit 700)))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) i.n i.k)
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.heapHeight i)
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))))
(And (@DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.State.memory i (@List.nil.{0} (Fin i.k)) q t)
(And
(@Eq.{1} (Multiset.{0} (Prod.{0, 0} Nat (Fin i.n)))
(@DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.State.queue i (@List.nil.{0} (Fin i.k)) q)
(@OfNat.ofNat.{0} (Multiset.{0} (Prod.{0, 0} Nat (Fin i.n))) (nat_lit 0)
(@Zero.toOfNat0.{0} (Multiset.{0} (Prod.{0, 0} Nat (Fin i.n)))
(@Multiset.instZero.{0} (Prod.{0, 0} Nat (Fin i.n))))))
(And (DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.Ready i (@List.nil.{0} (Fin i.k)) t)
(And
(@Eq.{1} ENNReal (DecrAlmostLinearSSSP.Decremental.stored t.machine (@Fin.val i.n i.source))
(@OfNat.ofNat.{0} ENNReal (nat_lit 0) (@Zero.toOfNat0.{0} ENNReal ENNReal.instZero)))
(And
(∀ (v : Fin i.n),
And
(@LE.le.{0} Nat instLENat (t.natMem (@Fin.val i.n v))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(@Eq.{1} Nat (t.natMem (@Fin.val i.n v))
(@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))) →
@LE.le.{0} Real Real.instLE
(@OfNat.ofNat.{0} Real (nat_lit 0) (@Zero.toOfNat0.{0} Real Real.instZero))
(t.realMem (@Fin.val i.n v))))
(∀ (v : Fin i.n),
And
(@Eq.{1} ENNReal (DecrAlmostLinearSSSP.Decremental.stored t.machine (@Fin.val i.n v))
(i.dist (@List.nil.{0} (Fin i.k)) v))
(Iff
(@Eq.{1} ENNReal (DecrAlmostLinearSSSP.Decremental.stored t.machine (@Fin.val i.n v))
(@Top.top.{0} ENNReal ENNReal.instTop))
(Not
(@DecrAlmostLinearSSSP.Decremental.Reachable i.n i.k i.graph
(@DecrAlmostLinearSSSP.Decremental.live i.k (@List.nil.{0} (Fin i.k))) i.source
v))))))))))) ∧ (∀ {i : DecrAlmostLinearSSSP.Decremental.Input} {deleted : List.{0} (Fin i.k)}
{s : DecrAlmostLinearSSSP.Decremental.Structured.Data},
DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.Ready i deleted s →
∀ (index : Nat),
DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.Ready i deleted
{ realReg := s.realReg,
natReg :=
@Function.update.{1, 1} Nat (fun a => Nat) instDecidableEqNat s.natReg
(@OfNat.ofNat.{0} Nat (nat_lit 5) (instOfNatNat (nat_lit 5))) index,
realMem := s.realMem, natMem := s.natMem })) ∧ ((∀ {i : DecrAlmostLinearSSSP.Decremental.Input},
i.Valid →
∀ {deleted : List.{0} (Fin i.k)} {s : DecrAlmostLinearSSSP.Decremental.Structured.Data},
DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.Ready i deleted s →
∀ (e : Fin i.k),
@Eq.{1} Nat (s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 5) (instOfNatNat (nat_lit 5)))) (@Fin.val i.k e) →
∃ cost t q,
And
(DecrAlmostLinearSSSP.Decremental.Structured.Eval
DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.updateCode s cost t)
(And
(@LE.le.{0} Nat instLENat cost
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 602) (instOfNatNat (nat_lit 602)))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) i.n i.k)
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.heapHeight i)
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))))
(And
(@DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.State.memory i
(@HAppend.hAppend.{0, 0, 0} (List.{0} (Fin i.k)) (List.{0} (Fin i.k)) (List.{0} (Fin i.k))
(@instHAppendOfAppend.{0} (List.{0} (Fin i.k)) (@List.instAppend.{0} (Fin i.k))) deleted
(@List.cons.{0} (Fin i.k) e (@List.nil.{0} (Fin i.k))))
q t)
(And
(@Eq.{1} (Multiset.{0} (Prod.{0, 0} Nat (Fin i.n)))
(@DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.State.queue i
(@HAppend.hAppend.{0, 0, 0} (List.{0} (Fin i.k)) (List.{0} (Fin i.k)) (List.{0} (Fin i.k))
(@instHAppendOfAppend.{0} (List.{0} (Fin i.k)) (@List.instAppend.{0} (Fin i.k))) deleted
(@List.cons.{0} (Fin i.k) e (@List.nil.{0} (Fin i.k))))
q)
(@OfNat.ofNat.{0} (Multiset.{0} (Prod.{0, 0} Nat (Fin i.n))) (nat_lit 0)
(@Zero.toOfNat0.{0} (Multiset.{0} (Prod.{0, 0} Nat (Fin i.n)))
(@Multiset.instZero.{0} (Prod.{0, 0} Nat (Fin i.n))))))
(And
(DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.Ready i
(@HAppend.hAppend.{0, 0, 0} (List.{0} (Fin i.k)) (List.{0} (Fin i.k)) (List.{0} (Fin i.k))
(@instHAppendOfAppend.{0} (List.{0} (Fin i.k)) (@List.instAppend.{0} (Fin i.k))) deleted
(@List.cons.{0} (Fin i.k) e (@List.nil.{0} (Fin i.k))))
t)
(And
(@Eq.{1} ENNReal (DecrAlmostLinearSSSP.Decremental.stored t.machine (@Fin.val i.n i.source))
(@OfNat.ofNat.{0} ENNReal (nat_lit 0) (@Zero.toOfNat0.{0} ENNReal ENNReal.instZero)))
(And
(∀ (v : Fin i.n),
And
(@LE.le.{0} Nat instLENat (t.natMem (@Fin.val i.n v))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(@Eq.{1} Nat (t.natMem (@Fin.val i.n v))
(@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))) →
@LE.le.{0} Real Real.instLE
(@OfNat.ofNat.{0} Real (nat_lit 0) (@Zero.toOfNat0.{0} Real Real.instZero))
(t.realMem (@Fin.val i.n v))))
(∀ (v : Fin i.n),
And
(@Eq.{1} ENNReal (DecrAlmostLinearSSSP.Decremental.stored t.machine (@Fin.val i.n v))
(i.dist
(@HAppend.hAppend.{0, 0, 0} (List.{0} (Fin i.k)) (List.{0} (Fin i.k))
(List.{0} (Fin i.k))
(@instHAppendOfAppend.{0} (List.{0} (Fin i.k)) (@List.instAppend.{0} (Fin i.k)))
deleted (@List.cons.{0} (Fin i.k) e (@List.nil.{0} (Fin i.k))))
v))
(Iff
(@Eq.{1} ENNReal (DecrAlmostLinearSSSP.Decremental.stored t.machine (@Fin.val i.n v))
(@Top.top.{0} ENNReal ENNReal.instTop))
(Not
(@DecrAlmostLinearSSSP.Decremental.Reachable i.n i.k i.graph
(@DecrAlmostLinearSSSP.Decremental.live i.k
(@HAppend.hAppend.{0, 0, 0} (List.{0} (Fin i.k)) (List.{0} (Fin i.k))
(List.{0} (Fin i.k))
(@instHAppendOfAppend.{0} (List.{0} (Fin i.k))
(@List.instAppend.{0} (Fin i.k)))
deleted (@List.cons.{0} (Fin i.k) e (@List.nil.{0} (Fin i.k)))))
i.source v))))))))))) ∧ ((∀ (i : DecrAlmostLinearSSSP.Decremental.Input),
i.Valid →
∃ cost c,
And
(DecrAlmostLinearSSSP.Decremental.Ends DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.hostProgram
(DecrAlmostLinearSSSP.Decremental.initialMachine DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.hostProgram
i)
c)
(And
(@Eq.{1} Nat c.work
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) cost
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(And
(@LE.le.{0} Nat instLENat cost
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 700) (instOfNatNat (nat_lit 700)))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) i.n i.k)
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.heapHeight i)
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))))
(And
(DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.Ready i (@List.nil.{0} (Fin i.k))
(DecrAlmostLinearSSSP.Decremental.Structured.data c))
(∃ q,
And
(@DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.State.memory i (@List.nil.{0} (Fin i.k)) q
(DecrAlmostLinearSSSP.Decremental.Structured.data c))
(@Eq.{1} (Multiset.{0} (Prod.{0, 0} Nat (Fin i.n)))
(@DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.State.queue i (@List.nil.{0} (Fin i.k)) q)
(@OfNat.ofNat.{0} (Multiset.{0} (Prod.{0, 0} Nat (Fin i.n))) (nat_lit 0)
(@Zero.toOfNat0.{0} (Multiset.{0} (Prod.{0, 0} Nat (Fin i.n)))
(@Multiset.instZero.{0} (Prod.{0, 0} Nat (Fin i.n))))))))))) ∧ (∀ (i : DecrAlmostLinearSSSP.Decremental.Input),
i.Valid →
∀ (deleted : List.{0} (Fin i.k)) (c : DecrAlmostLinearSSSP.Decremental.Machine),
DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.Ready i deleted
(DecrAlmostLinearSSSP.Decremental.Structured.data c) →
∀ (e : Fin i.k),
∃ cost d,
And
(DecrAlmostLinearSSSP.Decremental.Ends DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.hostProgram
(DecrAlmostLinearSSSP.Decremental.deletionMachine
DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.hostProgram c (@Fin.val i.k e))
d)
(And
(@Eq.{1} Nat d.work
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.work cost)
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(And
(@LE.le.{0} Nat instLENat cost
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 602) (instOfNatNat (nat_lit 602)))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) i.n i.k)
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.heapHeight i)
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))))
(And
(DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.Ready i
(@HAppend.hAppend.{0, 0, 0} (List.{0} (Fin i.k)) (List.{0} (Fin i.k)) (List.{0} (Fin i.k))
(@instHAppendOfAppend.{0} (List.{0} (Fin i.k)) (@List.instAppend.{0} (Fin i.k))) deleted
(@List.cons.{0} (Fin i.k) e (@List.nil.{0} (Fin i.k))))
(DecrAlmostLinearSSSP.Decremental.Structured.data d))
(∃ q,
And
(@DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.State.memory i
(@HAppend.hAppend.{0, 0, 0} (List.{0} (Fin i.k)) (List.{0} (Fin i.k)) (List.{0} (Fin i.k))
(@instHAppendOfAppend.{0} (List.{0} (Fin i.k)) (@List.instAppend.{0} (Fin i.k))) deleted
(@List.cons.{0} (Fin i.k) e (@List.nil.{0} (Fin i.k))))
q (DecrAlmostLinearSSSP.Decremental.Structured.data d))
(@Eq.{1} (Multiset.{0} (Prod.{0, 0} Nat (Fin i.n)))
(@DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.State.queue i
(@HAppend.hAppend.{0, 0, 0} (List.{0} (Fin i.k)) (List.{0} (Fin i.k)) (List.{0} (Fin i.k))
(@instHAppendOfAppend.{0} (List.{0} (Fin i.k)) (@List.instAppend.{0} (Fin i.k))) deleted
(@List.cons.{0} (Fin i.k) e (@List.nil.{0} (Fin i.k))))
q)
(@OfNat.ofNat.{0} (Multiset.{0} (Prod.{0, 0} Nat (Fin i.n))) (nat_lit 0)
(@Zero.toOfNat0.{0} (Multiset.{0} (Prod.{0, 0} Nat (Fin i.n)))
(@Multiset.instZero.{0} (Prod.{0, 0} Nat (Fin i.n)))))))))))))))) ∧ (((((∀ {i : DecrAlmostLinearSSSP.Decremental.Input} {deleted : List.{0} (Fin i.k)}
{c : DecrAlmostLinearSSSP.Decremental.Machine},
DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.Completed i deleted c →
DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.Ready i deleted (DecrAlmostLinearSSSP.Decremental.Structured.data c)) ∧ (∀ {i : DecrAlmostLinearSSSP.Decremental.Input},
i.Valid →
∀ {deleted : List.{0} (Fin i.k)} {c : DecrAlmostLinearSSSP.Decremental.Machine},
DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.Completed i deleted c →
DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.Good i deleted c)) ∧ ((∀ (p : DecrAlmostLinearSSSP.Decremental.Program) (c d : DecrAlmostLinearSSSP.Decremental.Machine),
@Eq.{1} Bool c.halted Bool.false →
DecrAlmostLinearSSSP.Decremental.Ends p c d →
@LE.le.{0} Nat instLENat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.work
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
d.work) ∧ (∀ (D overhead before after cost : Nat),
@LE.le.{0} Nat instLENat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) before
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
after →
@LE.le.{0} Nat instLENat cost
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) D
(@HSub.hSub.{0, 0, 0} Nat Nat Nat (@instHSub.{0} Nat instSubNat) after before))
overhead) →
@LE.le.{0} Nat instLENat cost
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) D overhead)
(@HSub.hSub.{0, 0, 0} Nat Nat Nat (@instHSub.{0} Nat instSubNat) after before))))) ∧ (((∀ {k : Nat} (ds : List.{0} (Fin k)) (j : Nat),
@LE.le.{0} (Finset.{0} (Fin k))
(@Preorder.toLE.{0} (Finset.{0} (Fin k))
(@PartialOrder.toPreorder.{0} (Finset.{0} (Fin k)) (@Finset.instPartialOrder.{0} (Fin k))))
(@DecrAlmostLinearSSSP.Decremental.live k ds)
(@DecrAlmostLinearSSSP.Decremental.live k (@List.take.{0} (Fin k) j ds))) ∧ (∀ {p : DecrAlmostLinearSSSP.Decremental.Program} {i : DecrAlmostLinearSSSP.Decremental.Input} {ds : List.{0} (Fin i.k)}
{cs : List.{0} DecrAlmostLinearSSSP.Decremental.Machine},
DecrAlmostLinearSSSP.Decremental.OnlineRun p i ds cs →
∃ c,
And
(@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Machine)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Machine) Nat
DecrAlmostLinearSSSP.Decremental.Machine
(fun as i => @LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Machine as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Machine) cs
(@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))))
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Machine c))
(DecrAlmostLinearSSSP.Decremental.Ends p (DecrAlmostLinearSSSP.Decremental.initialMachine p i) c))) ∧ ((∀ {p : DecrAlmostLinearSSSP.Decremental.Program} {C : Real} {a : Nat → Real} {queryBound : Nat} {logWeights : Bool}
{i : DecrAlmostLinearSSSP.Decremental.Input},
DecrAlmostLinearSSSP.Decremental.Maintains p C a queryBound logWeights i →
∃ c,
And (DecrAlmostLinearSSSP.Decremental.Ends p (DecrAlmostLinearSSSP.Decremental.initialMachine p i) c)
(And
(@Eq.{1} ENNReal (DecrAlmostLinearSSSP.Decremental.stored c (@Fin.val i.n i.source))
(@OfNat.ofNat.{0} ENNReal (nat_lit 0) (@Zero.toOfNat0.{0} ENNReal ENNReal.instZero)))
(And
(∀ (v : Fin i.n),
And
(@LE.le.{0} Nat instLENat (c.natMem (@Fin.val i.n v))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(@Eq.{1} Nat (c.natMem (@Fin.val i.n v)) (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))) →
@LE.le.{0} Real Real.instLE
(@OfNat.ofNat.{0} Real (nat_lit 0) (@Zero.toOfNat0.{0} Real Real.instZero))
(c.realMem (@Fin.val i.n v))))
(And
(∀ (v : Fin i.n),
And
(@LE.le.{0} ENNReal ENNReal.instLE (i.dist (@List.nil.{0} (Fin i.k)) v)
(DecrAlmostLinearSSSP.Decremental.stored c (@Fin.val i.n v)))
(And
(@LE.le.{0} ENNReal ENNReal.instLE (DecrAlmostLinearSSSP.Decremental.stored c (@Fin.val i.n v))
(@HMul.hMul.{0, 0, 0} ENNReal ENNReal ENNReal
(@instHMul.{0} ENNReal
(@Distrib.toMul.{0} ENNReal
(@instDistribOfSemiring.{0} ENNReal
(@CommSemiring.toSemiring.{0} ENNReal ENNReal.instCommSemiring))))
(ENNReal.ofReal
(@HAdd.hAdd.{0, 0, 0} Real Real Real (@instHAdd.{0} Real Real.instAdd)
(@OfNat.ofNat.{0} Real (nat_lit 1) (@One.toOfNat1.{0} Real Real.instOne)) i.accuracy))
(i.dist (@List.nil.{0} (Fin i.k)) v)))
(Iff
(@Eq.{1} ENNReal (DecrAlmostLinearSSSP.Decremental.stored c (@Fin.val i.n v))
(@Top.top.{0} ENNReal ENNReal.instTop))
(Not
(@DecrAlmostLinearSSSP.Decremental.Reachable i.n i.k i.graph
(@DecrAlmostLinearSSSP.Decremental.live i.k (@List.nil.{0} (Fin i.k))) i.source v)))))
(@LE.le.{0} Real Real.instLE (@Nat.cast.{0} Real Real.instNatCast c.work)
(@HMul.hMul.{0, 0, 0} Real Real Real (@instHMul.{0} Real Real.instMul)
(@HDiv.hDiv.{0, 0, 0} Real Real Real
(@instHDiv.{0} Real (@DivInvMonoid.toDiv.{0} Real Real.instDivInvMonoid))
(@HMul.hMul.{0, 0, 0} Real Real Real (@instHMul.{0} Real Real.instMul)
(@HMul.hMul.{0, 0, 0} Real Real Real (@instHMul.{0} Real Real.instMul) C
(@Nat.cast.{0} Real Real.instNatCast i.size))
(a i.size))
i.accuracy)
(@ite.{1} Real (@Eq.{1} Bool logWeights Bool.true) (instDecidableEqBool logWeights Bool.true)
(@Max.max.{0} Real Real.instMax
(@OfNat.ofNat.{0} Real (nat_lit 1) (@One.toOfNat1.{0} Real Real.instOne))
(DecrAlmostLinearSSSP.Decremental.logarithm2 (@Nat.cast.{0} Real Real.instNatCast i.W)))
(@OfNat.ofNat.{0} Real (nat_lit 1) (@One.toOfNat1.{0} Real Real.instOne))))))))) ∧ ((∀ {p : DecrAlmostLinearSSSP.Decremental.Program} {c d e : DecrAlmostLinearSSSP.Decremental.Machine},
DecrAlmostLinearSSSP.Decremental.Ends p c d →
DecrAlmostLinearSSSP.Decremental.Ends p c e → @Eq.{1} DecrAlmostLinearSSSP.Decremental.Machine d e) ∧ (∀ {p : DecrAlmostLinearSSSP.Decremental.Program} {i : DecrAlmostLinearSSSP.Decremental.Input} {ds : List.{0} (Fin i.k)}
{cs : List.{0} DecrAlmostLinearSSSP.Decremental.Machine},
DecrAlmostLinearSSSP.Decremental.OnlineRun p i ds cs →
@Eq.{1} Nat (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Machine cs)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) (@List.length.{0} (Fin i.k) ds)
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))))))) ∧ ((((∀ {p : DecrAlmostLinearSSSP.Decremental.Program} {i : DecrAlmostLinearSSSP.Decremental.Input} {ds : List.{0} (Fin i.k)}
{cs : List.{0} DecrAlmostLinearSSSP.Decremental.Machine},
DecrAlmostLinearSSSP.Decremental.OnlineRun p i ds cs →
∀ (k : Nat) (hk : @LT.lt.{0} Nat instLTNat k (@List.length.{0} (Fin i.k) ds)),
∃ c d,
And
(@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Machine)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Machine) Nat
DecrAlmostLinearSSSP.Decremental.Machine
(fun as i => @LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Machine as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Machine) cs k)
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Machine c))
(And
(@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Machine)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Machine) Nat
DecrAlmostLinearSSSP.Decremental.Machine
(fun as i => @LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Machine as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Machine) cs
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) k
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Machine d))
(DecrAlmostLinearSSSP.Decremental.Ends p
(DecrAlmostLinearSSSP.Decremental.deletionMachine p c
(@Fin.val i.k
(@GetElem.getElem.{0, 0, 0} (List.{0} (Fin i.k)) Nat (Fin i.k)
(fun as i_1 => @LT.lt.{0} Nat instLTNat i_1 (@List.length.{0} (Fin i.k) as))
(@List.instGetElemNatLtLength.{0} (Fin i.k)) ds k hk)))
d))) ∧ (∀ {p : DecrAlmostLinearSSSP.Decremental.Program} {c d : DecrAlmostLinearSSSP.Decremental.Machine},
DecrAlmostLinearSSSP.Decremental.Ends p c d → @LE.le.{0} Nat instLENat c.work d.work)) ∧ ((∀ {p : DecrAlmostLinearSSSP.Decremental.Program} {i : DecrAlmostLinearSSSP.Decremental.Input} {ds : List.{0} (Fin i.k)}
{cs : List.{0} DecrAlmostLinearSSSP.Decremental.Machine},
DecrAlmostLinearSSSP.Decremental.OnlineRun p i ds cs →
∀ (last : DecrAlmostLinearSSSP.Decremental.Machine),
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Machine)
(@List.getLast?.{0} DecrAlmostLinearSSSP.Decremental.Machine cs)
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Machine last) →
∀ (c : DecrAlmostLinearSSSP.Decremental.Machine),
@Membership.mem.{0, 0} DecrAlmostLinearSSSP.Decremental.Machine
(List.{0} DecrAlmostLinearSSSP.Decremental.Machine)
(@List.instMembership.{0} DecrAlmostLinearSSSP.Decremental.Machine) cs c →
@LE.le.{0} Nat instLENat c.work last.work) ∧ (∀ (i : DecrAlmostLinearSSSP.Decremental.Input),
i.Valid →
∀ (ds : List.{0} (Fin i.k)),
∃ cs last,
And
(DecrAlmostLinearSSSP.Decremental.OnlineRun DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.hostProgram i ds
cs)
(And
(@Eq.{1} Nat (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Machine cs)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) (@List.length.{0} (Fin i.k) ds)
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(And
(@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Machine)
(@List.getLast?.{0} DecrAlmostLinearSSSP.Decremental.Machine cs)
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Machine last))
(And (DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.Completed i ds last)
(And
(∀ (j : Nat) (c : DecrAlmostLinearSSSP.Decremental.Machine),
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Machine)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Machine) Nat
DecrAlmostLinearSSSP.Decremental.Machine
(fun as i =>
@LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Machine as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Machine) cs j)
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Machine c) →
DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.Completed i (@List.take.{0} (Fin i.k) j ds) c)
(@LE.le.{0} Nat instLENat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) last.work
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 6) (instOfNatNat (nat_lit 6))) (@List.length.{0} (Fin i.k) ds)))
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 1000) (instOfNatNat (nat_lit 1000)))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) i.n i.k)
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.heapHeight i)
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) (@List.length.{0} (Fin i.k) ds)
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))))))))))) ∧ (((DecrAlmostLinearSSSP.Decremental.Subpolynomial DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.overhead) ∧ (∀ (i : DecrAlmostLinearSSSP.Decremental.Input),
i.Valid →
@LE.le.{0} Real Real.instLE
(@Nat.cast.{0} Real Real.instNatCast
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.heapHeight i)
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(@HMul.hMul.{0, 0, 0} Real Real Real (@instHMul.{0} Real Real.instMul)
(DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.overhead i.size)
(@Max.max.{0} Real Real.instMax (@OfNat.ofNat.{0} Real (nat_lit 1) (@One.toOfNat1.{0} Real Real.instOne))
(DecrAlmostLinearSSSP.Decremental.logarithm2 (@Nat.cast.{0} Real Real.instNatCast i.W)))))) ∧ ((∀ (i : DecrAlmostLinearSSSP.Decremental.Input),
i.Valid →
@LE.le.{0} Real Real.instLE i.accuracy
(@HDiv.hDiv.{0, 0, 0} Real Real Real (@instHDiv.{0} Real (@DivInvMonoid.toDiv.{0} Real Real.instDivInvMonoid))
(@OfNat.ofNat.{0} Real (nat_lit 1) (@One.toOfNat1.{0} Real Real.instOne))
(@Nat.cast.{0} Real Real.instNatCast i.size)) →
@LE.le.{0} Real Real.instLE
(@HMul.hMul.{0, 0, 0} Real Real Real (@instHMul.{0} Real Real.instMul)
(@HMul.hMul.{0, 0, 0} Real Real Real (@instHMul.{0} Real Real.instMul)
(@OfNat.ofNat.{0} Real (nat_lit 10000)
(@instOfNatAtLeastTwo.{0} Real (nat_lit 10000) Real.instNatCast
(@Nat.instAtLeastTwoHAddOfNat (@OfNat.ofNat.{0} Nat (nat_lit 9999) (instOfNatNat (nat_lit 9999)))
(@Nat.instNeZeroSucc (@OfNat.ofNat.{0} Nat (nat_lit 9998) (instOfNatNat (nat_lit 9998)))))))
(@HPow.hPow.{0, 0, 0} Real Nat Real
(@instHPow.{0, 0} Real Nat (@NPow.toPow.{0} Real (@Monoid.toNPow.{0} Real Real.instMonoid)))
(@Nat.cast.{0} Real Real.instNatCast i.size)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))))
(@Nat.cast.{0} Real Real.instNatCast
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.heapHeight i)
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))))
(@HMul.hMul.{0, 0, 0} Real Real Real (@instHMul.{0} Real Real.instMul)
(@HDiv.hDiv.{0, 0, 0} Real Real Real (@instHDiv.{0} Real (@DivInvMonoid.toDiv.{0} Real Real.instDivInvMonoid))
(@HMul.hMul.{0, 0, 0} Real Real Real (@instHMul.{0} Real Real.instMul)
(@HMul.hMul.{0, 0, 0} Real Real Real (@instHMul.{0} Real Real.instMul)
(@OfNat.ofNat.{0} Real (nat_lit 10000)
(@instOfNatAtLeastTwo.{0} Real (nat_lit 10000) Real.instNatCast
(@Nat.instAtLeastTwoHAddOfNat (@OfNat.ofNat.{0} Nat (nat_lit 9999) (instOfNatNat (nat_lit 9999)))
(@Nat.instNeZeroSucc (@OfNat.ofNat.{0} Nat (nat_lit 9998) (instOfNatNat (nat_lit 9998)))))))
(@Nat.cast.{0} Real Real.instNatCast i.size))
(DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.overhead i.size))
i.accuracy)
(@Max.max.{0} Real Real.instMax (@OfNat.ofNat.{0} Real (nat_lit 1) (@One.toOfNat1.{0} Real Real.instOne))
(DecrAlmostLinearSSSP.Decremental.logarithm2 (@Nat.cast.{0} Real Real.instNatCast i.W))))) ∧ ((∀ (i : DecrAlmostLinearSSSP.Decremental.Input),
i.Valid →
∀ (ds : List.{0} (Fin i.k)),
@DecrAlmostLinearSSSP.Decremental.Legal i.k ds →
@LE.le.{0} Nat instLENat
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 1000) (instOfNatNat (nat_lit 1000)))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) i.n i.k)
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.heapHeight i)
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) (@List.length.{0} (Fin i.k) ds)
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 10000) (instOfNatNat (nat_lit 10000)))
(@HPow.hPow.{0, 0, 0} Nat Nat Nat
(@instHPow.{0, 0} Nat Nat (@NPow.toPow.{0} Nat (@Monoid.toNPow.{0} Nat Nat.instMonoid))) i.size
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.heapHeight i)
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))) ∧ (∀ (i : DecrAlmostLinearSSSP.Decremental.Input),
i.Valid →
@LE.le.{0} Real Real.instLE i.accuracy
(@HDiv.hDiv.{0, 0, 0} Real Real Real (@instHDiv.{0} Real (@DivInvMonoid.toDiv.{0} Real Real.instDivInvMonoid))
(@OfNat.ofNat.{0} Real (nat_lit 1) (@One.toOfNat1.{0} Real Real.instOne))
(@Nat.cast.{0} Real Real.instNatCast i.size)) →
DecrAlmostLinearSSSP.Decremental.Maintains DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.hostProgram
(@OfNat.ofNat.{0} Real (nat_lit 10000)
(@instOfNatAtLeastTwo.{0} Real (nat_lit 10000) Real.instNatCast
(@Nat.instAtLeastTwoHAddOfNat (@OfNat.ofNat.{0} Nat (nat_lit 9999) (instOfNatNat (nat_lit 9999)))
(@Nat.instNeZeroSucc (@OfNat.ofNat.{0} Nat (nat_lit 9998) (instOfNatNat (nat_lit 9998)))))))
DecrAlmostLinearSSSP.Decremental.Exact.Dijkstra.overhead
(@OfNat.ofNat.{0} Nat (nat_lit 9) (instOfNatNat (nat_lit 9))) Bool.true i)))))))) := by sorry