Breadth-first search program and shortest-path result contract
DefinitionCLRS_BFS_ProgramThe concrete FIFO breadth-first search uses a read-only arrays-of-arrays graph, a distance sentinel of −1, a parent array, and an explicitly instrumented graph_work clock. The generated public Call relation fixes its operational meaning. Its postcondition requires a fresh result object and two distinct fresh arrays, shortest attained distances to exactly the reachable vertices, −1 at unreachable vertices, predecessor edges decreasing distance by one, and preservation of caller storage. A valid source is required by the open goals; there is no valid source in an empty graph. This bundle supplies the implementation and specification only.
import Definitions.Def_Algo2LeanLib_Modules
import Definitions.Def_CLRS_Graph_Input
set_option autoImplicit true
set_option backward.isDefEq.respectTransparency false
set_option backward.defeqAttrib.useBackward true
-- Generated by Algo2Lean 0.1.4 https://github.com/lunjiah/algo2lean
namespace Algo.«bfs»
open _root_.Algo2LeanGenerated
-- Independently compiled module; imported algorithms keep their own transitions.
namespace Algo2LeanGenerated
abbrev Ref__a2l_import_0_UnweightedGraph := Algo.«graph_input».Algo2LeanGenerated.Ref_UnweightedGraph
abbrev Ref_BFSResult := ObjectRef
abbrev is__a2l_import_0_UnweightedGraph := Algo.«graph_input».Algo2LeanGenerated.is_UnweightedGraph
abbrev create__a2l_import_0_UnweightedGraph := Algo.«graph_input».Algo2LeanGenerated.create_UnweightedGraph
abbrev field__a2l_import_0_UnweightedGraph_size := Algo.«graph_input».Algo2LeanGenerated.field_UnweightedGraph_size
abbrev set__a2l_import_0_UnweightedGraph_size := Algo.«graph_input».Algo2LeanGenerated.set_UnweightedGraph_size
abbrev field__a2l_import_0_UnweightedGraph_adj := Algo.«graph_input».Algo2LeanGenerated.field_UnweightedGraph_adj
abbrev set__a2l_import_0_UnweightedGraph_adj := Algo.«graph_input».Algo2LeanGenerated.set_UnweightedGraph_adj
abbrev field__a2l_import_0_UnweightedGraph_degree := Algo.«graph_input».Algo2LeanGenerated.field_UnweightedGraph_degree
abbrev set__a2l_import_0_UnweightedGraph_degree := Algo.«graph_input».Algo2LeanGenerated.set_UnweightedGraph_degree
-- Shallow class membership; fields and referenced objects are observed separately.
def is_BFSResult (h : Heap) (ref : Ref_BFSResult) : Prop :=
ref < h.nextObject ∧ h.objectClass ref = some "bfs.BFSResult"
instance (h : Heap) (ref : Ref_BFSResult) : Decidable (is_BFSResult h ref) :=
inferInstanceAs (Decidable (ref < h.nextObject ∧ h.objectClass ref = some "bfs.BFSResult"))
def field_BFSResult_distance (h : Heap) (ref : Ref_BFSResult) : Option SeqRef :=
if is_BFSResult h ref then (h.readField ref "distance").bind ObjectValue.asSeq else none
def set_BFSResult_distance (h : Heap) (ref : Ref_BFSResult) (value : SeqRef) : Heap :=
h.writeField ref "distance" (ObjectValue.seqValue value)
@[simp] theorem field_BFSResult_distance_set (h : Heap) (ref : Ref_BFSResult) (value : SeqRef)
(valid : is_BFSResult h ref) :
field_BFSResult_distance (set_BFSResult_distance h ref value) ref = some value := by
have valid' : is_BFSResult (set_BFSResult_distance h ref value) ref := by
simpa [set_BFSResult_distance, is_BFSResult] using valid
rw [field_BFSResult_distance, if_pos valid']
unfold set_BFSResult_distance
rw [Heap.readField_writeField_same h ref "distance" _ "bfs.BFSResult" valid.2]
rfl
def field_BFSResult_parent (h : Heap) (ref : Ref_BFSResult) : Option SeqRef :=
if is_BFSResult h ref then (h.readField ref "parent").bind ObjectValue.asSeq else none
def set_BFSResult_parent (h : Heap) (ref : Ref_BFSResult) (value : SeqRef) : Heap :=
h.writeField ref "parent" (ObjectValue.seqValue value)
@[simp] theorem field_BFSResult_parent_set (h : Heap) (ref : Ref_BFSResult) (value : SeqRef)
(valid : is_BFSResult h ref) :
field_BFSResult_parent (set_BFSResult_parent h ref value) ref = some value := by
have valid' : is_BFSResult (set_BFSResult_parent h ref value) ref := by
simpa [set_BFSResult_parent, is_BFSResult] using valid
rw [field_BFSResult_parent, if_pos valid']
unfold set_BFSResult_parent
rw [Heap.readField_writeField_same h ref "parent" _ "bfs.BFSResult" valid.2]
rfl
/-- Build input data directly; this helper does not execute `__init__`. -/
def create_BFSResult (h : Heap) (value_distance : SeqRef) (value_parent : SeqRef) : Heap × Ref_BFSResult :=
let ref := h.nextObject
let h := h.allocateObject "bfs.BFSResult"
let h := set_BFSResult_distance h ref value_distance
let h := set_BFSResult_parent h ref value_parent
(h, ref)
def seq_Seq_Int : SequenceType SeqRef where
name := "Seq[Int]"
encode := fun value => (ObjectValue.seqValue value)
decode := ObjectValue.asSeq
decode_encode := by intro value; rfl
structure State_BFSResult___init__ where
v0 : Ref_BFSResult := 0 -- self
t1 : Unit := () -- temporary
t2 : SeqRef := 0 -- temporary
t3 : Ref_BFSResult := 0 -- temporary
t4 : Int := 0 -- temporary
t5 : SeqRef := 0 -- temporary
t6 : Ref_BFSResult := 0 -- temporary
t7 : Int := 0 -- temporary
structure State_bfs where
v0 : Ref__a2l_import_0_UnweightedGraph := 0 -- graph
v1 : Int := 0 -- source
v2 : Ref_BFSResult := 0 -- result
v3 : Int := 0 -- vertex
v4 : SeqRef := 0 -- queue
v5 : Int := 0 -- head
v6 : Int := 0 -- tail
v7 : Int := 0 -- index
v8 : Int := 0 -- neighbor
t9 : Ref_BFSResult := 0 -- temporary
t10 : Bool := false -- temporary
t11 : Bool := false -- temporary
t12 : Bool := false -- temporary
t13 : SeqRef := 0 -- temporary
t14 : Int := 0 -- temporary
t15 : Bool := false -- temporary
t16 : Ref_BFSResult := 0 -- temporary
structure State_BFSResult where
v0 : Ref_BFSResult := 0 -- _instance
t1 : Ref_BFSResult := 0 -- temporary
t2 : Unit := () -- temporary
t3 : Ref_BFSResult := 0 -- temporary
t4 : Ref_BFSResult := 0 -- temporary
inductive Frame where
| invalid
| fn_BFSResult___init__ (pc : Nat) (state : State_BFSResult___init__)
| fn_bfs (pc : Nat) (state : State_bfs)
| fn_BFSResult (pc : Nat) (state : State_BFSResult)
inductive Result where
| fn_BFSResult___init__ (value : Unit)
| fn_bfs (value : Ref_BFSResult)
| fn_BFSResult (value : Ref_BFSResult)
abbrev Configuration := Algo2LeanCore.Config Heap (Frame) Result
abbrev Stack := Algo2LeanCore.Stack (Frame) Result
abbrev Transcript := List (Configuration)
inductive Step : Configuration → Configuration → Prop where
| BFSResult___init___pc1 (h : Heap) (s : State_BFSResult___init__) (stack : Stack) :
Step (.active h (Frame.fn_BFSResult___init__ 1 s) stack) (Algo2LeanCore.resumeConfig h (Result.fn_BFSResult___init__ (s.t1)) stack)
| BFSResult___init___pc2 (h : Heap) (s : State_BFSResult___init__) (stack : Stack) :
Step (.active h (Frame.fn_BFSResult___init__ 2 s) stack) (.active h (Frame.fn_BFSResult___init__ 1 { s with t1 := () }) stack)
| BFSResult___init___pc3 (h : Heap) (s : State_BFSResult___init__) (stack : Stack) (defined : (is_BFSResult h (s.t3))) :
Step (.active h (Frame.fn_BFSResult___init__ 3 s) stack) (.active (set_BFSResult_parent h (s.t3) (s.t2)) (Frame.fn_BFSResult___init__ 2 s) stack)
| BFSResult___init___pc4 (h : Heap) (s : State_BFSResult___init__) (stack : Stack) :
Step (.active h (Frame.fn_BFSResult___init__ 4 s) stack) (.active h (Frame.fn_BFSResult___init__ 3 { s with t3 := s.v0 }) stack)
| BFSResult___init___pc5 (h : Heap) (s : State_BFSResult___init__) (stack : Stack) :
Step (.active h (Frame.fn_BFSResult___init__ 5 s) stack) (.active (h.allocate (fun _ => s.t4)) (Frame.fn_BFSResult___init__ 4 { s with t2 := h.nextRef }) stack)
| BFSResult___init___pc6 (h : Heap) (s : State_BFSResult___init__) (stack : Stack) :
Step (.active h (Frame.fn_BFSResult___init__ 6 s) stack) (.active h (Frame.fn_BFSResult___init__ 5 { s with t4 := (-(1 : Int)) }) stack)
| BFSResult___init___pc7 (h : Heap) (s : State_BFSResult___init__) (stack : Stack) (defined : (is_BFSResult h (s.t6))) :
Step (.active h (Frame.fn_BFSResult___init__ 7 s) stack) (.active (set_BFSResult_distance h (s.t6) (s.t5)) (Frame.fn_BFSResult___init__ 6 s) stack)
| BFSResult___init___pc8 (h : Heap) (s : State_BFSResult___init__) (stack : Stack) :
Step (.active h (Frame.fn_BFSResult___init__ 8 s) stack) (.active h (Frame.fn_BFSResult___init__ 7 { s with t6 := s.v0 }) stack)
| BFSResult___init___pc9 (h : Heap) (s : State_BFSResult___init__) (stack : Stack) :
Step (.active h (Frame.fn_BFSResult___init__ 9 s) stack) (.active (h.allocate (fun _ => s.t7)) (Frame.fn_BFSResult___init__ 8 { s with t5 := h.nextRef }) stack)
| BFSResult___init___pc10 (h : Heap) (s : State_BFSResult___init__) (stack : Stack) :
Step (.active h (Frame.fn_BFSResult___init__ 10 s) stack) (.active h (Frame.fn_BFSResult___init__ 9 { s with t7 := (-(1 : Int)) }) stack)
| BFSResult___init___pc11 (h : Heap) (s : State_BFSResult___init__) (stack : Stack) :
Step (.active h (Frame.fn_BFSResult___init__ 11 s) stack) (.active (h.tick "graph_work" 1) (Frame.fn_BFSResult___init__ 10 s) stack)
| bfs_pc1 (h : Heap) (s : State_bfs) (stack : Stack) (defined : is_BFSResult h s.t9) :
Step (.active h (Frame.fn_bfs 1 s) stack) (Algo2LeanCore.resumeConfig h (Result.fn_bfs (s.t9)) stack)
| bfs_pc2 (h : Heap) (s : State_bfs) (stack : Stack) :
Step (.active h (Frame.fn_bfs 2 s) stack) (.active h (Frame.fn_bfs 1 { s with t9 := s.v2 }) stack)
| bfs_pc3 (h : Heap) (s : State_bfs) (stack : Stack) :
Step (.active h (Frame.fn_bfs 3 s) stack) (.active (h.tick "graph_work" 1) (Frame.fn_bfs 2 s) stack)
| bfs_pc4_true (h : Heap) (s : State_bfs) (stack : Stack) (condition : s.t10 = true) :
Step (.active h (Frame.fn_bfs 4 s) stack) (.active h (Frame.fn_bfs 24 s) stack)
| bfs_pc4_false (h : Heap) (s : State_bfs) (stack : Stack) (condition : s.t10 = false) :
Step (.active h (Frame.fn_bfs 4 s) stack) (.active h (Frame.fn_bfs 3 s) stack)
| bfs_pc5 (h : Heap) (s : State_bfs) (stack : Stack) :
Step (.active h (Frame.fn_bfs 5 s) stack) (.active h (Frame.fn_bfs 4 { s with t10 := (decide ((s.v5 < s.v6))) }) stack)
| bfs_pc6 (h : Heap) (s : State_bfs) (stack : Stack) :
Step (.active h (Frame.fn_bfs 6 s) stack) (.active (h.tick "graph_work" 1) (Frame.fn_bfs 5 s) stack)
| bfs_pc7_true (h : Heap) (s : State_bfs) (stack : Stack) (condition : s.t11 = true) :
Step (.active h (Frame.fn_bfs 7 s) stack) (.active h (Frame.fn_bfs 19 s) stack)
| bfs_pc7_false (h : Heap) (s : State_bfs) (stack : Stack) (condition : s.t11 = false) :
Step (.active h (Frame.fn_bfs 7 s) stack) (.active h (Frame.fn_bfs 6 s) stack)
| bfs_pc8 (h : Heap) (s : State_bfs) (stack : Stack) (defined : (((((field__a2l_import_0_UnweightedGraph_degree h (s.v0)).isSome = true))) ∧ (((field__a2l_import_0_UnweightedGraph_degree h (s.v0)).getD 0) < h.nextRef))) :
Step (.active h (Frame.fn_bfs 8 s) stack) (.active h (Frame.fn_bfs 7 { s with t11 := (decide ((s.v7 < (h.read ((field__a2l_import_0_UnweightedGraph_degree h (s.v0)).getD 0) s.v3)))) }) stack)
| bfs_pc9 (h : Heap) (s : State_bfs) (stack : Stack) :
Step (.active h (Frame.fn_bfs 9 s) stack) (.active (h.tick "graph_work" 1) (Frame.fn_bfs 8 s) stack)
| bfs_pc10 (h : Heap) (s : State_bfs) (stack : Stack) :
Step (.active h (Frame.fn_bfs 10 s) stack) (.active h (Frame.fn_bfs 9 { s with v7 := (s.v7 + (1 : Int)) }) stack)
| bfs_pc11 (h : Heap) (s : State_bfs) (stack : Stack) :
Step (.active h (Frame.fn_bfs 11 s) stack) (.active h (Frame.fn_bfs 10 { s with v6 := (s.v6 + (1 : Int)) }) stack)
| bfs_pc12 (h : Heap) (s : State_bfs) (stack : Stack) (defined : s.v4 < h.nextRef) :
Step (.active h (Frame.fn_bfs 12 s) stack) (.active (h.write s.v4 s.v6 s.v8) (Frame.fn_bfs 11 s) stack)
| bfs_pc13 (h : Heap) (s : State_bfs) (stack : Stack) (defined : (((((field_BFSResult_parent h (s.v2)).isSome = true)))) ∧ (((field_BFSResult_parent h (s.v2)).getD 0) < h.nextRef)) :
Step (.active h (Frame.fn_bfs 13 s) stack) (.active (h.write ((field_BFSResult_parent h (s.v2)).getD 0) s.v8 s.v3) (Frame.fn_bfs 12 s) stack)
| bfs_pc14 (h : Heap) (s : State_bfs) (stack : Stack) (defined : (((((((field_BFSResult_distance h (s.v2)).isSome = true))) ∧ (((field_BFSResult_distance h (s.v2)).getD 0) < h.nextRef))) ∧ ((((field_BFSResult_distance h (s.v2)).isSome = true)))) ∧ (((field_BFSResult_distance h (s.v2)).getD 0) < h.nextRef)) :
Step (.active h (Frame.fn_bfs 14 s) stack) (.active (h.write ((field_BFSResult_distance h (s.v2)).getD 0) s.v8 ((h.read ((field_BFSResult_distance h (s.v2)).getD 0) s.v3) + (1 : Int))) (Frame.fn_bfs 13 s) stack)
| bfs_pc15 (h : Heap) (s : State_bfs) (stack : Stack) :
Step (.active h (Frame.fn_bfs 15 s) stack) (.active (h.tick "graph_work" 1) (Frame.fn_bfs 14 s) stack)
| bfs_pc16_true (h : Heap) (s : State_bfs) (stack : Stack) (condition : s.t12 = true) :
Step (.active h (Frame.fn_bfs 16 s) stack) (.active h (Frame.fn_bfs 15 s) stack)
| bfs_pc16_false (h : Heap) (s : State_bfs) (stack : Stack) (condition : s.t12 = false) :
Step (.active h (Frame.fn_bfs 16 s) stack) (.active h (Frame.fn_bfs 10 s) stack)
| bfs_pc17 (h : Heap) (s : State_bfs) (stack : Stack) (defined : (((((field_BFSResult_distance h (s.v2)).isSome = true))) ∧ (((field_BFSResult_distance h (s.v2)).getD 0) < h.nextRef))) :
Step (.active h (Frame.fn_bfs 17 s) stack) (.active h (Frame.fn_bfs 16 { s with t12 := (decide (((h.read ((field_BFSResult_distance h (s.v2)).getD 0) s.v8) = (-(1 : Int))))) }) stack)
| bfs_pc18 (h : Heap) (s : State_bfs) (stack : Stack) (defined : (((((field__a2l_import_0_UnweightedGraph_adj h (s.v0)).isSome = true))) ∧ ((seq_Seq_Int.get h ((field__a2l_import_0_UnweightedGraph_adj h (s.v0)).getD 0) s.v3).isSome = true)) ∧ (((seq_Seq_Int.get h ((field__a2l_import_0_UnweightedGraph_adj h (s.v0)).getD 0) s.v3).getD 0) < h.nextRef)) :
Step (.active h (Frame.fn_bfs 18 s) stack) (.active h (Frame.fn_bfs 17 { s with v8 := (h.read ((seq_Seq_Int.get h ((field__a2l_import_0_UnweightedGraph_adj h (s.v0)).getD 0) s.v3).getD 0) s.v7) }) stack)
| bfs_pc19 (h : Heap) (s : State_bfs) (stack : Stack) :
Step (.active h (Frame.fn_bfs 19 s) stack) (.active (h.tick "graph_work" 1) (Frame.fn_bfs 18 s) stack)
| bfs_pc20 (h : Heap) (s : State_bfs) (stack : Stack) :
Step (.active h (Frame.fn_bfs 20 s) stack) (.active (h.tick "graph_work" 1) (Frame.fn_bfs 8 s) stack)
| bfs_pc21 (h : Heap) (s : State_bfs) (stack : Stack) :
Step (.active h (Frame.fn_bfs 21 s) stack) (.active h (Frame.fn_bfs 20 { s with v7 := (0 : Int) }) stack)
| bfs_pc22 (h : Heap) (s : State_bfs) (stack : Stack) :
Step (.active h (Frame.fn_bfs 22 s) stack) (.active h (Frame.fn_bfs 21 { s with v5 := (s.v5 + (1 : Int)) }) stack)
| bfs_pc23 (h : Heap) (s : State_bfs) (stack : Stack) (defined : (s.v4 < h.nextRef)) :
Step (.active h (Frame.fn_bfs 23 s) stack) (.active h (Frame.fn_bfs 22 { s with v3 := (h.read s.v4 s.v5) }) stack)
| bfs_pc24 (h : Heap) (s : State_bfs) (stack : Stack) :
Step (.active h (Frame.fn_bfs 24 s) stack) (.active (h.tick "graph_work" 1) (Frame.fn_bfs 23 s) stack)
| bfs_pc25 (h : Heap) (s : State_bfs) (stack : Stack) :
Step (.active h (Frame.fn_bfs 25 s) stack) (.active (h.tick "graph_work" 1) (Frame.fn_bfs 5 s) stack)
| bfs_pc26 (h : Heap) (s : State_bfs) (stack : Stack) (defined : (((((field_BFSResult_distance h (s.v2)).isSome = true)))) ∧ (((field_BFSResult_distance h (s.v2)).getD 0) < h.nextRef)) :
Step (.active h (Frame.fn_bfs 26 s) stack) (.active (h.write ((field_BFSResult_distance h (s.v2)).getD 0) s.v1 (0 : Int)) (Frame.fn_bfs 25 s) stack)
| bfs_pc27 (h : Heap) (s : State_bfs) (stack : Stack) (defined : s.v4 < h.nextRef) :
Step (.active h (Frame.fn_bfs 27 s) stack) (.active (h.write s.v4 (0 : Int) s.v1) (Frame.fn_bfs 26 s) stack)
| bfs_pc28 (h : Heap) (s : State_bfs) (stack : Stack) :
Step (.active h (Frame.fn_bfs 28 s) stack) (.active h (Frame.fn_bfs 27 { s with v6 := (1 : Int) }) stack)
| bfs_pc29 (h : Heap) (s : State_bfs) (stack : Stack) :
Step (.active h (Frame.fn_bfs 29 s) stack) (.active h (Frame.fn_bfs 28 { s with v5 := (0 : Int) }) stack)
| bfs_pc30 (h : Heap) (s : State_bfs) (stack : Stack) :
Step (.active h (Frame.fn_bfs 30 s) stack) (.active h (Frame.fn_bfs 29 { s with v4 := s.t13 }) stack)
| bfs_pc31 (h : Heap) (s : State_bfs) (stack : Stack) :
Step (.active h (Frame.fn_bfs 31 s) stack) (.active (h.allocate (fun _ => s.t14)) (Frame.fn_bfs 30 { s with t13 := h.nextRef }) stack)
| bfs_pc32 (h : Heap) (s : State_bfs) (stack : Stack) :
Step (.active h (Frame.fn_bfs 32 s) stack) (.active h (Frame.fn_bfs 31 { s with t14 := (-(1 : Int)) }) stack)
| bfs_pc33 (h : Heap) (s : State_bfs) (stack : Stack) :
Step (.active h (Frame.fn_bfs 33 s) stack) (.active (h.tick "graph_work" 1) (Frame.fn_bfs 32 s) stack)
| bfs_pc34_true (h : Heap) (s : State_bfs) (stack : Stack) (condition : s.t15 = true) :
Step (.active h (Frame.fn_bfs 34 s) stack) (.active h (Frame.fn_bfs 40 s) stack)
| bfs_pc34_false (h : Heap) (s : State_bfs) (stack : Stack) (condition : s.t15 = false) :
Step (.active h (Frame.fn_bfs 34 s) stack) (.active h (Frame.fn_bfs 33 s) stack)
| bfs_pc35 (h : Heap) (s : State_bfs) (stack : Stack) (defined : ((((field__a2l_import_0_UnweightedGraph_size h (s.v0)).isSome = true)))) :
Step (.active h (Frame.fn_bfs 35 s) stack) (.active h (Frame.fn_bfs 34 { s with t15 := (decide ((s.v3 < ((field__a2l_import_0_UnweightedGraph_size h (s.v0)).getD 0)))) }) stack)
| bfs_pc36 (h : Heap) (s : State_bfs) (stack : Stack) :
Step (.active h (Frame.fn_bfs 36 s) stack) (.active (h.tick "graph_work" 1) (Frame.fn_bfs 35 s) stack)
| bfs_pc37 (h : Heap) (s : State_bfs) (stack : Stack) :
Step (.active h (Frame.fn_bfs 37 s) stack) (.active h (Frame.fn_bfs 36 { s with v3 := (s.v3 + (1 : Int)) }) stack)
| bfs_pc38 (h : Heap) (s : State_bfs) (stack : Stack) (defined : (((((field_BFSResult_parent h (s.v2)).isSome = true)))) ∧ (((field_BFSResult_parent h (s.v2)).getD 0) < h.nextRef)) :
Step (.active h (Frame.fn_bfs 38 s) stack) (.active (h.write ((field_BFSResult_parent h (s.v2)).getD 0) s.v3 (-(1 : Int))) (Frame.fn_bfs 37 s) stack)
| bfs_pc39 (h : Heap) (s : State_bfs) (stack : Stack) (defined : (((((field_BFSResult_distance h (s.v2)).isSome = true)))) ∧ (((field_BFSResult_distance h (s.v2)).getD 0) < h.nextRef)) :
Step (.active h (Frame.fn_bfs 39 s) stack) (.active (h.write ((field_BFSResult_distance h (s.v2)).getD 0) s.v3 (-(1 : Int))) (Frame.fn_bfs 38 s) stack)
| bfs_pc40 (h : Heap) (s : State_bfs) (stack : Stack) :
Step (.active h (Frame.fn_bfs 40 s) stack) (.active (h.tick "graph_work" 1) (Frame.fn_bfs 39 s) stack)
| bfs_pc41 (h : Heap) (s : State_bfs) (stack : Stack) :
Step (.active h (Frame.fn_bfs 41 s) stack) (.active (h.tick "graph_work" 1) (Frame.fn_bfs 35 s) stack)
| bfs_pc42 (h : Heap) (s : State_bfs) (stack : Stack) :
Step (.active h (Frame.fn_bfs 42 s) stack) (.active h (Frame.fn_bfs 41 { s with v3 := (0 : Int) }) stack)
| bfs_pc43 (h : Heap) (s : State_bfs) (stack : Stack) :
Step (.active h (Frame.fn_bfs 43 s) stack) (.active h (Frame.fn_bfs 42 { s with v2 := s.t16 }) stack)
| bfs_pc44 (h : Heap) (s : State_bfs) (stack : Stack) :
Step (.active h (Frame.fn_bfs 44 s) stack) (.active h (Frame.fn_BFSResult 6 ({ } : State_BFSResult)) ((fun value => match value with | .fn_BFSResult result => (Frame.fn_bfs 43 { s with t16 := result }) | _ => .invalid) :: stack))
| bfs_pc45 (h : Heap) (s : State_bfs) (stack : Stack) :
Step (.active h (Frame.fn_bfs 45 s) stack) (.active (h.tick "graph_work" 1) (Frame.fn_bfs 44 s) stack)
| BFSResult_pc1 (h : Heap) (s : State_BFSResult) (stack : Stack) (defined : is_BFSResult h s.t1) :
Step (.active h (Frame.fn_BFSResult 1 s) stack) (Algo2LeanCore.resumeConfig h (Result.fn_BFSResult (s.t1)) stack)
| BFSResult_pc2 (h : Heap) (s : State_BFSResult) (stack : Stack) :
Step (.active h (Frame.fn_BFSResult 2 s) stack) (.active h (Frame.fn_BFSResult 1 { s with t1 := s.v0 }) stack)
| BFSResult_pc3 (h : Heap) (s : State_BFSResult) (stack : Stack) :
Step (.active h (Frame.fn_BFSResult 3 s) stack) (.active h (Frame.fn_BFSResult___init__ 11 ({ v0 := s.t3 } : State_BFSResult___init__)) ((fun value => match value with | .fn_BFSResult___init__ result => (Frame.fn_BFSResult 2 { s with t2 := result }) | _ => .invalid) :: stack))
| BFSResult_pc4 (h : Heap) (s : State_BFSResult) (stack : Stack) :
Step (.active h (Frame.fn_BFSResult 4 s) stack) (.active h (Frame.fn_BFSResult 3 { s with t3 := s.v0 }) stack)
| BFSResult_pc5 (h : Heap) (s : State_BFSResult) (stack : Stack) :
Step (.active h (Frame.fn_BFSResult 5 s) stack) (.active h (Frame.fn_BFSResult 4 { s with v0 := s.t4 }) stack)
| BFSResult_pc6 (h : Heap) (s : State_BFSResult) (stack : Stack) :
Step (.active h (Frame.fn_BFSResult 6 s) stack) (.active (h.allocateObject "bfs.BFSResult") (Frame.fn_BFSResult 5 { s with t4 := h.nextObject }) stack)
theorem terminal (h : Heap) (result : Result) :
Algo2LeanCore.Terminal Step (.done h result) := by
intro next transition
cases transition
end Algo2LeanGenerated
open Algo2LeanGenerated
def entry_BFSResult___init__ (input : Ref_BFSResult) : Frame :=
(Frame.fn_BFSResult___init__ 11 ({ v0 := input } : State_BFSResult___init__))
def BFSResult.__init__.ValidInput (h : Heap) (input : Ref_BFSResult) : Prop := is_BFSResult h input
def BFSResult.__init__.initial (h : Heap) (input : Ref_BFSResult) : Configuration :=
Algo2LeanCore.start h (Frame.fn_BFSResult___init__ 11 ({ v0 := input } : State_BFSResult___init__))
def BFSResult.__init__.Run (h : Heap) (input : Ref_BFSResult) (h' : Heap) (output : Unit) : Prop :=
_root_.Algo.«bfs».BFSResult.__init__.ValidInput h input ∧ Algo2LeanCore.Reaches Step (_root_.Algo.«bfs».BFSResult.__init__.initial h input) (.done h' (Result.fn_BFSResult___init__ output))
def BFSResult.__init__.ValidHeapTranscript (h : Heap) (input : Ref_BFSResult) (trace : Transcript) : Prop :=
_root_.Algo.«bfs».BFSResult.__init__.ValidInput h input ∧ ∃ final, Algo2LeanCore.Valid Step (_root_.Algo.«bfs».BFSResult.__init__.initial h input) trace final
def BFSResult.__init__.Call (h : Heap) (input : Ref_BFSResult) (h' : Heap) (output : Unit) : Prop :=
_root_.Algo.«bfs».BFSResult.__init__.ValidInput h input ∧ Algo2LeanCore.Summary Step h (Frame.fn_BFSResult___init__ 11 ({ v0 := input } : State_BFSResult___init__)) h' (Result.fn_BFSResult___init__ output)
-- Complete this function from the supplied local state, under any caller stack.
def BFSResult.__init__.CallFrom (state : Configuration) (finalHeap : Heap) (output : Unit) : Prop :=
match state with
| .active heap (Frame.fn_BFSResult___init__ pc locals) _ =>
Algo2LeanCore.Summary Step heap (Frame.fn_BFSResult___init__ pc locals) finalHeap (Result.fn_BFSResult___init__ output)
| _ => False
-- Object inputs carry their heap, preserving shared references and cycles.
def BFSResult.__init__.load (input : Heap × (Ref_BFSResult)) : Heap × (Ref_BFSResult) := input
def BFSResult.__init__.ValidTranscript (my_input : Heap × (Ref_BFSResult)) (trace : Transcript) : Prop :=
let loaded := _root_.Algo.«bfs».BFSResult.__init__.load my_input
_root_.Algo.«bfs».BFSResult.__init__.ValidHeapTranscript loaded.1 loaded.2 trace
def BFSResult.__init__.Returns (my_input : Heap × (Ref_BFSResult)) (my_output : Unit) : Prop :=
let loaded := _root_.Algo.«bfs».BFSResult.__init__.load my_input
∃ finalHeap, _root_.Algo.«bfs».BFSResult.__init__.Run loaded.1 loaded.2 finalHeap my_output
-- Output and clock increments from one completed execution.
def BFSResult.__init__.ReturnsWithCost (my_input : Heap × (Ref_BFSResult)) (my_output : Unit) (costs : Clocks) : Prop :=
let loaded := _root_.Algo.«bfs».BFSResult.__init__.load my_input
∃ finalHeap, _root_.Algo.«bfs».BFSResult.__init__.Run loaded.1 loaded.2 finalHeap my_output ∧ Heap.cost loaded.1 finalHeap = costs
theorem BFSResult.__init__.ReturnsWithCost.returns {input output costs}
(run : _root_.Algo.«bfs».BFSResult.__init__.ReturnsWithCost input output costs) : _root_.Algo.«bfs».BFSResult.__init__.Returns input output := by
obtain ⟨heap, execution, _⟩ := run
exact ⟨heap, execution⟩
theorem BFSResult.__init__.Returns.withCost {input output}
(run : _root_.Algo.«bfs».BFSResult.__init__.Returns input output) : ∃ costs, _root_.Algo.«bfs».BFSResult.__init__.ReturnsWithCost input output costs := by
obtain ⟨heap, execution⟩ := run
exact ⟨Heap.cost (_root_.Algo.«bfs».BFSResult.__init__.load input).1 heap, heap, execution, rfl⟩
theorem BFSResult.__init__.Call.run {before input after output}
(call : _root_.Algo.«bfs».BFSResult.__init__.Call before input after output) :
_root_.Algo.«bfs».BFSResult.__init__.Run before input after output :=
⟨call.1, call.2.root⟩
def entry_bfs (input : Ref__a2l_import_0_UnweightedGraph × Int) : Frame :=
(Frame.fn_bfs 45 ({ v0 := input.1, v1 := input.2 } : State_bfs))
def bfs.ValidInput (h : Heap) (input : Ref__a2l_import_0_UnweightedGraph × Int) : Prop := is__a2l_import_0_UnweightedGraph h input.1
def bfs.initial (h : Heap) (input : Ref__a2l_import_0_UnweightedGraph × Int) : Configuration :=
Algo2LeanCore.start h (Frame.fn_bfs 45 ({ v0 := input.1, v1 := input.2 } : State_bfs))
def bfs.Run (h : Heap) (input : Ref__a2l_import_0_UnweightedGraph × Int) (h' : Heap) (output : Ref_BFSResult) : Prop :=
_root_.Algo.«bfs».bfs.ValidInput h input ∧ Algo2LeanCore.Reaches Step (_root_.Algo.«bfs».bfs.initial h input) (.done h' (Result.fn_bfs output))
def bfs.ValidHeapTranscript (h : Heap) (input : Ref__a2l_import_0_UnweightedGraph × Int) (trace : Transcript) : Prop :=
_root_.Algo.«bfs».bfs.ValidInput h input ∧ ∃ final, Algo2LeanCore.Valid Step (_root_.Algo.«bfs».bfs.initial h input) trace final
def bfs.Call (h : Heap) (input : Ref__a2l_import_0_UnweightedGraph × Int) (h' : Heap) (output : Ref_BFSResult) : Prop :=
_root_.Algo.«bfs».bfs.ValidInput h input ∧ Algo2LeanCore.Summary Step h (Frame.fn_bfs 45 ({ v0 := input.1, v1 := input.2 } : State_bfs)) h' (Result.fn_bfs output)
-- Complete this function from the supplied local state, under any caller stack.
def bfs.CallFrom (state : Configuration) (finalHeap : Heap) (output : Ref_BFSResult) : Prop :=
match state with
| .active heap (Frame.fn_bfs pc locals) _ =>
Algo2LeanCore.Summary Step heap (Frame.fn_bfs pc locals) finalHeap (Result.fn_bfs output)
| _ => False
-- Object inputs carry their heap, preserving shared references and cycles.
def bfs.load (input : Heap × (Ref__a2l_import_0_UnweightedGraph × Int)) : Heap × (Ref__a2l_import_0_UnweightedGraph × Int) := input
def bfs.ValidTranscript (my_input : Heap × (Ref__a2l_import_0_UnweightedGraph × Int)) (trace : Transcript) : Prop :=
let loaded := _root_.Algo.«bfs».bfs.load my_input
_root_.Algo.«bfs».bfs.ValidHeapTranscript loaded.1 loaded.2 trace
def bfs.Returns (my_input : Heap × (Ref__a2l_import_0_UnweightedGraph × Int)) (my_output : Heap × (Ref_BFSResult)) : Prop :=
let loaded := _root_.Algo.«bfs».bfs.load my_input
_root_.Algo.«bfs».bfs.Run loaded.1 loaded.2 my_output.1 my_output.2
-- Output and clock increments from one completed execution.
def bfs.ReturnsWithCost (my_input : Heap × (Ref__a2l_import_0_UnweightedGraph × Int)) (my_output : Heap × (Ref_BFSResult)) (costs : Clocks) : Prop :=
let loaded := _root_.Algo.«bfs».bfs.load my_input
_root_.Algo.«bfs».bfs.Run loaded.1 loaded.2 my_output.1 my_output.2 ∧ Heap.cost loaded.1 my_output.1 = costs
theorem bfs.ReturnsWithCost.returns {input output costs}
(run : _root_.Algo.«bfs».bfs.ReturnsWithCost input output costs) : _root_.Algo.«bfs».bfs.Returns input output := by
obtain ⟨execution, _⟩ := run
exact execution
theorem bfs.Returns.withCost {input output}
(run : _root_.Algo.«bfs».bfs.Returns input output) : ∃ costs, _root_.Algo.«bfs».bfs.ReturnsWithCost input output costs := by
exact ⟨Heap.cost (_root_.Algo.«bfs».bfs.load input).1 output.1, run, rfl⟩
theorem bfs.Call.run {before input after output}
(call : _root_.Algo.«bfs».bfs.Call before input after output) :
_root_.Algo.«bfs».bfs.Run before input after output :=
⟨call.1, call.2.root⟩
def entry_BFSResult (_input : Unit) : Frame :=
(Frame.fn_BFSResult 6 ({ } : State_BFSResult))
def BFSResult.ValidInput (_h : Heap) (_input : Unit) : Prop := True
def BFSResult.initial (h : Heap) (_input : Unit) : Configuration :=
Algo2LeanCore.start h (Frame.fn_BFSResult 6 ({ } : State_BFSResult))
def BFSResult.Run (h : Heap) (input : Unit) (h' : Heap) (output : Ref_BFSResult) : Prop :=
_root_.Algo.«bfs».BFSResult.ValidInput h input ∧ Algo2LeanCore.Reaches Step (_root_.Algo.«bfs».BFSResult.initial h input) (.done h' (Result.fn_BFSResult output))
def BFSResult.ValidHeapTranscript (h : Heap) (input : Unit) (trace : Transcript) : Prop :=
_root_.Algo.«bfs».BFSResult.ValidInput h input ∧ ∃ final, Algo2LeanCore.Valid Step (_root_.Algo.«bfs».BFSResult.initial h input) trace final
def BFSResult.Call (h : Heap) (input : Unit) (h' : Heap) (output : Ref_BFSResult) : Prop :=
_root_.Algo.«bfs».BFSResult.ValidInput h input ∧ Algo2LeanCore.Summary Step h (Frame.fn_BFSResult 6 ({ } : State_BFSResult)) h' (Result.fn_BFSResult output)
-- Complete this function from the supplied local state, under any caller stack.
def BFSResult.CallFrom (state : Configuration) (finalHeap : Heap) (output : Ref_BFSResult) : Prop :=
match state with
| .active heap (Frame.fn_BFSResult pc locals) _ =>
Algo2LeanCore.Summary Step heap (Frame.fn_BFSResult pc locals) finalHeap (Result.fn_BFSResult output)
| _ => False
-- The value view gives each sequence input its own object.
def BFSResult.load (_input : Unit) : Heap × (Unit) :=
let h0 : Heap := {}
(h0, ())
def BFSResult.ValidTranscript (my_input : Unit) (trace : Transcript) : Prop :=
let loaded := _root_.Algo.«bfs».BFSResult.load my_input
_root_.Algo.«bfs».BFSResult.ValidHeapTranscript loaded.1 loaded.2 trace
def BFSResult.Returns (my_input : Unit) (my_output : Heap × (Ref_BFSResult)) : Prop :=
let loaded := _root_.Algo.«bfs».BFSResult.load my_input
_root_.Algo.«bfs».BFSResult.Run loaded.1 loaded.2 my_output.1 my_output.2
-- Output and clock increments from one completed execution.
def BFSResult.ReturnsWithCost (my_input : Unit) (my_output : Heap × (Ref_BFSResult)) (costs : Clocks) : Prop :=
let loaded := _root_.Algo.«bfs».BFSResult.load my_input
_root_.Algo.«bfs».BFSResult.Run loaded.1 loaded.2 my_output.1 my_output.2 ∧ Heap.cost loaded.1 my_output.1 = costs
theorem BFSResult.ReturnsWithCost.returns {input output costs}
(run : _root_.Algo.«bfs».BFSResult.ReturnsWithCost input output costs) : _root_.Algo.«bfs».BFSResult.Returns input output := by
obtain ⟨execution, _⟩ := run
exact execution
theorem BFSResult.Returns.withCost {input output}
(run : _root_.Algo.«bfs».BFSResult.Returns input output) : ∃ costs, _root_.Algo.«bfs».BFSResult.ReturnsWithCost input output costs := by
exact ⟨Heap.cost (_root_.Algo.«bfs».BFSResult.load input).1 output.1, run, rfl⟩
theorem BFSResult.Call.run {before input after output}
(call : _root_.Algo.«bfs».BFSResult.Call before input after output) :
_root_.Algo.«bfs».BFSResult.Run before input after output :=
⟨call.1, call.2.root⟩
end Algo.«bfs»
set_option autoImplicit false
namespace CLRS.BFS
open Algo2LeanGenerated CLRS.GraphTraversal
/-- Caller-facing BFS result over the initial mathematical graph. The fresh
distance and parent arrays describe shortest directed paths from the source.
Unreachable vertices have distance and parent -1. Reachable non-source vertices
have a predecessor edge and a distance exactly one larger than their parent's.
The input graph and every other previously allocated object, sequence, and
collection are preserved; entries outside the vertex range are unspecified. -/
def Post (before after : Heap) (result : ObjectRef) (g : Graph) (source : Int) : Prop :=
Algo.bfs.Algo2LeanGenerated.is_BFSResult after result ∧
FreshObject before after result ∧
Preserves before after ∧
∃ distance parent,
Algo.bfs.Algo2LeanGenerated.field_BFSResult_distance after result = some distance ∧
Algo.bfs.Algo2LeanGenerated.field_BFSResult_parent after result = some parent ∧
FreshArrays before after [distance, parent] ∧
after.read distance source = 0 ∧
after.read parent source = -1 ∧
∀ vertex, Vertex g vertex →
-1 ≤ after.read distance vertex ∧
(after.read distance vertex = -1 ↔ ¬ Reachable g source vertex) ∧
(0 ≤ after.read distance vertex →
Shortest g source vertex (after.read distance vertex).toNat) ∧
(after.read distance vertex = -1 → after.read parent vertex = -1) ∧
(vertex ≠ source → 0 ≤ after.read distance vertex →
Edge g (after.read parent vertex) vertex ∧
after.read distance (after.read parent vertex) + 1 = after.read distance vertex)
end CLRS.BFS
Read-back
What the Lean code literally says, in plain math · GPT-6 (Codex, independent fresh-context agent)
This bundle defines a heap transition system for a routine with an allocated unweighted-graph object reference and an integer source as input, together with result-object operations and a separate mathematical postcondition. A result object has class bfs.BFSResult and fields for two integer-sequence references, distance and parent; class membership itself only checks the class tag and that the object reference is allocated, and field readers separately check the appropriate stored value tags. The direct creation helper allocates an object and stores two supplied references without checking that those sequences are allocated or running the initializer. The generated result initializer, whose input condition is class membership, adds one graph_work tick, allocates two different total integer sequences initially equal to at every integer index, and stores their references as distance and parent. The result constructor accepts the unique unit input without any heap precondition, allocates an object, and executes that initializer. The BFS entry's own validity predicate checks only the graph object's allocated class tag; it does not itself require a represented graph or a source in range. The BFS transitions add an entry tick, construct the result, and loop through integers starting at zero while they are below the stored size, writing to both output sequences at each such index. They then allocate an internal queue sequence initially equal to everywhere, put the source at queue index zero, set its distance to zero, and set the head and tail indices to zero and one. While head is less than tail, they read the vertex at the head, increment the head, and scan integer row indices starting at zero while below that vertex's stored degree. Each scanned adjacency entry supplies a neighbor. If its distance is , they set its distance to the current vertex's distance plus one, set its parent to the current vertex, append it at the queue tail, and increment the tail. Otherwise they leave those entries unchanged. They increment the row index after each adjacency examination and eventually return the result object when the queue loop ends. Field accesses, decoded adjacency-row references, and integer-sequence accesses have the explicit tag and allocation side conditions shown in the transitions; if such a side condition fails, that transition is unavailable. Integer-sequence indexing itself has no bounds restriction because sequences are total functions on integers. Besides the result-initializer and entry ticks, the routine adds one tick for each initialization-loop test, each initialization-loop body, queue setup, each queue-loop test, each dequeued-vertex body, each adjacency-loop test, each examined adjacency occurrence, each newly discovered vertex, and the final return. Other transitions are not separately charged; this is an explicitly instrumented counter on unbounded mathematical integers and total sequences. A top-level run requires valid input and a finite transition sequence to a completed state. A call requires valid input and finite completion to the same heap and result under every suspended caller stack. A call from local state uses the corresponding active function frame and demands completion under every stack, without independently adding entry validity; other frame kinds make that predicate false. Valid transcripts may be finite prefixes and need not terminate. Loading a BFS or result-initializer input keeps its supplied heap; loading the unit-valued result constructor for its return predicates starts with the empty default heap. BFS and constructor return predicates include the final heap, while initializer returns existentially hide it. Their cost-bearing return predicates additionally equate the pointwise natural-number clock differences with the supplied cost function; the bundle proves the conversions between returns and existential cost-bearing returns, that calls yield runs, same-field setter facts, and that completed states have no successor. For arbitrary before and after heaps, result reference, mathematical graph with vertex integers , and integer source , the separate postcondition requires an allocated result-class object whose reference is at least the old object counter and below the new one, and requires preservation of the complete contents of every initially allocated integer sequence, object, and collection, nondecrease of allocation counters and graph_work, and unchanged values of all other clocks. There must exist distance and parent sequence references stored in the result's two fields; these references must be distinct, each at least the old sequence counter and strictly below the new one. If and denote their final integer contents, then and . Every vertex must satisfy ; if and only if no finite directed walk from to exists; whenever , there is a walk of length equal to the natural-number conversion of and this length is at most that of every walk from to ; implies ; and, whenever and , the value is a valid vertex with an edge to and . Walks permit repeated vertices and have valid-vertex zero-length walks. The postcondition by itself assumes neither graph representation nor source validity, and always specifies the two source entries even if the source lies outside the vertex range. Other out-of-range output entries, the identity of a parent among possible predecessors, and any extra new allocations are not constrained by this postcondition. The definitions do not themselves assert that a BFS execution exists or satisfies it.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.