Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Breadth-first search program and shortest-path result contract

Definition
CLRS_BFS_Program

by Chutong · Oct 14, 2026 · Mathlib 0df444a (Lean v4.33.1)

algo2leanalgorithmsclrsgraph-theoryrunning-timetextbook

The 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.

Definition code
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
Source
CLRS, Introduction to Algorithms, fourth edition (MIT Press, 2022), Chapter 20, §20.2. https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/ ; new arrays-of-arrays implementation compiled with Algo2Lean v0.1.4, https://www.algo2lean.com/versions/v0.1.4/ . Source filenames and full code are in the mission description.
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 −1-1−1 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 −1-1−1 to both output sequences at each such index. They then allocate an internal queue sequence initially equal to −1-1−1 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 −1-1−1, 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 ggg with vertex integers 0≤v<V0≤v<V0≤v<V, and integer source sss, 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 ddd and ppp denote their final integer contents, then d(s)=0d(s)=0d(s)=0 and p(s)=−1p(s)=-1p(s)=−1. Every vertex vvv must satisfy d(v)≥−1d(v)≥-1d(v)≥−1; d(v)=−1d(v)=-1d(v)=−1 if and only if no finite directed walk from sss to vvv exists; whenever d(v)≥0d(v)≥0d(v)≥0, there is a walk of length equal to the natural-number conversion of d(v)d(v)d(v) and this length is at most that of every walk from sss to vvv; d(v)=−1d(v)=-1d(v)=−1 implies p(v)=−1p(v)=-1p(v)=−1; and, whenever v≠sv≠sv=s and d(v)≥0d(v)≥0d(v)≥0, the value p(v)p(v)p(v) is a valid vertex with an edge to vvv and d(p(v))+1=d(v)d(p(v))+1=d(v)d(p(v))+1=d(v). 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.

Human review
  • Endorsed by Shuze Chen · Oct 15, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Chutong · Oct 15, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me