Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Depth-first search program, ordered forest, and timestamp specifications

Definition
CLRS_DFS_Program

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

algo2leanalgorithmsclrsgraph-theoryrunning-timetextbook

The concrete recursive depth-first search accepts either an arbitrary vertex-root permutation or constructs identity order. The generated Call interfaces describe these executions. A fresh result object contains six distinct fresh arrays for colors, parents, discovery and finish times, increasing finish order, and predecessor-tree labels. The mathematical forest contract includes edge-valid parents, distinct events in 1,…,2n, nested or disjoint intervals, ancestor equivalence, induced-white-path reachability, root-order priority, a finish-order permutation, and dense nonempty tree labels. These labels describe DFS trees, not strongly connected components. This bundle contains definitions and generated interfaces, with no DFS correctness or runtime proof.

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.«dfs»

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_DFSResult := 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_DFSResult (h : Heap) (ref : Ref_DFSResult) : Prop :=
  ref < h.nextObject ∧ h.objectClass ref = some "dfs.DFSResult"
instance (h : Heap) (ref : Ref_DFSResult) : Decidable (is_DFSResult h ref) :=
  inferInstanceAs (Decidable (ref < h.nextObject ∧ h.objectClass ref = some "dfs.DFSResult"))

def field_DFSResult_color (h : Heap) (ref : Ref_DFSResult) : Option SeqRef :=
  if is_DFSResult h ref then (h.readField ref "color").bind ObjectValue.asSeq else none
def set_DFSResult_color (h : Heap) (ref : Ref_DFSResult) (value : SeqRef) : Heap :=
  h.writeField ref "color" (ObjectValue.seqValue value)
@[simp] theorem field_DFSResult_color_set (h : Heap) (ref : Ref_DFSResult) (value : SeqRef)
    (valid : is_DFSResult h ref) :
    field_DFSResult_color (set_DFSResult_color h ref value) ref = some value := by
  have valid' : is_DFSResult (set_DFSResult_color h ref value) ref := by
    simpa [set_DFSResult_color, is_DFSResult] using valid
  rw [field_DFSResult_color, if_pos valid']
  unfold set_DFSResult_color
  rw [Heap.readField_writeField_same h ref "color" _ "dfs.DFSResult" valid.2]
  rfl

def field_DFSResult_parent (h : Heap) (ref : Ref_DFSResult) : Option SeqRef :=
  if is_DFSResult h ref then (h.readField ref "parent").bind ObjectValue.asSeq else none
def set_DFSResult_parent (h : Heap) (ref : Ref_DFSResult) (value : SeqRef) : Heap :=
  h.writeField ref "parent" (ObjectValue.seqValue value)
@[simp] theorem field_DFSResult_parent_set (h : Heap) (ref : Ref_DFSResult) (value : SeqRef)
    (valid : is_DFSResult h ref) :
    field_DFSResult_parent (set_DFSResult_parent h ref value) ref = some value := by
  have valid' : is_DFSResult (set_DFSResult_parent h ref value) ref := by
    simpa [set_DFSResult_parent, is_DFSResult] using valid
  rw [field_DFSResult_parent, if_pos valid']
  unfold set_DFSResult_parent
  rw [Heap.readField_writeField_same h ref "parent" _ "dfs.DFSResult" valid.2]
  rfl

def field_DFSResult_discover (h : Heap) (ref : Ref_DFSResult) : Option SeqRef :=
  if is_DFSResult h ref then (h.readField ref "discover").bind ObjectValue.asSeq else none
def set_DFSResult_discover (h : Heap) (ref : Ref_DFSResult) (value : SeqRef) : Heap :=
  h.writeField ref "discover" (ObjectValue.seqValue value)
@[simp] theorem field_DFSResult_discover_set (h : Heap) (ref : Ref_DFSResult) (value : SeqRef)
    (valid : is_DFSResult h ref) :
    field_DFSResult_discover (set_DFSResult_discover h ref value) ref = some value := by
  have valid' : is_DFSResult (set_DFSResult_discover h ref value) ref := by
    simpa [set_DFSResult_discover, is_DFSResult] using valid
  rw [field_DFSResult_discover, if_pos valid']
  unfold set_DFSResult_discover
  rw [Heap.readField_writeField_same h ref "discover" _ "dfs.DFSResult" valid.2]
  rfl

def field_DFSResult_finish (h : Heap) (ref : Ref_DFSResult) : Option SeqRef :=
  if is_DFSResult h ref then (h.readField ref "finish").bind ObjectValue.asSeq else none
def set_DFSResult_finish (h : Heap) (ref : Ref_DFSResult) (value : SeqRef) : Heap :=
  h.writeField ref "finish" (ObjectValue.seqValue value)
@[simp] theorem field_DFSResult_finish_set (h : Heap) (ref : Ref_DFSResult) (value : SeqRef)
    (valid : is_DFSResult h ref) :
    field_DFSResult_finish (set_DFSResult_finish h ref value) ref = some value := by
  have valid' : is_DFSResult (set_DFSResult_finish h ref value) ref := by
    simpa [set_DFSResult_finish, is_DFSResult] using valid
  rw [field_DFSResult_finish, if_pos valid']
  unfold set_DFSResult_finish
  rw [Heap.readField_writeField_same h ref "finish" _ "dfs.DFSResult" valid.2]
  rfl

def field_DFSResult_order (h : Heap) (ref : Ref_DFSResult) : Option SeqRef :=
  if is_DFSResult h ref then (h.readField ref "order").bind ObjectValue.asSeq else none
def set_DFSResult_order (h : Heap) (ref : Ref_DFSResult) (value : SeqRef) : Heap :=
  h.writeField ref "order" (ObjectValue.seqValue value)
@[simp] theorem field_DFSResult_order_set (h : Heap) (ref : Ref_DFSResult) (value : SeqRef)
    (valid : is_DFSResult h ref) :
    field_DFSResult_order (set_DFSResult_order h ref value) ref = some value := by
  have valid' : is_DFSResult (set_DFSResult_order h ref value) ref := by
    simpa [set_DFSResult_order, is_DFSResult] using valid
  rw [field_DFSResult_order, if_pos valid']
  unfold set_DFSResult_order
  rw [Heap.readField_writeField_same h ref "order" _ "dfs.DFSResult" valid.2]
  rfl

def field_DFSResult_component (h : Heap) (ref : Ref_DFSResult) : Option SeqRef :=
  if is_DFSResult h ref then (h.readField ref "component").bind ObjectValue.asSeq else none
def set_DFSResult_component (h : Heap) (ref : Ref_DFSResult) (value : SeqRef) : Heap :=
  h.writeField ref "component" (ObjectValue.seqValue value)
@[simp] theorem field_DFSResult_component_set (h : Heap) (ref : Ref_DFSResult) (value : SeqRef)
    (valid : is_DFSResult h ref) :
    field_DFSResult_component (set_DFSResult_component h ref value) ref = some value := by
  have valid' : is_DFSResult (set_DFSResult_component h ref value) ref := by
    simpa [set_DFSResult_component, is_DFSResult] using valid
  rw [field_DFSResult_component, if_pos valid']
  unfold set_DFSResult_component
  rw [Heap.readField_writeField_same h ref "component" _ "dfs.DFSResult" valid.2]
  rfl

def field_DFSResult_clock (h : Heap) (ref : Ref_DFSResult) : Option Int :=
  if is_DFSResult h ref then (h.readField ref "clock").bind ObjectValue.asInt else none
def set_DFSResult_clock (h : Heap) (ref : Ref_DFSResult) (value : Int) : Heap :=
  h.writeField ref "clock" (ObjectValue.intValue value)
@[simp] theorem field_DFSResult_clock_set (h : Heap) (ref : Ref_DFSResult) (value : Int)
    (valid : is_DFSResult h ref) :
    field_DFSResult_clock (set_DFSResult_clock h ref value) ref = some value := by
  have valid' : is_DFSResult (set_DFSResult_clock h ref value) ref := by
    simpa [set_DFSResult_clock, is_DFSResult] using valid
  rw [field_DFSResult_clock, if_pos valid']
  unfold set_DFSResult_clock
  rw [Heap.readField_writeField_same h ref "clock" _ "dfs.DFSResult" valid.2]
  rfl

def field_DFSResult_finished (h : Heap) (ref : Ref_DFSResult) : Option Int :=
  if is_DFSResult h ref then (h.readField ref "finished").bind ObjectValue.asInt else none
def set_DFSResult_finished (h : Heap) (ref : Ref_DFSResult) (value : Int) : Heap :=
  h.writeField ref "finished" (ObjectValue.intValue value)
@[simp] theorem field_DFSResult_finished_set (h : Heap) (ref : Ref_DFSResult) (value : Int)
    (valid : is_DFSResult h ref) :
    field_DFSResult_finished (set_DFSResult_finished h ref value) ref = some value := by
  have valid' : is_DFSResult (set_DFSResult_finished h ref value) ref := by
    simpa [set_DFSResult_finished, is_DFSResult] using valid
  rw [field_DFSResult_finished, if_pos valid']
  unfold set_DFSResult_finished
  rw [Heap.readField_writeField_same h ref "finished" _ "dfs.DFSResult" valid.2]
  rfl

def field_DFSResult_components (h : Heap) (ref : Ref_DFSResult) : Option Int :=
  if is_DFSResult h ref then (h.readField ref "components").bind ObjectValue.asInt else none
def set_DFSResult_components (h : Heap) (ref : Ref_DFSResult) (value : Int) : Heap :=
  h.writeField ref "components" (ObjectValue.intValue value)
@[simp] theorem field_DFSResult_components_set (h : Heap) (ref : Ref_DFSResult) (value : Int)
    (valid : is_DFSResult h ref) :
    field_DFSResult_components (set_DFSResult_components h ref value) ref = some value := by
  have valid' : is_DFSResult (set_DFSResult_components h ref value) ref := by
    simpa [set_DFSResult_components, is_DFSResult] using valid
  rw [field_DFSResult_components, if_pos valid']
  unfold set_DFSResult_components
  rw [Heap.readField_writeField_same h ref "components" _ "dfs.DFSResult" valid.2]
  rfl

/-- Build input data directly; this helper does not execute `__init__`. -/
def create_DFSResult (h : Heap) (value_color : SeqRef) (value_parent : SeqRef) (value_discover : SeqRef) (value_finish : SeqRef) (value_order : SeqRef) (value_component : SeqRef) (value_clock : Int) (value_finished : Int) (value_components : Int) : Heap × Ref_DFSResult :=
  let ref := h.nextObject
  let h := h.allocateObject "dfs.DFSResult"
  let h := set_DFSResult_color h ref value_color
  let h := set_DFSResult_parent h ref value_parent
  let h := set_DFSResult_discover h ref value_discover
  let h := set_DFSResult_finish h ref value_finish
  let h := set_DFSResult_order h ref value_order
  let h := set_DFSResult_component h ref value_component
  let h := set_DFSResult_clock h ref value_clock
  let h := set_DFSResult_finished h ref value_finished
  let h := set_DFSResult_components h ref value_components
  (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_DFSResult___init__ where
  v0 : Ref_DFSResult := 0 -- self
  t1 : Unit := () -- temporary
  t2 : SeqRef := 0 -- temporary
  t3 : Ref_DFSResult := 0 -- temporary
  t4 : Int := 0 -- temporary
  t5 : SeqRef := 0 -- temporary
  t6 : Ref_DFSResult := 0 -- temporary
  t7 : Int := 0 -- temporary
  t8 : SeqRef := 0 -- temporary
  t9 : Ref_DFSResult := 0 -- temporary
  t10 : Int := 0 -- temporary
  t11 : SeqRef := 0 -- temporary
  t12 : Ref_DFSResult := 0 -- temporary
  t13 : Int := 0 -- temporary
  t14 : SeqRef := 0 -- temporary
  t15 : Ref_DFSResult := 0 -- temporary
  t16 : Int := 0 -- temporary
  t17 : SeqRef := 0 -- temporary
  t18 : Ref_DFSResult := 0 -- temporary
  t19 : Int := 0 -- temporary

structure State_visit where
  v0 : Ref__a2l_import_0_UnweightedGraph := 0 -- graph
  v1 : Ref_DFSResult := 0 -- result
  v2 : Int := 0 -- u
  v3 : Int := 0 -- label
  v4 : SeqRef := 0 -- neighbors
  v5 : Int := 0 -- j
  v6 : Int := 0 -- v
  t7 : Unit := () -- temporary
  t8 : Ref_DFSResult := 0 -- temporary
  t9 : Int := 0 -- temporary
  t10 : Int := 0 -- temporary
  t11 : Ref_DFSResult := 0 -- temporary
  t12 : Int := 0 -- temporary
  t13 : Int := 0 -- temporary
  t14 : Bool := false -- temporary
  t15 : Bool := false -- temporary
  t16 : Unit := () -- temporary
  t17 : Ref__a2l_import_0_UnweightedGraph := 0 -- temporary
  t18 : Ref_DFSResult := 0 -- temporary
  t19 : Int := 0 -- temporary
  t20 : Int := 0 -- temporary
  t21 : Ref_DFSResult := 0 -- temporary
  t22 : Int := 0 -- temporary
  t23 : Int := 0 -- temporary

structure State_dfs_ordered where
  v0 : Ref__a2l_import_0_UnweightedGraph := 0 -- graph
  v1 : SeqRef := 0 -- order
  v2 : Ref_DFSResult := 0 -- result
  v3 : Int := 0 -- i
  v4 : Int := 0 -- u
  t5 : Ref_DFSResult := 0 -- temporary
  t6 : Bool := false -- temporary
  t7 : Bool := false -- temporary
  t8 : Ref_DFSResult := 0 -- temporary
  t9 : Int := 0 -- temporary
  t10 : Int := 0 -- temporary
  t11 : Unit := () -- temporary
  t12 : Ref__a2l_import_0_UnweightedGraph := 0 -- temporary
  t13 : Ref_DFSResult := 0 -- temporary
  t14 : Int := 0 -- temporary
  t15 : Int := 0 -- temporary
  t16 : Ref_DFSResult := 0 -- temporary

structure State_dfs where
  v0 : Ref__a2l_import_0_UnweightedGraph := 0 -- graph
  v1 : SeqRef := 0 -- order
  v2 : Int := 0 -- i
  t3 : Ref_DFSResult := 0 -- temporary
  t4 : Ref__a2l_import_0_UnweightedGraph := 0 -- temporary
  t5 : SeqRef := 0 -- temporary
  t6 : Bool := false -- temporary
  t7 : SeqRef := 0 -- temporary
  t8 : Int := 0 -- temporary

structure State_DFSResult where
  v0 : Ref_DFSResult := 0 -- _instance
  t1 : Ref_DFSResult := 0 -- temporary
  t2 : Unit := () -- temporary
  t3 : Ref_DFSResult := 0 -- temporary
  t4 : Ref_DFSResult := 0 -- temporary

inductive Frame where
  | invalid
  | fn_DFSResult___init__ (pc : Nat) (state : State_DFSResult___init__)
  | fn_visit (pc : Nat) (state : State_visit)
  | fn_dfs_ordered (pc : Nat) (state : State_dfs_ordered)
  | fn_dfs (pc : Nat) (state : State_dfs)
  | fn_DFSResult (pc : Nat) (state : State_DFSResult)

inductive Result where
  | fn_DFSResult___init__ (value : Unit)
  | fn_visit (value : Unit)
  | fn_dfs_ordered (value : Ref_DFSResult)
  | fn_dfs (value : Ref_DFSResult)
  | fn_DFSResult (value : Ref_DFSResult)

abbrev Configuration := Algo2LeanCore.Config Heap (Frame) Result
abbrev Stack := Algo2LeanCore.Stack (Frame) Result
abbrev Transcript := List (Configuration)

inductive Step : Configuration → Configuration → Prop where
  | DFSResult___init___pc1 (h : Heap) (s : State_DFSResult___init__) (stack : Stack) :
      Step (.active h (Frame.fn_DFSResult___init__ 1 s) stack) (Algo2LeanCore.resumeConfig h (Result.fn_DFSResult___init__ (s.t1)) stack)
  | DFSResult___init___pc2 (h : Heap) (s : State_DFSResult___init__) (stack : Stack) :
      Step (.active h (Frame.fn_DFSResult___init__ 2 s) stack) (.active h (Frame.fn_DFSResult___init__ 1 { s with t1 := () }) stack)
  | DFSResult___init___pc3 (h : Heap) (s : State_DFSResult___init__) (stack : Stack) (defined : (is_DFSResult h (s.v0))) :
      Step (.active h (Frame.fn_DFSResult___init__ 3 s) stack) (.active (set_DFSResult_components h (s.v0) ((0 : Int))) (Frame.fn_DFSResult___init__ 2 s) stack)
  | DFSResult___init___pc4 (h : Heap) (s : State_DFSResult___init__) (stack : Stack) (defined : (is_DFSResult h (s.v0))) :
      Step (.active h (Frame.fn_DFSResult___init__ 4 s) stack) (.active (set_DFSResult_finished h (s.v0) ((0 : Int))) (Frame.fn_DFSResult___init__ 3 s) stack)
  | DFSResult___init___pc5 (h : Heap) (s : State_DFSResult___init__) (stack : Stack) (defined : (is_DFSResult h (s.v0))) :
      Step (.active h (Frame.fn_DFSResult___init__ 5 s) stack) (.active (set_DFSResult_clock h (s.v0) ((0 : Int))) (Frame.fn_DFSResult___init__ 4 s) stack)
  | DFSResult___init___pc6 (h : Heap) (s : State_DFSResult___init__) (stack : Stack) (defined : (is_DFSResult h (s.t3))) :
      Step (.active h (Frame.fn_DFSResult___init__ 6 s) stack) (.active (set_DFSResult_component h (s.t3) (s.t2)) (Frame.fn_DFSResult___init__ 5 s) stack)
  | DFSResult___init___pc7 (h : Heap) (s : State_DFSResult___init__) (stack : Stack) :
      Step (.active h (Frame.fn_DFSResult___init__ 7 s) stack) (.active h (Frame.fn_DFSResult___init__ 6 { s with t3 := s.v0 }) stack)
  | DFSResult___init___pc8 (h : Heap) (s : State_DFSResult___init__) (stack : Stack) :
      Step (.active h (Frame.fn_DFSResult___init__ 8 s) stack) (.active (h.allocate (fun _ => s.t4)) (Frame.fn_DFSResult___init__ 7 { s with t2 := h.nextRef }) stack)
  | DFSResult___init___pc9 (h : Heap) (s : State_DFSResult___init__) (stack : Stack) :
      Step (.active h (Frame.fn_DFSResult___init__ 9 s) stack) (.active h (Frame.fn_DFSResult___init__ 8 { s with t4 := (-(1 : Int)) }) stack)
  | DFSResult___init___pc10 (h : Heap) (s : State_DFSResult___init__) (stack : Stack) (defined : (is_DFSResult h (s.t6))) :
      Step (.active h (Frame.fn_DFSResult___init__ 10 s) stack) (.active (set_DFSResult_order h (s.t6) (s.t5)) (Frame.fn_DFSResult___init__ 9 s) stack)
  | DFSResult___init___pc11 (h : Heap) (s : State_DFSResult___init__) (stack : Stack) :
      Step (.active h (Frame.fn_DFSResult___init__ 11 s) stack) (.active h (Frame.fn_DFSResult___init__ 10 { s with t6 := s.v0 }) stack)
  | DFSResult___init___pc12 (h : Heap) (s : State_DFSResult___init__) (stack : Stack) :
      Step (.active h (Frame.fn_DFSResult___init__ 12 s) stack) (.active (h.allocate (fun _ => s.t7)) (Frame.fn_DFSResult___init__ 11 { s with t5 := h.nextRef }) stack)
  | DFSResult___init___pc13 (h : Heap) (s : State_DFSResult___init__) (stack : Stack) :
      Step (.active h (Frame.fn_DFSResult___init__ 13 s) stack) (.active h (Frame.fn_DFSResult___init__ 12 { s with t7 := (-(1 : Int)) }) stack)
  | DFSResult___init___pc14 (h : Heap) (s : State_DFSResult___init__) (stack : Stack) (defined : (is_DFSResult h (s.t9))) :
      Step (.active h (Frame.fn_DFSResult___init__ 14 s) stack) (.active (set_DFSResult_finish h (s.t9) (s.t8)) (Frame.fn_DFSResult___init__ 13 s) stack)
  | DFSResult___init___pc15 (h : Heap) (s : State_DFSResult___init__) (stack : Stack) :
      Step (.active h (Frame.fn_DFSResult___init__ 15 s) stack) (.active h (Frame.fn_DFSResult___init__ 14 { s with t9 := s.v0 }) stack)
  | DFSResult___init___pc16 (h : Heap) (s : State_DFSResult___init__) (stack : Stack) :
      Step (.active h (Frame.fn_DFSResult___init__ 16 s) stack) (.active (h.allocate (fun _ => s.t10)) (Frame.fn_DFSResult___init__ 15 { s with t8 := h.nextRef }) stack)
  | DFSResult___init___pc17 (h : Heap) (s : State_DFSResult___init__) (stack : Stack) :
      Step (.active h (Frame.fn_DFSResult___init__ 17 s) stack) (.active h (Frame.fn_DFSResult___init__ 16 { s with t10 := (0 : Int) }) stack)
  | DFSResult___init___pc18 (h : Heap) (s : State_DFSResult___init__) (stack : Stack) (defined : (is_DFSResult h (s.t12))) :
      Step (.active h (Frame.fn_DFSResult___init__ 18 s) stack) (.active (set_DFSResult_discover h (s.t12) (s.t11)) (Frame.fn_DFSResult___init__ 17 s) stack)
  | DFSResult___init___pc19 (h : Heap) (s : State_DFSResult___init__) (stack : Stack) :
      Step (.active h (Frame.fn_DFSResult___init__ 19 s) stack) (.active h (Frame.fn_DFSResult___init__ 18 { s with t12 := s.v0 }) stack)
  | DFSResult___init___pc20 (h : Heap) (s : State_DFSResult___init__) (stack : Stack) :
      Step (.active h (Frame.fn_DFSResult___init__ 20 s) stack) (.active (h.allocate (fun _ => s.t13)) (Frame.fn_DFSResult___init__ 19 { s with t11 := h.nextRef }) stack)
  | DFSResult___init___pc21 (h : Heap) (s : State_DFSResult___init__) (stack : Stack) :
      Step (.active h (Frame.fn_DFSResult___init__ 21 s) stack) (.active h (Frame.fn_DFSResult___init__ 20 { s with t13 := (0 : Int) }) stack)
  | DFSResult___init___pc22 (h : Heap) (s : State_DFSResult___init__) (stack : Stack) (defined : (is_DFSResult h (s.t15))) :
      Step (.active h (Frame.fn_DFSResult___init__ 22 s) stack) (.active (set_DFSResult_parent h (s.t15) (s.t14)) (Frame.fn_DFSResult___init__ 21 s) stack)
  | DFSResult___init___pc23 (h : Heap) (s : State_DFSResult___init__) (stack : Stack) :
      Step (.active h (Frame.fn_DFSResult___init__ 23 s) stack) (.active h (Frame.fn_DFSResult___init__ 22 { s with t15 := s.v0 }) stack)
  | DFSResult___init___pc24 (h : Heap) (s : State_DFSResult___init__) (stack : Stack) :
      Step (.active h (Frame.fn_DFSResult___init__ 24 s) stack) (.active (h.allocate (fun _ => s.t16)) (Frame.fn_DFSResult___init__ 23 { s with t14 := h.nextRef }) stack)
  | DFSResult___init___pc25 (h : Heap) (s : State_DFSResult___init__) (stack : Stack) :
      Step (.active h (Frame.fn_DFSResult___init__ 25 s) stack) (.active h (Frame.fn_DFSResult___init__ 24 { s with t16 := (-(1 : Int)) }) stack)
  | DFSResult___init___pc26 (h : Heap) (s : State_DFSResult___init__) (stack : Stack) (defined : (is_DFSResult h (s.t18))) :
      Step (.active h (Frame.fn_DFSResult___init__ 26 s) stack) (.active (set_DFSResult_color h (s.t18) (s.t17)) (Frame.fn_DFSResult___init__ 25 s) stack)
  | DFSResult___init___pc27 (h : Heap) (s : State_DFSResult___init__) (stack : Stack) :
      Step (.active h (Frame.fn_DFSResult___init__ 27 s) stack) (.active h (Frame.fn_DFSResult___init__ 26 { s with t18 := s.v0 }) stack)
  | DFSResult___init___pc28 (h : Heap) (s : State_DFSResult___init__) (stack : Stack) :
      Step (.active h (Frame.fn_DFSResult___init__ 28 s) stack) (.active (h.allocate (fun _ => s.t19)) (Frame.fn_DFSResult___init__ 27 { s with t17 := h.nextRef }) stack)
  | DFSResult___init___pc29 (h : Heap) (s : State_DFSResult___init__) (stack : Stack) :
      Step (.active h (Frame.fn_DFSResult___init__ 29 s) stack) (.active h (Frame.fn_DFSResult___init__ 28 { s with t19 := (0 : Int) }) stack)
  | DFSResult___init___pc30 (h : Heap) (s : State_DFSResult___init__) (stack : Stack) :
      Step (.active h (Frame.fn_DFSResult___init__ 30 s) stack) (.active (h.tick "graph_work" 1) (Frame.fn_DFSResult___init__ 29 s) stack)
  | visit_pc1 (h : Heap) (s : State_visit) (stack : Stack) :
      Step (.active h (Frame.fn_visit 1 s) stack) (Algo2LeanCore.resumeConfig h (Result.fn_visit (s.t7)) stack)
  | visit_pc2 (h : Heap) (s : State_visit) (stack : Stack) :
      Step (.active h (Frame.fn_visit 2 s) stack) (.active h (Frame.fn_visit 1 { s with t7 := () }) stack)
  | visit_pc3 (h : Heap) (s : State_visit) (stack : Stack) (defined : (is_DFSResult h (s.t8))) :
      Step (.active h (Frame.fn_visit 3 s) stack) (.active (set_DFSResult_finished h (s.t8) ((s.t9 + s.t10))) (Frame.fn_visit 2 s) stack)
  | visit_pc4 (h : Heap) (s : State_visit) (stack : Stack) :
      Step (.active h (Frame.fn_visit 4 s) stack) (.active h (Frame.fn_visit 3 { s with t10 := (1 : Int) }) stack)
  | visit_pc5 (h : Heap) (s : State_visit) (stack : Stack) (defined : ((field_DFSResult_finished h (s.t8)).isSome = true)) :
      Step (.active h (Frame.fn_visit 5 s) stack) (.active h (Frame.fn_visit 4 { s with t9 := ((field_DFSResult_finished h (s.t8)).getD 0) }) stack)
  | visit_pc6 (h : Heap) (s : State_visit) (stack : Stack) :
      Step (.active h (Frame.fn_visit 6 s) stack) (.active h (Frame.fn_visit 5 { s with t8 := s.v1 }) stack)
  | visit_pc7 (h : Heap) (s : State_visit) (stack : Stack) (defined : (((((field_DFSResult_order h (s.v1)).isSome = true))) ∧ ((((field_DFSResult_finished h (s.v1)).isSome = true)))) ∧ (((field_DFSResult_order h (s.v1)).getD 0) < h.nextRef)) :
      Step (.active h (Frame.fn_visit 7 s) stack) (.active (h.write ((field_DFSResult_order h (s.v1)).getD 0) ((field_DFSResult_finished h (s.v1)).getD 0) s.v2) (Frame.fn_visit 6 s) stack)
  | visit_pc8 (h : Heap) (s : State_visit) (stack : Stack) (defined : (((((field_DFSResult_clock h (s.v1)).isSome = true))) ∧ ((((field_DFSResult_finish h (s.v1)).isSome = true)))) ∧ (((field_DFSResult_finish h (s.v1)).getD 0) < h.nextRef)) :
      Step (.active h (Frame.fn_visit 8 s) stack) (.active (h.write ((field_DFSResult_finish h (s.v1)).getD 0) s.v2 ((field_DFSResult_clock h (s.v1)).getD 0)) (Frame.fn_visit 7 s) stack)
  | visit_pc9 (h : Heap) (s : State_visit) (stack : Stack) (defined : (is_DFSResult h (s.t11))) :
      Step (.active h (Frame.fn_visit 9 s) stack) (.active (set_DFSResult_clock h (s.t11) ((s.t12 + s.t13))) (Frame.fn_visit 8 s) stack)
  | visit_pc10 (h : Heap) (s : State_visit) (stack : Stack) :
      Step (.active h (Frame.fn_visit 10 s) stack) (.active h (Frame.fn_visit 9 { s with t13 := (1 : Int) }) stack)
  | visit_pc11 (h : Heap) (s : State_visit) (stack : Stack) (defined : ((field_DFSResult_clock h (s.t11)).isSome = true)) :
      Step (.active h (Frame.fn_visit 11 s) stack) (.active h (Frame.fn_visit 10 { s with t12 := ((field_DFSResult_clock h (s.t11)).getD 0) }) stack)
  | visit_pc12 (h : Heap) (s : State_visit) (stack : Stack) :
      Step (.active h (Frame.fn_visit 12 s) stack) (.active h (Frame.fn_visit 11 { s with t11 := s.v1 }) stack)
  | visit_pc13 (h : Heap) (s : State_visit) (stack : Stack) (defined : (((((field_DFSResult_color h (s.v1)).isSome = true)))) ∧ (((field_DFSResult_color h (s.v1)).getD 0) < h.nextRef)) :
      Step (.active h (Frame.fn_visit 13 s) stack) (.active (h.write ((field_DFSResult_color h (s.v1)).getD 0) s.v2 (2 : Int)) (Frame.fn_visit 12 s) stack)
  | visit_pc14 (h : Heap) (s : State_visit) (stack : Stack) :
      Step (.active h (Frame.fn_visit 14 s) stack) (.active (h.tick "graph_work" 1) (Frame.fn_visit 13 s) stack)
  | visit_pc15_true (h : Heap) (s : State_visit) (stack : Stack) (condition : s.t14 = true) :
      Step (.active h (Frame.fn_visit 15 s) stack) (.active h (Frame.fn_visit 29 s) stack)
  | visit_pc15_false (h : Heap) (s : State_visit) (stack : Stack) (condition : s.t14 = false) :
      Step (.active h (Frame.fn_visit 15 s) stack) (.active h (Frame.fn_visit 14 s) stack)
  | visit_pc16 (h : Heap) (s : State_visit) (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_visit 16 s) stack) (.active h (Frame.fn_visit 15 { s with t14 := (decide ((s.v5 < (h.read ((field__a2l_import_0_UnweightedGraph_degree h (s.v0)).getD 0) s.v2)))) }) stack)
  | visit_pc17 (h : Heap) (s : State_visit) (stack : Stack) :
      Step (.active h (Frame.fn_visit 17 s) stack) (.active (h.tick "graph_work" 1) (Frame.fn_visit 16 s) stack)
  | visit_pc18 (h : Heap) (s : State_visit) (stack : Stack) :
      Step (.active h (Frame.fn_visit 18 s) stack) (.active h (Frame.fn_visit 17 { s with v5 := (s.v5 + (1 : Int)) }) stack)
  | visit_pc19 (h : Heap) (s : State_visit) (stack : Stack) :
      Step (.active h (Frame.fn_visit 19 s) stack) (.active h (Frame.fn_visit 40 ({ v0 := s.t17, v1 := s.t18, v2 := s.t19, v3 := s.t20 } : State_visit)) ((fun value => match value with | .fn_visit result => (Frame.fn_visit 18 { s with t16 := result }) | _ => .invalid) :: stack))
  | visit_pc20 (h : Heap) (s : State_visit) (stack : Stack) :
      Step (.active h (Frame.fn_visit 20 s) stack) (.active h (Frame.fn_visit 19 { s with t20 := s.v3 }) stack)
  | visit_pc21 (h : Heap) (s : State_visit) (stack : Stack) :
      Step (.active h (Frame.fn_visit 21 s) stack) (.active h (Frame.fn_visit 20 { s with t19 := s.v6 }) stack)
  | visit_pc22 (h : Heap) (s : State_visit) (stack : Stack) :
      Step (.active h (Frame.fn_visit 22 s) stack) (.active h (Frame.fn_visit 21 { s with t18 := s.v1 }) stack)
  | visit_pc23 (h : Heap) (s : State_visit) (stack : Stack) :
      Step (.active h (Frame.fn_visit 23 s) stack) (.active h (Frame.fn_visit 22 { s with t17 := s.v0 }) stack)
  | visit_pc24 (h : Heap) (s : State_visit) (stack : Stack) (defined : (((((field_DFSResult_parent h (s.v1)).isSome = true)))) ∧ (((field_DFSResult_parent h (s.v1)).getD 0) < h.nextRef)) :
      Step (.active h (Frame.fn_visit 24 s) stack) (.active (h.write ((field_DFSResult_parent h (s.v1)).getD 0) s.v6 s.v2) (Frame.fn_visit 23 s) stack)
  | visit_pc25 (h : Heap) (s : State_visit) (stack : Stack) :
      Step (.active h (Frame.fn_visit 25 s) stack) (.active (h.tick "graph_work" 1) (Frame.fn_visit 24 s) stack)
  | visit_pc26_true (h : Heap) (s : State_visit) (stack : Stack) (condition : s.t15 = true) :
      Step (.active h (Frame.fn_visit 26 s) stack) (.active h (Frame.fn_visit 25 s) stack)
  | visit_pc26_false (h : Heap) (s : State_visit) (stack : Stack) (condition : s.t15 = false) :
      Step (.active h (Frame.fn_visit 26 s) stack) (.active h (Frame.fn_visit 18 s) stack)
  | visit_pc27 (h : Heap) (s : State_visit) (stack : Stack) (defined : (((((field_DFSResult_color h (s.v1)).isSome = true))) ∧ (((field_DFSResult_color h (s.v1)).getD 0) < h.nextRef))) :
      Step (.active h (Frame.fn_visit 27 s) stack) (.active h (Frame.fn_visit 26 { s with t15 := (decide (((h.read ((field_DFSResult_color h (s.v1)).getD 0) s.v6) = (0 : Int)))) }) stack)
  | visit_pc28 (h : Heap) (s : State_visit) (stack : Stack) (defined : (s.v4 < h.nextRef)) :
      Step (.active h (Frame.fn_visit 28 s) stack) (.active h (Frame.fn_visit 27 { s with v6 := (h.read s.v4 s.v5) }) stack)
  | visit_pc29 (h : Heap) (s : State_visit) (stack : Stack) :
      Step (.active h (Frame.fn_visit 29 s) stack) (.active (h.tick "graph_work" 1) (Frame.fn_visit 28 s) stack)
  | visit_pc30 (h : Heap) (s : State_visit) (stack : Stack) :
      Step (.active h (Frame.fn_visit 30 s) stack) (.active (h.tick "graph_work" 1) (Frame.fn_visit 16 s) stack)
  | visit_pc31 (h : Heap) (s : State_visit) (stack : Stack) :
      Step (.active h (Frame.fn_visit 31 s) stack) (.active h (Frame.fn_visit 30 { s with v5 := (0 : Int) }) stack)
  | visit_pc32 (h : Heap) (s : State_visit) (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.v2).isSome = true)) :
      Step (.active h (Frame.fn_visit 32 s) stack) (.active h (Frame.fn_visit 31 { s with v4 := ((seq_Seq_Int.get h ((field__a2l_import_0_UnweightedGraph_adj h (s.v0)).getD 0) s.v2).getD 0) }) stack)
  | visit_pc33 (h : Heap) (s : State_visit) (stack : Stack) (defined : (((((field_DFSResult_component h (s.v1)).isSome = true)))) ∧ (((field_DFSResult_component h (s.v1)).getD 0) < h.nextRef)) :
      Step (.active h (Frame.fn_visit 33 s) stack) (.active (h.write ((field_DFSResult_component h (s.v1)).getD 0) s.v2 s.v3) (Frame.fn_visit 32 s) stack)
  | visit_pc34 (h : Heap) (s : State_visit) (stack : Stack) (defined : (((((field_DFSResult_color h (s.v1)).isSome = true)))) ∧ (((field_DFSResult_color h (s.v1)).getD 0) < h.nextRef)) :
      Step (.active h (Frame.fn_visit 34 s) stack) (.active (h.write ((field_DFSResult_color h (s.v1)).getD 0) s.v2 (1 : Int)) (Frame.fn_visit 33 s) stack)
  | visit_pc35 (h : Heap) (s : State_visit) (stack : Stack) (defined : (((((field_DFSResult_clock h (s.v1)).isSome = true))) ∧ ((((field_DFSResult_discover h (s.v1)).isSome = true)))) ∧ (((field_DFSResult_discover h (s.v1)).getD 0) < h.nextRef)) :
      Step (.active h (Frame.fn_visit 35 s) stack) (.active (h.write ((field_DFSResult_discover h (s.v1)).getD 0) s.v2 ((field_DFSResult_clock h (s.v1)).getD 0)) (Frame.fn_visit 34 s) stack)
  | visit_pc36 (h : Heap) (s : State_visit) (stack : Stack) (defined : (is_DFSResult h (s.t21))) :
      Step (.active h (Frame.fn_visit 36 s) stack) (.active (set_DFSResult_clock h (s.t21) ((s.t22 + s.t23))) (Frame.fn_visit 35 s) stack)
  | visit_pc37 (h : Heap) (s : State_visit) (stack : Stack) :
      Step (.active h (Frame.fn_visit 37 s) stack) (.active h (Frame.fn_visit 36 { s with t23 := (1 : Int) }) stack)
  | visit_pc38 (h : Heap) (s : State_visit) (stack : Stack) (defined : ((field_DFSResult_clock h (s.t21)).isSome = true)) :
      Step (.active h (Frame.fn_visit 38 s) stack) (.active h (Frame.fn_visit 37 { s with t22 := ((field_DFSResult_clock h (s.t21)).getD 0) }) stack)
  | visit_pc39 (h : Heap) (s : State_visit) (stack : Stack) :
      Step (.active h (Frame.fn_visit 39 s) stack) (.active h (Frame.fn_visit 38 { s with t21 := s.v1 }) stack)
  | visit_pc40 (h : Heap) (s : State_visit) (stack : Stack) :
      Step (.active h (Frame.fn_visit 40 s) stack) (.active (h.tick "graph_work" 1) (Frame.fn_visit 39 s) stack)
  | dfs_ordered_pc1 (h : Heap) (s : State_dfs_ordered) (stack : Stack) (defined : is_DFSResult h s.t5) :
      Step (.active h (Frame.fn_dfs_ordered 1 s) stack) (Algo2LeanCore.resumeConfig h (Result.fn_dfs_ordered (s.t5)) stack)
  | dfs_ordered_pc2 (h : Heap) (s : State_dfs_ordered) (stack : Stack) :
      Step (.active h (Frame.fn_dfs_ordered 2 s) stack) (.active h (Frame.fn_dfs_ordered 1 { s with t5 := s.v2 }) stack)
  | dfs_ordered_pc3 (h : Heap) (s : State_dfs_ordered) (stack : Stack) :
      Step (.active h (Frame.fn_dfs_ordered 3 s) stack) (.active (h.tick "graph_work" 1) (Frame.fn_dfs_ordered 2 s) stack)
  | dfs_ordered_pc4_true (h : Heap) (s : State_dfs_ordered) (stack : Stack) (condition : s.t6 = true) :
      Step (.active h (Frame.fn_dfs_ordered 4 s) stack) (.active h (Frame.fn_dfs_ordered 21 s) stack)
  | dfs_ordered_pc4_false (h : Heap) (s : State_dfs_ordered) (stack : Stack) (condition : s.t6 = false) :
      Step (.active h (Frame.fn_dfs_ordered 4 s) stack) (.active h (Frame.fn_dfs_ordered 3 s) stack)
  | dfs_ordered_pc5 (h : Heap) (s : State_dfs_ordered) (stack : Stack) (defined : ((((field__a2l_import_0_UnweightedGraph_size h (s.v0)).isSome = true)))) :
      Step (.active h (Frame.fn_dfs_ordered 5 s) stack) (.active h (Frame.fn_dfs_ordered 4 { s with t6 := (decide ((s.v3 < ((field__a2l_import_0_UnweightedGraph_size h (s.v0)).getD 0)))) }) stack)
  | dfs_ordered_pc6 (h : Heap) (s : State_dfs_ordered) (stack : Stack) :
      Step (.active h (Frame.fn_dfs_ordered 6 s) stack) (.active (h.tick "graph_work" 1) (Frame.fn_dfs_ordered 5 s) stack)
  | dfs_ordered_pc7 (h : Heap) (s : State_dfs_ordered) (stack : Stack) :
      Step (.active h (Frame.fn_dfs_ordered 7 s) stack) (.active h (Frame.fn_dfs_ordered 6 { s with v3 := (s.v3 + (1 : Int)) }) stack)
  | dfs_ordered_pc8 (h : Heap) (s : State_dfs_ordered) (stack : Stack) (defined : (is_DFSResult h (s.t8))) :
      Step (.active h (Frame.fn_dfs_ordered 8 s) stack) (.active (set_DFSResult_components h (s.t8) ((s.t9 + s.t10))) (Frame.fn_dfs_ordered 7 s) stack)
  | dfs_ordered_pc9 (h : Heap) (s : State_dfs_ordered) (stack : Stack) :
      Step (.active h (Frame.fn_dfs_ordered 9 s) stack) (.active h (Frame.fn_dfs_ordered 8 { s with t10 := (1 : Int) }) stack)
  | dfs_ordered_pc10 (h : Heap) (s : State_dfs_ordered) (stack : Stack) (defined : ((field_DFSResult_components h (s.t8)).isSome = true)) :
      Step (.active h (Frame.fn_dfs_ordered 10 s) stack) (.active h (Frame.fn_dfs_ordered 9 { s with t9 := ((field_DFSResult_components h (s.t8)).getD 0) }) stack)
  | dfs_ordered_pc11 (h : Heap) (s : State_dfs_ordered) (stack : Stack) :
      Step (.active h (Frame.fn_dfs_ordered 11 s) stack) (.active h (Frame.fn_dfs_ordered 10 { s with t8 := s.v2 }) stack)
  | dfs_ordered_pc12 (h : Heap) (s : State_dfs_ordered) (stack : Stack) :
      Step (.active h (Frame.fn_dfs_ordered 12 s) stack) (.active h (Frame.fn_visit 40 ({ v0 := s.t12, v1 := s.t13, v2 := s.t14, v3 := s.t15 } : State_visit)) ((fun value => match value with | .fn_visit result => (Frame.fn_dfs_ordered 11 { s with t11 := result }) | _ => .invalid) :: stack))
  | dfs_ordered_pc13 (h : Heap) (s : State_dfs_ordered) (stack : Stack) (defined : (((field_DFSResult_components h (s.v2)).isSome = true))) :
      Step (.active h (Frame.fn_dfs_ordered 13 s) stack) (.active h (Frame.fn_dfs_ordered 12 { s with t15 := ((field_DFSResult_components h (s.v2)).getD 0) }) stack)
  | dfs_ordered_pc14 (h : Heap) (s : State_dfs_ordered) (stack : Stack) :
      Step (.active h (Frame.fn_dfs_ordered 14 s) stack) (.active h (Frame.fn_dfs_ordered 13 { s with t14 := s.v4 }) stack)
  | dfs_ordered_pc15 (h : Heap) (s : State_dfs_ordered) (stack : Stack) :
      Step (.active h (Frame.fn_dfs_ordered 15 s) stack) (.active h (Frame.fn_dfs_ordered 14 { s with t13 := s.v2 }) stack)
  | dfs_ordered_pc16 (h : Heap) (s : State_dfs_ordered) (stack : Stack) :
      Step (.active h (Frame.fn_dfs_ordered 16 s) stack) (.active h (Frame.fn_dfs_ordered 15 { s with t12 := s.v0 }) stack)
  | dfs_ordered_pc17 (h : Heap) (s : State_dfs_ordered) (stack : Stack) :
      Step (.active h (Frame.fn_dfs_ordered 17 s) stack) (.active (h.tick "graph_work" 1) (Frame.fn_dfs_ordered 16 s) stack)
  | dfs_ordered_pc18_true (h : Heap) (s : State_dfs_ordered) (stack : Stack) (condition : s.t7 = true) :
      Step (.active h (Frame.fn_dfs_ordered 18 s) stack) (.active h (Frame.fn_dfs_ordered 17 s) stack)
  | dfs_ordered_pc18_false (h : Heap) (s : State_dfs_ordered) (stack : Stack) (condition : s.t7 = false) :
      Step (.active h (Frame.fn_dfs_ordered 18 s) stack) (.active h (Frame.fn_dfs_ordered 7 s) stack)
  | dfs_ordered_pc19 (h : Heap) (s : State_dfs_ordered) (stack : Stack) (defined : (((((field_DFSResult_color h (s.v2)).isSome = true))) ∧ (((field_DFSResult_color h (s.v2)).getD 0) < h.nextRef))) :
      Step (.active h (Frame.fn_dfs_ordered 19 s) stack) (.active h (Frame.fn_dfs_ordered 18 { s with t7 := (decide (((h.read ((field_DFSResult_color h (s.v2)).getD 0) s.v4) = (0 : Int)))) }) stack)
  | dfs_ordered_pc20 (h : Heap) (s : State_dfs_ordered) (stack : Stack) (defined : (s.v1 < h.nextRef)) :
      Step (.active h (Frame.fn_dfs_ordered 20 s) stack) (.active h (Frame.fn_dfs_ordered 19 { s with v4 := (h.read s.v1 s.v3) }) stack)
  | dfs_ordered_pc21 (h : Heap) (s : State_dfs_ordered) (stack : Stack) :
      Step (.active h (Frame.fn_dfs_ordered 21 s) stack) (.active (h.tick "graph_work" 1) (Frame.fn_dfs_ordered 20 s) stack)
  | dfs_ordered_pc22 (h : Heap) (s : State_dfs_ordered) (stack : Stack) :
      Step (.active h (Frame.fn_dfs_ordered 22 s) stack) (.active (h.tick "graph_work" 1) (Frame.fn_dfs_ordered 5 s) stack)
  | dfs_ordered_pc23 (h : Heap) (s : State_dfs_ordered) (stack : Stack) :
      Step (.active h (Frame.fn_dfs_ordered 23 s) stack) (.active h (Frame.fn_dfs_ordered 22 { s with v3 := (0 : Int) }) stack)
  | dfs_ordered_pc24 (h : Heap) (s : State_dfs_ordered) (stack : Stack) :
      Step (.active h (Frame.fn_dfs_ordered 24 s) stack) (.active h (Frame.fn_dfs_ordered 23 { s with v2 := s.t16 }) stack)
  | dfs_ordered_pc25 (h : Heap) (s : State_dfs_ordered) (stack : Stack) :
      Step (.active h (Frame.fn_dfs_ordered 25 s) stack) (.active h (Frame.fn_DFSResult 6 ({  } : State_DFSResult)) ((fun value => match value with | .fn_DFSResult result => (Frame.fn_dfs_ordered 24 { s with t16 := result }) | _ => .invalid) :: stack))
  | dfs_ordered_pc26 (h : Heap) (s : State_dfs_ordered) (stack : Stack) :
      Step (.active h (Frame.fn_dfs_ordered 26 s) stack) (.active (h.tick "graph_work" 1) (Frame.fn_dfs_ordered 25 s) stack)
  | dfs_pc1 (h : Heap) (s : State_dfs) (stack : Stack) (defined : is_DFSResult h s.t3) :
      Step (.active h (Frame.fn_dfs 1 s) stack) (Algo2LeanCore.resumeConfig h (Result.fn_dfs (s.t3)) stack)
  | dfs_pc2 (h : Heap) (s : State_dfs) (stack : Stack) :
      Step (.active h (Frame.fn_dfs 2 s) stack) (.active h (Frame.fn_dfs_ordered 26 ({ v0 := s.t4, v1 := s.t5 } : State_dfs_ordered)) ((fun value => match value with | .fn_dfs_ordered result => (Frame.fn_dfs 1 { s with t3 := result }) | _ => .invalid) :: stack))
  | dfs_pc3 (h : Heap) (s : State_dfs) (stack : Stack) :
      Step (.active h (Frame.fn_dfs 3 s) stack) (.active h (Frame.fn_dfs 2 { s with t5 := s.v1 }) stack)
  | dfs_pc4 (h : Heap) (s : State_dfs) (stack : Stack) :
      Step (.active h (Frame.fn_dfs 4 s) stack) (.active h (Frame.fn_dfs 3 { s with t4 := s.v0 }) stack)
  | dfs_pc5 (h : Heap) (s : State_dfs) (stack : Stack) :
      Step (.active h (Frame.fn_dfs 5 s) stack) (.active (h.tick "graph_work" 1) (Frame.fn_dfs 4 s) stack)
  | dfs_pc6_true (h : Heap) (s : State_dfs) (stack : Stack) (condition : s.t6 = true) :
      Step (.active h (Frame.fn_dfs 6 s) stack) (.active h (Frame.fn_dfs 11 s) stack)
  | dfs_pc6_false (h : Heap) (s : State_dfs) (stack : Stack) (condition : s.t6 = false) :
      Step (.active h (Frame.fn_dfs 6 s) stack) (.active h (Frame.fn_dfs 5 s) stack)
  | dfs_pc7 (h : Heap) (s : State_dfs) (stack : Stack) (defined : ((((field__a2l_import_0_UnweightedGraph_size h (s.v0)).isSome = true)))) :
      Step (.active h (Frame.fn_dfs 7 s) stack) (.active h (Frame.fn_dfs 6 { s with t6 := (decide ((s.v2 < ((field__a2l_import_0_UnweightedGraph_size h (s.v0)).getD 0)))) }) stack)
  | dfs_pc8 (h : Heap) (s : State_dfs) (stack : Stack) :
      Step (.active h (Frame.fn_dfs 8 s) stack) (.active (h.tick "graph_work" 1) (Frame.fn_dfs 7 s) stack)
  | dfs_pc9 (h : Heap) (s : State_dfs) (stack : Stack) :
      Step (.active h (Frame.fn_dfs 9 s) stack) (.active h (Frame.fn_dfs 8 { s with v2 := (s.v2 + (1 : Int)) }) stack)
  | dfs_pc10 (h : Heap) (s : State_dfs) (stack : Stack) (defined : s.v1 < h.nextRef) :
      Step (.active h (Frame.fn_dfs 10 s) stack) (.active (h.write s.v1 s.v2 s.v2) (Frame.fn_dfs 9 s) stack)
  | dfs_pc11 (h : Heap) (s : State_dfs) (stack : Stack) :
      Step (.active h (Frame.fn_dfs 11 s) stack) (.active (h.tick "graph_work" 1) (Frame.fn_dfs 10 s) stack)
  | dfs_pc12 (h : Heap) (s : State_dfs) (stack : Stack) :
      Step (.active h (Frame.fn_dfs 12 s) stack) (.active (h.tick "graph_work" 1) (Frame.fn_dfs 7 s) stack)
  | dfs_pc13 (h : Heap) (s : State_dfs) (stack : Stack) :
      Step (.active h (Frame.fn_dfs 13 s) stack) (.active h (Frame.fn_dfs 12 { s with v2 := (0 : Int) }) stack)
  | dfs_pc14 (h : Heap) (s : State_dfs) (stack : Stack) :
      Step (.active h (Frame.fn_dfs 14 s) stack) (.active h (Frame.fn_dfs 13 { s with v1 := s.t7 }) stack)
  | dfs_pc15 (h : Heap) (s : State_dfs) (stack : Stack) :
      Step (.active h (Frame.fn_dfs 15 s) stack) (.active (h.allocate (fun _ => s.t8)) (Frame.fn_dfs 14 { s with t7 := h.nextRef }) stack)
  | dfs_pc16 (h : Heap) (s : State_dfs) (stack : Stack) :
      Step (.active h (Frame.fn_dfs 16 s) stack) (.active h (Frame.fn_dfs 15 { s with t8 := (0 : Int) }) stack)
  | dfs_pc17 (h : Heap) (s : State_dfs) (stack : Stack) :
      Step (.active h (Frame.fn_dfs 17 s) stack) (.active (h.tick "graph_work" 1) (Frame.fn_dfs 16 s) stack)
  | DFSResult_pc1 (h : Heap) (s : State_DFSResult) (stack : Stack) (defined : is_DFSResult h s.t1) :
      Step (.active h (Frame.fn_DFSResult 1 s) stack) (Algo2LeanCore.resumeConfig h (Result.fn_DFSResult (s.t1)) stack)
  | DFSResult_pc2 (h : Heap) (s : State_DFSResult) (stack : Stack) :
      Step (.active h (Frame.fn_DFSResult 2 s) stack) (.active h (Frame.fn_DFSResult 1 { s with t1 := s.v0 }) stack)
  | DFSResult_pc3 (h : Heap) (s : State_DFSResult) (stack : Stack) :
      Step (.active h (Frame.fn_DFSResult 3 s) stack) (.active h (Frame.fn_DFSResult___init__ 30 ({ v0 := s.t3 } : State_DFSResult___init__)) ((fun value => match value with | .fn_DFSResult___init__ result => (Frame.fn_DFSResult 2 { s with t2 := result }) | _ => .invalid) :: stack))
  | DFSResult_pc4 (h : Heap) (s : State_DFSResult) (stack : Stack) :
      Step (.active h (Frame.fn_DFSResult 4 s) stack) (.active h (Frame.fn_DFSResult 3 { s with t3 := s.v0 }) stack)
  | DFSResult_pc5 (h : Heap) (s : State_DFSResult) (stack : Stack) :
      Step (.active h (Frame.fn_DFSResult 5 s) stack) (.active h (Frame.fn_DFSResult 4 { s with v0 := s.t4 }) stack)
  | DFSResult_pc6 (h : Heap) (s : State_DFSResult) (stack : Stack) :
      Step (.active h (Frame.fn_DFSResult 6 s) stack) (.active (h.allocateObject "dfs.DFSResult") (Frame.fn_DFSResult 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_DFSResult___init__ (input : Ref_DFSResult) : Frame :=
  (Frame.fn_DFSResult___init__ 30 ({ v0 := input } : State_DFSResult___init__))

def DFSResult.__init__.ValidInput (h : Heap) (input : Ref_DFSResult) : Prop := is_DFSResult h input
def DFSResult.__init__.initial (h : Heap) (input : Ref_DFSResult) : Configuration :=
  Algo2LeanCore.start h (Frame.fn_DFSResult___init__ 30 ({ v0 := input } : State_DFSResult___init__))
def DFSResult.__init__.Run (h : Heap) (input : Ref_DFSResult) (h' : Heap) (output : Unit) : Prop :=
  _root_.Algo.«dfs».DFSResult.__init__.ValidInput h input ∧ Algo2LeanCore.Reaches Step (_root_.Algo.«dfs».DFSResult.__init__.initial h input) (.done h' (Result.fn_DFSResult___init__ output))
def DFSResult.__init__.ValidHeapTranscript (h : Heap) (input : Ref_DFSResult) (trace : Transcript) : Prop :=
  _root_.Algo.«dfs».DFSResult.__init__.ValidInput h input ∧ ∃ final, Algo2LeanCore.Valid Step (_root_.Algo.«dfs».DFSResult.__init__.initial h input) trace final
def DFSResult.__init__.Call (h : Heap) (input : Ref_DFSResult) (h' : Heap) (output : Unit) : Prop :=
  _root_.Algo.«dfs».DFSResult.__init__.ValidInput h input ∧ Algo2LeanCore.Summary Step h (Frame.fn_DFSResult___init__ 30 ({ v0 := input } : State_DFSResult___init__)) h' (Result.fn_DFSResult___init__ output)
-- Complete this function from the supplied local state, under any caller stack.
def DFSResult.__init__.CallFrom (state : Configuration) (finalHeap : Heap) (output : Unit) : Prop :=
  match state with
  | .active heap (Frame.fn_DFSResult___init__ pc locals) _ =>
      Algo2LeanCore.Summary Step heap (Frame.fn_DFSResult___init__ pc locals) finalHeap (Result.fn_DFSResult___init__ output)
  | _ => False
-- Object inputs carry their heap, preserving shared references and cycles.
def DFSResult.__init__.load (input : Heap × (Ref_DFSResult)) : Heap × (Ref_DFSResult) := input
def DFSResult.__init__.ValidTranscript (my_input : Heap × (Ref_DFSResult)) (trace : Transcript) : Prop :=
  let loaded := _root_.Algo.«dfs».DFSResult.__init__.load my_input
  _root_.Algo.«dfs».DFSResult.__init__.ValidHeapTranscript loaded.1 loaded.2 trace
def DFSResult.__init__.Returns (my_input : Heap × (Ref_DFSResult)) (my_output : Unit) : Prop :=
  let loaded := _root_.Algo.«dfs».DFSResult.__init__.load my_input
  ∃ finalHeap, _root_.Algo.«dfs».DFSResult.__init__.Run loaded.1 loaded.2 finalHeap my_output

-- Output and clock increments from one completed execution.
def DFSResult.__init__.ReturnsWithCost (my_input : Heap × (Ref_DFSResult)) (my_output : Unit) (costs : Clocks) : Prop :=
  let loaded := _root_.Algo.«dfs».DFSResult.__init__.load my_input
  ∃ finalHeap, _root_.Algo.«dfs».DFSResult.__init__.Run loaded.1 loaded.2 finalHeap my_output ∧ Heap.cost loaded.1 finalHeap = costs
theorem DFSResult.__init__.ReturnsWithCost.returns {input output costs}
    (run : _root_.Algo.«dfs».DFSResult.__init__.ReturnsWithCost input output costs) : _root_.Algo.«dfs».DFSResult.__init__.Returns input output := by
  obtain ⟨heap, execution, _⟩ := run
  exact ⟨heap, execution⟩
theorem DFSResult.__init__.Returns.withCost {input output}
    (run : _root_.Algo.«dfs».DFSResult.__init__.Returns input output) : ∃ costs, _root_.Algo.«dfs».DFSResult.__init__.ReturnsWithCost input output costs := by
  obtain ⟨heap, execution⟩ := run
  exact ⟨Heap.cost (_root_.Algo.«dfs».DFSResult.__init__.load input).1 heap, heap, execution, rfl⟩

theorem DFSResult.__init__.Call.run {before input after output}
    (call : _root_.Algo.«dfs».DFSResult.__init__.Call before input after output) :
    _root_.Algo.«dfs».DFSResult.__init__.Run before input after output :=
  ⟨call.1, call.2.root⟩

def entry_visit (input : Ref__a2l_import_0_UnweightedGraph × Ref_DFSResult × Int × Int) : Frame :=
  (Frame.fn_visit 40 ({ v0 := input.1, v1 := input.2.1, v2 := input.2.2.1, v3 := input.2.2.2 } : State_visit))

def visit.ValidInput (h : Heap) (input : Ref__a2l_import_0_UnweightedGraph × Ref_DFSResult × Int × Int) : Prop := is__a2l_import_0_UnweightedGraph h input.1 ∧ is_DFSResult h input.2.1
def visit.initial (h : Heap) (input : Ref__a2l_import_0_UnweightedGraph × Ref_DFSResult × Int × Int) : Configuration :=
  Algo2LeanCore.start h (Frame.fn_visit 40 ({ v0 := input.1, v1 := input.2.1, v2 := input.2.2.1, v3 := input.2.2.2 } : State_visit))
def visit.Run (h : Heap) (input : Ref__a2l_import_0_UnweightedGraph × Ref_DFSResult × Int × Int) (h' : Heap) (output : Unit) : Prop :=
  _root_.Algo.«dfs».visit.ValidInput h input ∧ Algo2LeanCore.Reaches Step (_root_.Algo.«dfs».visit.initial h input) (.done h' (Result.fn_visit output))
def visit.ValidHeapTranscript (h : Heap) (input : Ref__a2l_import_0_UnweightedGraph × Ref_DFSResult × Int × Int) (trace : Transcript) : Prop :=
  _root_.Algo.«dfs».visit.ValidInput h input ∧ ∃ final, Algo2LeanCore.Valid Step (_root_.Algo.«dfs».visit.initial h input) trace final
def visit.Call (h : Heap) (input : Ref__a2l_import_0_UnweightedGraph × Ref_DFSResult × Int × Int) (h' : Heap) (output : Unit) : Prop :=
  _root_.Algo.«dfs».visit.ValidInput h input ∧ Algo2LeanCore.Summary Step h (Frame.fn_visit 40 ({ v0 := input.1, v1 := input.2.1, v2 := input.2.2.1, v3 := input.2.2.2 } : State_visit)) h' (Result.fn_visit output)
-- Complete this function from the supplied local state, under any caller stack.
def visit.CallFrom (state : Configuration) (finalHeap : Heap) (output : Unit) : Prop :=
  match state with
  | .active heap (Frame.fn_visit pc locals) _ =>
      Algo2LeanCore.Summary Step heap (Frame.fn_visit pc locals) finalHeap (Result.fn_visit output)
  | _ => False
-- Object inputs carry their heap, preserving shared references and cycles.
def visit.load (input : Heap × (Ref__a2l_import_0_UnweightedGraph × Ref_DFSResult × Int × Int)) : Heap × (Ref__a2l_import_0_UnweightedGraph × Ref_DFSResult × Int × Int) := input
def visit.ValidTranscript (my_input : Heap × (Ref__a2l_import_0_UnweightedGraph × Ref_DFSResult × Int × Int)) (trace : Transcript) : Prop :=
  let loaded := _root_.Algo.«dfs».visit.load my_input
  _root_.Algo.«dfs».visit.ValidHeapTranscript loaded.1 loaded.2 trace
def visit.Returns (my_input : Heap × (Ref__a2l_import_0_UnweightedGraph × Ref_DFSResult × Int × Int)) (my_output : Unit) : Prop :=
  let loaded := _root_.Algo.«dfs».visit.load my_input
  ∃ finalHeap, _root_.Algo.«dfs».visit.Run loaded.1 loaded.2 finalHeap my_output

-- Output and clock increments from one completed execution.
def visit.ReturnsWithCost (my_input : Heap × (Ref__a2l_import_0_UnweightedGraph × Ref_DFSResult × Int × Int)) (my_output : Unit) (costs : Clocks) : Prop :=
  let loaded := _root_.Algo.«dfs».visit.load my_input
  ∃ finalHeap, _root_.Algo.«dfs».visit.Run loaded.1 loaded.2 finalHeap my_output ∧ Heap.cost loaded.1 finalHeap = costs
theorem visit.ReturnsWithCost.returns {input output costs}
    (run : _root_.Algo.«dfs».visit.ReturnsWithCost input output costs) : _root_.Algo.«dfs».visit.Returns input output := by
  obtain ⟨heap, execution, _⟩ := run
  exact ⟨heap, execution⟩
theorem visit.Returns.withCost {input output}
    (run : _root_.Algo.«dfs».visit.Returns input output) : ∃ costs, _root_.Algo.«dfs».visit.ReturnsWithCost input output costs := by
  obtain ⟨heap, execution⟩ := run
  exact ⟨Heap.cost (_root_.Algo.«dfs».visit.load input).1 heap, heap, execution, rfl⟩

theorem visit.Call.run {before input after output}
    (call : _root_.Algo.«dfs».visit.Call before input after output) :
    _root_.Algo.«dfs».visit.Run before input after output :=
  ⟨call.1, call.2.root⟩

def entry_dfs_ordered (input : Ref__a2l_import_0_UnweightedGraph × SeqRef) : Frame :=
  (Frame.fn_dfs_ordered 26 ({ v0 := input.1, v1 := input.2 } : State_dfs_ordered))

def dfs_ordered.ValidInput (h : Heap) (input : Ref__a2l_import_0_UnweightedGraph × SeqRef) : Prop := is__a2l_import_0_UnweightedGraph h input.1 ∧ input.2 < h.nextRef
def dfs_ordered.initial (h : Heap) (input : Ref__a2l_import_0_UnweightedGraph × SeqRef) : Configuration :=
  Algo2LeanCore.start h (Frame.fn_dfs_ordered 26 ({ v0 := input.1, v1 := input.2 } : State_dfs_ordered))
def dfs_ordered.Run (h : Heap) (input : Ref__a2l_import_0_UnweightedGraph × SeqRef) (h' : Heap) (output : Ref_DFSResult) : Prop :=
  _root_.Algo.«dfs».dfs_ordered.ValidInput h input ∧ Algo2LeanCore.Reaches Step (_root_.Algo.«dfs».dfs_ordered.initial h input) (.done h' (Result.fn_dfs_ordered output))
def dfs_ordered.ValidHeapTranscript (h : Heap) (input : Ref__a2l_import_0_UnweightedGraph × SeqRef) (trace : Transcript) : Prop :=
  _root_.Algo.«dfs».dfs_ordered.ValidInput h input ∧ ∃ final, Algo2LeanCore.Valid Step (_root_.Algo.«dfs».dfs_ordered.initial h input) trace final
def dfs_ordered.Call (h : Heap) (input : Ref__a2l_import_0_UnweightedGraph × SeqRef) (h' : Heap) (output : Ref_DFSResult) : Prop :=
  _root_.Algo.«dfs».dfs_ordered.ValidInput h input ∧ Algo2LeanCore.Summary Step h (Frame.fn_dfs_ordered 26 ({ v0 := input.1, v1 := input.2 } : State_dfs_ordered)) h' (Result.fn_dfs_ordered output)
-- Complete this function from the supplied local state, under any caller stack.
def dfs_ordered.CallFrom (state : Configuration) (finalHeap : Heap) (output : Ref_DFSResult) : Prop :=
  match state with
  | .active heap (Frame.fn_dfs_ordered pc locals) _ =>
      Algo2LeanCore.Summary Step heap (Frame.fn_dfs_ordered pc locals) finalHeap (Result.fn_dfs_ordered output)
  | _ => False
-- Object inputs carry their heap, preserving shared references and cycles.
def dfs_ordered.load (input : Heap × (Ref__a2l_import_0_UnweightedGraph × SeqRef)) : Heap × (Ref__a2l_import_0_UnweightedGraph × SeqRef) := input
def dfs_ordered.ValidTranscript (my_input : Heap × (Ref__a2l_import_0_UnweightedGraph × SeqRef)) (trace : Transcript) : Prop :=
  let loaded := _root_.Algo.«dfs».dfs_ordered.load my_input
  _root_.Algo.«dfs».dfs_ordered.ValidHeapTranscript loaded.1 loaded.2 trace
def dfs_ordered.Returns (my_input : Heap × (Ref__a2l_import_0_UnweightedGraph × SeqRef)) (my_output : Heap × (Ref_DFSResult)) : Prop :=
  let loaded := _root_.Algo.«dfs».dfs_ordered.load my_input
  _root_.Algo.«dfs».dfs_ordered.Run loaded.1 loaded.2 my_output.1 my_output.2

-- Output and clock increments from one completed execution.
def dfs_ordered.ReturnsWithCost (my_input : Heap × (Ref__a2l_import_0_UnweightedGraph × SeqRef)) (my_output : Heap × (Ref_DFSResult)) (costs : Clocks) : Prop :=
  let loaded := _root_.Algo.«dfs».dfs_ordered.load my_input
  _root_.Algo.«dfs».dfs_ordered.Run loaded.1 loaded.2 my_output.1 my_output.2 ∧ Heap.cost loaded.1 my_output.1 = costs
theorem dfs_ordered.ReturnsWithCost.returns {input output costs}
    (run : _root_.Algo.«dfs».dfs_ordered.ReturnsWithCost input output costs) : _root_.Algo.«dfs».dfs_ordered.Returns input output := by
  obtain ⟨execution, _⟩ := run
  exact execution
theorem dfs_ordered.Returns.withCost {input output}
    (run : _root_.Algo.«dfs».dfs_ordered.Returns input output) : ∃ costs, _root_.Algo.«dfs».dfs_ordered.ReturnsWithCost input output costs := by
  exact ⟨Heap.cost (_root_.Algo.«dfs».dfs_ordered.load input).1 output.1, run, rfl⟩

theorem dfs_ordered.Call.run {before input after output}
    (call : _root_.Algo.«dfs».dfs_ordered.Call before input after output) :
    _root_.Algo.«dfs».dfs_ordered.Run before input after output :=
  ⟨call.1, call.2.root⟩

def entry_dfs (input : Ref__a2l_import_0_UnweightedGraph) : Frame :=
  (Frame.fn_dfs 17 ({ v0 := input } : State_dfs))

def dfs.ValidInput (h : Heap) (input : Ref__a2l_import_0_UnweightedGraph) : Prop := is__a2l_import_0_UnweightedGraph h input
def dfs.initial (h : Heap) (input : Ref__a2l_import_0_UnweightedGraph) : Configuration :=
  Algo2LeanCore.start h (Frame.fn_dfs 17 ({ v0 := input } : State_dfs))
def dfs.Run (h : Heap) (input : Ref__a2l_import_0_UnweightedGraph) (h' : Heap) (output : Ref_DFSResult) : Prop :=
  _root_.Algo.«dfs».dfs.ValidInput h input ∧ Algo2LeanCore.Reaches Step (_root_.Algo.«dfs».dfs.initial h input) (.done h' (Result.fn_dfs output))
def dfs.ValidHeapTranscript (h : Heap) (input : Ref__a2l_import_0_UnweightedGraph) (trace : Transcript) : Prop :=
  _root_.Algo.«dfs».dfs.ValidInput h input ∧ ∃ final, Algo2LeanCore.Valid Step (_root_.Algo.«dfs».dfs.initial h input) trace final
def dfs.Call (h : Heap) (input : Ref__a2l_import_0_UnweightedGraph) (h' : Heap) (output : Ref_DFSResult) : Prop :=
  _root_.Algo.«dfs».dfs.ValidInput h input ∧ Algo2LeanCore.Summary Step h (Frame.fn_dfs 17 ({ v0 := input } : State_dfs)) h' (Result.fn_dfs output)
-- Complete this function from the supplied local state, under any caller stack.
def dfs.CallFrom (state : Configuration) (finalHeap : Heap) (output : Ref_DFSResult) : Prop :=
  match state with
  | .active heap (Frame.fn_dfs pc locals) _ =>
      Algo2LeanCore.Summary Step heap (Frame.fn_dfs pc locals) finalHeap (Result.fn_dfs output)
  | _ => False
-- Object inputs carry their heap, preserving shared references and cycles.
def dfs.load (input : Heap × (Ref__a2l_import_0_UnweightedGraph)) : Heap × (Ref__a2l_import_0_UnweightedGraph) := input
def dfs.ValidTranscript (my_input : Heap × (Ref__a2l_import_0_UnweightedGraph)) (trace : Transcript) : Prop :=
  let loaded := _root_.Algo.«dfs».dfs.load my_input
  _root_.Algo.«dfs».dfs.ValidHeapTranscript loaded.1 loaded.2 trace
def dfs.Returns (my_input : Heap × (Ref__a2l_import_0_UnweightedGraph)) (my_output : Heap × (Ref_DFSResult)) : Prop :=
  let loaded := _root_.Algo.«dfs».dfs.load my_input
  _root_.Algo.«dfs».dfs.Run loaded.1 loaded.2 my_output.1 my_output.2

-- Output and clock increments from one completed execution.
def dfs.ReturnsWithCost (my_input : Heap × (Ref__a2l_import_0_UnweightedGraph)) (my_output : Heap × (Ref_DFSResult)) (costs : Clocks) : Prop :=
  let loaded := _root_.Algo.«dfs».dfs.load my_input
  _root_.Algo.«dfs».dfs.Run loaded.1 loaded.2 my_output.1 my_output.2 ∧ Heap.cost loaded.1 my_output.1 = costs
theorem dfs.ReturnsWithCost.returns {input output costs}
    (run : _root_.Algo.«dfs».dfs.ReturnsWithCost input output costs) : _root_.Algo.«dfs».dfs.Returns input output := by
  obtain ⟨execution, _⟩ := run
  exact execution
theorem dfs.Returns.withCost {input output}
    (run : _root_.Algo.«dfs».dfs.Returns input output) : ∃ costs, _root_.Algo.«dfs».dfs.ReturnsWithCost input output costs := by
  exact ⟨Heap.cost (_root_.Algo.«dfs».dfs.load input).1 output.1, run, rfl⟩

theorem dfs.Call.run {before input after output}
    (call : _root_.Algo.«dfs».dfs.Call before input after output) :
    _root_.Algo.«dfs».dfs.Run before input after output :=
  ⟨call.1, call.2.root⟩

def entry_DFSResult (_input : Unit) : Frame :=
  (Frame.fn_DFSResult 6 ({  } : State_DFSResult))

def DFSResult.ValidInput (_h : Heap) (_input : Unit) : Prop := True
def DFSResult.initial (h : Heap) (_input : Unit) : Configuration :=
  Algo2LeanCore.start h (Frame.fn_DFSResult 6 ({  } : State_DFSResult))
def DFSResult.Run (h : Heap) (input : Unit) (h' : Heap) (output : Ref_DFSResult) : Prop :=
  _root_.Algo.«dfs».DFSResult.ValidInput h input ∧ Algo2LeanCore.Reaches Step (_root_.Algo.«dfs».DFSResult.initial h input) (.done h' (Result.fn_DFSResult output))
def DFSResult.ValidHeapTranscript (h : Heap) (input : Unit) (trace : Transcript) : Prop :=
  _root_.Algo.«dfs».DFSResult.ValidInput h input ∧ ∃ final, Algo2LeanCore.Valid Step (_root_.Algo.«dfs».DFSResult.initial h input) trace final
def DFSResult.Call (h : Heap) (input : Unit) (h' : Heap) (output : Ref_DFSResult) : Prop :=
  _root_.Algo.«dfs».DFSResult.ValidInput h input ∧ Algo2LeanCore.Summary Step h (Frame.fn_DFSResult 6 ({  } : State_DFSResult)) h' (Result.fn_DFSResult output)
-- Complete this function from the supplied local state, under any caller stack.
def DFSResult.CallFrom (state : Configuration) (finalHeap : Heap) (output : Ref_DFSResult) : Prop :=
  match state with
  | .active heap (Frame.fn_DFSResult pc locals) _ =>
      Algo2LeanCore.Summary Step heap (Frame.fn_DFSResult pc locals) finalHeap (Result.fn_DFSResult output)
  | _ => False
-- The value view gives each sequence input its own object.
def DFSResult.load (_input : Unit) : Heap × (Unit) :=
  let h0 : Heap := {}
  (h0, ())
def DFSResult.ValidTranscript (my_input : Unit) (trace : Transcript) : Prop :=
  let loaded := _root_.Algo.«dfs».DFSResult.load my_input
  _root_.Algo.«dfs».DFSResult.ValidHeapTranscript loaded.1 loaded.2 trace
def DFSResult.Returns (my_input : Unit) (my_output : Heap × (Ref_DFSResult)) : Prop :=
  let loaded := _root_.Algo.«dfs».DFSResult.load my_input
  _root_.Algo.«dfs».DFSResult.Run loaded.1 loaded.2 my_output.1 my_output.2

-- Output and clock increments from one completed execution.
def DFSResult.ReturnsWithCost (my_input : Unit) (my_output : Heap × (Ref_DFSResult)) (costs : Clocks) : Prop :=
  let loaded := _root_.Algo.«dfs».DFSResult.load my_input
  _root_.Algo.«dfs».DFSResult.Run loaded.1 loaded.2 my_output.1 my_output.2 ∧ Heap.cost loaded.1 my_output.1 = costs
theorem DFSResult.ReturnsWithCost.returns {input output costs}
    (run : _root_.Algo.«dfs».DFSResult.ReturnsWithCost input output costs) : _root_.Algo.«dfs».DFSResult.Returns input output := by
  obtain ⟨execution, _⟩ := run
  exact execution
theorem DFSResult.Returns.withCost {input output}
    (run : _root_.Algo.«dfs».DFSResult.Returns input output) : ∃ costs, _root_.Algo.«dfs».DFSResult.ReturnsWithCost input output costs := by
  exact ⟨Heap.cost (_root_.Algo.«dfs».DFSResult.load input).1 output.1, run, rfl⟩

theorem DFSResult.Call.run {before input after output}
    (call : _root_.Algo.«dfs».DFSResult.Call before input after output) :
    _root_.Algo.«dfs».DFSResult.Run before input after output :=
  ⟨call.1, call.2.root⟩

end Algo.«dfs»


/-! Mathematical specifications for CLRS fourth-edition Section 20.3.
The statements describe the source-facing outputs of ordered recursive DFS.
The goals using these definitions are open; this module supplies no proofs. -/

namespace CLRS.DFS

open Algo2LeanGenerated CLRS.GraphTraversal

/-- A vertex is its own ancestor. Further steps follow the returned parent
array from a parent to a child, and remain in the finite vertex set. -/
inductive ParentPath (g : Graph) (parent : Seq) : Int → Int → Prop where
  | refl {u : Int} : Vertex g u → ParentPath g parent u u
  | step {u v w : Int} :
      ParentPath g parent u v → Vertex g w → parent w = v →
      ParentPath g parent u w

/-- A path whose vertices all belong to a specified set. The zero-edge path
also requires membership, so it is exactly induced-subgraph reachability. -/
inductive AllowedWalk (g : Graph) (allowed : Int → Prop) : Int → Int → Prop where
  | refl {u : Int} : Vertex g u → allowed u → AllowedWalk g allowed u u
  | step {u v w : Int} :
      Edge g u v → allowed u → AllowedWalk g allowed v w →
      AllowedWalk g allowed u w

/-- The root of a vertex's returned predecessor tree. -/
def RootOf (g : Graph) (parent : Seq) (root vertex : Int) : Prop :=
  Vertex g root ∧ parent root = -1 ∧ ParentPath g parent root vertex

/-- The ordered DFS forest, its event times, and the information needed to
reuse DFS in the two-pass strongly connected components algorithm.
`order` is the output in increasing finish time. `inputOrder` is the initial
outer-loop priority, and `component` numbers predecessor trees from zero.
These labels are not asserted to identify strongly connected components. -/
structure Forest (g : Graph)
    (inputOrder parent discover finish order component : Seq)
    (count : Nat) : Prop where
  parentEdges : ∀ v : Int, Vertex g v →
    parent v = -1 ∨ Edge g (parent v) v
  times : ∀ v : Int, Vertex g v →
    1 ≤ discover v ∧ discover v < finish v ∧ finish v ≤ 2 * (g.size : Int)
  discoveryDistinct : ∀ u v : Int, Vertex g u → Vertex g v →
    discover u = discover v → u = v
  finishDistinct : ∀ u v : Int, Vertex g u → Vertex g v →
    finish u = finish v → u = v
  eventDistinct : ∀ u v : Int, Vertex g u → Vertex g v →
    discover u ≠ finish v
  parentheses : ∀ u v : Int, Vertex g u → Vertex g v →
    finish u < discover v ∨ finish v < discover u ∨
      (discover u ≤ discover v ∧ finish v ≤ finish u) ∨
      (discover v ≤ discover u ∧ finish u ≤ finish v)
  ancestors : ∀ u v : Int, Vertex g u → Vertex g v →
    (ParentPath g parent u v ↔ discover u ≤ discover v ∧ finish v ≤ finish u)
  whitePaths : ∀ u v : Int, Vertex g u → Vertex g v →
    (ParentPath g parent u v ↔
      AllowedWalk g (fun w => discover u ≤ discover w) u v)
  rootPriority : ∀ i : Nat, i < g.size →
    parent (inputOrder (i : Int)) = -1 →
    ∀ j : Nat, j < i →
      finish (inputOrder (j : Int)) < discover (inputOrder (i : Int))
  finishOrder : VertexOrder g order
  finishIncreasing : ∀ i j : Nat, i < j → j < g.size →
    finish (order (i : Int)) < finish (order (j : Int))
  componentRange : ∀ v : Int, Vertex g v →
    0 ≤ component v ∧ component v < (count : Int)
  componentCoverage : ∀ label : Nat, label < count →
    ∃ v : Int, Vertex g v ∧ component v = (label : Int)
  componentTrees : ∀ u v : Int, Vertex g u → Vertex g v →
    (component u = component v ↔
      ∃ root : Int, RootOf g parent root u ∧ RootOf g parent root v)
  componentOrder : ∀ u v : Int, Vertex g u → Vertex g v →
    parent u = -1 → parent v = -1 →
    (component u < component v ↔ discover u < discover v)

/-- A fresh result object with six distinct fresh arrays, preserving every
initially allocated caller sequence, object, and collection. Every valid vertex
is black, all discovery/finish events have occurred, and the mathematical
forest contract uses the caller's original root-order sequence. Contents
outside the vertex prefixes are deliberately unspecified. -/
def Post (before after : Heap) (result : ObjectRef) (g : Graph)
    (inputOrder : Seq) : Prop :=
  Algo.dfs.Algo2LeanGenerated.is_DFSResult after result ∧
  FreshObject before after result ∧
  Preserves before after ∧
  ∃ color parent discover finish order component : SeqRef,
    Algo.dfs.Algo2LeanGenerated.field_DFSResult_color after result = some color ∧
    Algo.dfs.Algo2LeanGenerated.field_DFSResult_parent after result = some parent ∧
    Algo.dfs.Algo2LeanGenerated.field_DFSResult_discover after result = some discover ∧
    Algo.dfs.Algo2LeanGenerated.field_DFSResult_finish after result = some finish ∧
    Algo.dfs.Algo2LeanGenerated.field_DFSResult_order after result = some order ∧
    Algo.dfs.Algo2LeanGenerated.field_DFSResult_component after result = some component ∧
    FreshArrays before after [color, parent, discover, finish, order, component] ∧
    Algo.dfs.Algo2LeanGenerated.field_DFSResult_clock after result = some (2 * (g.size : Int)) ∧
    Algo.dfs.Algo2LeanGenerated.field_DFSResult_finished after result = some (g.size : Int) ∧
    (∀ v : Int, Vertex g v → after.read color v = 2) ∧
    ∃ count : Nat,
      Algo.dfs.Algo2LeanGenerated.field_DFSResult_components after result = some (count : Int) ∧
      count ≤ g.size ∧
      Forest g inputOrder (after.read parent) (after.read discover)
        (after.read finish) (after.read order) (after.read component) count

end CLRS.DFS
Source
CLRS, Introduction to Algorithms, fourth edition (MIT Press, 2022), Chapter 20, §20.3. 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 module defines a heap-and-stack transition relation for a result constructor, its initializer, a recursive visit procedure, an ordered traversal, and an ordinary traversal, together with execution relations and mathematical output predicates; it makes no unconditional termination or complexity assertion. Sequence, object, and collection references are natural numbers in separate identity spaces; integer sequences are total functions Z→Z\mathbb Z\to\mathbb ZZ→Z. Allocations use the current counter and increment it, and field reads check the object's allocated class tag and stored field type. The result constructor allocates an object tagged dfs.DFSResult and invokes its initializer, which allocates six distinct sequences, setting all integer positions of color, discover, and finish initially to zero, and of parent, order, and component initially to −1-1−1, and sets the integer fields clock, finished, and components to zero. The direct helper that creates a result object instead installs supplied references and integers without running the initializer or requiring these references to be fresh. For a graph reference aaa, result reference rrr, and arbitrary integer arguments u,ℓu,\ellu,ℓ, visit increments the result's event clock and writes it to d(u)d(u)d(u), writes color 111 and component label ℓ\ellℓ at uuu, reads the adjacency-row reference at uuu, and scans its entries with integer index jjj beginning at zero while jjj is less than the degree entry at uuu. For each read neighbor vvv, if its color is zero the procedure sets p(v)=up(v)=up(v)=u and recursively visits vvv with the same label, then advances jjj. After that loop it sets the color at uuu to 222, increments the event clock and records it in f(u)f(u)f(u), writes uuu into order at the old finished index, and increments finished. dfs_ordered allocates and initializes a result, scans the caller's order sequence at indices iii beginning at zero while iii is less than the graph's size field, and, whenever the selected vertex has color zero, calls visit with its current component count as label and increments that count after the call; it returns the result reference. dfs first allocates a zero-filled sequence, writes the identity values iii at indices from zero up to but excluding the graph's size field, and calls dfs_ordered with that sequence, returning its result. Each explicit tick increments only the heap's graph_work counter by one: the initializer ticks once; a visit ticks at entry, before each neighbor-loop condition test, at each neighbor-loop body entry, before each recursive-child call, and after the loop; ordered traversal ticks at entry, before each outer-loop condition test, at each outer-loop body entry, before each new-root visit, and after the loop; ordinary traversal ticks at entry, before each order-initialization loop condition test, at each such loop body entry, and after that loop. Other individual transitions carry no tick. The raw validity condition for dfs checks only that aaa is an allocated object with the graph class tag, for dfs_ordered additionally that the order sequence is allocated, for visit only that the graph and result objects have their respective allocated class tags, for the initializer only that its result object has that tag, and for the constructor it is always true; these raw conditions do not require valid graph fields, bounded neighbors, a valid vertex argument, or a permutation order. A missing or ill-typed field, an invalid referenced allocation when it is used, an invalid frame, or an inappropriate return tag can therefore leave a raw execution without a successor. Run means raw input validity plus a finite transition transcript from the entry on an empty stack to a completed configuration; Call means raw validity plus such finite reachability to the returned configuration for every suspended continuation stack, using the same final heap and result. CallFrom instead requires this stack-uniform reachability from the given matching procedure frame and its local state, without requiring entry validity; it is false for other kinds of configuration. A valid transcript may stop at an intermediate configuration and does not by itself express completion. The Returns relations keep caller-supplied heaps for object inputs, expose the final heap with returned result objects, and existentially hide the final heap for unit-returning visits and initialization; the constructor's value-level Returns starts with the default empty heap. ReturnsWithCost further equates all named cost increments with the final-minus-initial natural counter differences. Here a graph ggg consists of a natural number nnn and, for each natural number uuu, a finite ordered list N(u)N(u)N(u) of natural numbers, with every entry of N(u)N(u)N(u) less than nnn whenever u<nu<nu<n; its vertices are the integers 0≤v<n0\le v<n0≤v<n, an edge u→vu\to vu→v means that both endpoints are vertices and vvv occurs in N(u)N(u)N(u), and m=∑u=0n−1∣N(u)∣m=\sum_{u=0}^{n-1}|N(u)|m=∑u=0n−1​∣N(u)∣ counts occurrences, including parallel edges and self-loops. No symmetry is required, and rows at indices u≥nu\ge nu≥n are unrestricted. For such a graph, the mathematical predicate Post takes arbitrary heaps H,H′H,H'H,H′, result reference rrr, and integer sequence qqq and imposes precisely the following requirements; it does not itself require input graph representation or that qqq is a permutation. The resulting heap H′H'H′ contains an allocated object rrr of class dfs.DFSResult whose identity is at least the initial object-allocation counter, and its six fields color, parent, discover, finish, order, and component point to pairwise distinct allocated integer sequences, each with identity at least the initial sequence-allocation counter. Write their contents as c,p,d,f,o,bc,p,d,f,o,bc,p,d,f,o,b. Every initially allocated sequence retains its contents at every integer index, every initially allocated object and collection retains its entire stored value, all three allocation counters do not decrease, the named heap counter graph_work does not decrease, and all other named heap counters are unchanged. The result's separate integer fields clock and finished equal 2n2n2n and nnn, and c(v)=2c(v)=2c(v)=2 for every vertex. There is a natural number k≤nk\le nk≤n such that the result's components field equals kkk, and the following conditions hold. Each vertex vvv has p(v)=−1p(v)=-1p(v)=−1 or an edge p(v)→vp(v)\to vp(v)→v; 1≤d(v)<f(v)≤2n1\le d(v)<f(v)\le2n1≤d(v)<f(v)≤2n; discovery times are pairwise distinct, finishing times are pairwise distinct, and d(u)≠f(v)d(u)\ne f(v)d(u)=f(v) for every pair of vertices. For every two vertices u,vu,vu,v, either f(u)<d(v)f(u)<d(v)f(u)<d(v), or f(v)<d(u)f(v)<d(u)f(v)<d(u), or d(u)≤d(v)d(u)\le d(v)d(u)≤d(v) and f(v)≤f(u)f(v)\le f(u)f(v)≤f(u), or d(v)≤d(u)d(v)\le d(u)d(v)≤d(u) and f(u)≤f(v)f(u)\le f(v)f(u)≤f(v). Define A(u,v)A(u,v)A(u,v) to mean that there is a finite sequence of vertices starting at uuu and ending at vvv, possibly of length zero, such that each successive vertex yyy has parent equal to its predecessor; thus every vertex is its own ancestor. For vertices u,vu,vu,v, A(u,v)A(u,v)A(u,v) holds if and only if d(u)≤d(v)d(u)\le d(v)d(u)≤d(v) and f(v)≤f(u)f(v)\le f(u)f(v)≤f(u), and also if and only if there is a directed graph walk from uuu to vvv, possibly of length zero, all of whose vertices www satisfy d(u)≤d(w)d(u)\le d(w)d(u)≤d(w). With the input-priority sequence denoted by qqq, for every natural i<ni<ni<n with p(q(i))=−1p(q(i))=-1p(q(i))=−1, every natural j<ij<ij<i satisfies f(q(j))<d(q(i))f(q(j))<d(q(i))f(q(j))<d(q(i)). The prefix o(0),…,o(n−1)o(0),\ldots,o(n-1)o(0),…,o(n−1) is a permutation of the vertices and satisfies f(o(i))<f(o(j))f(o(i))<f(o(j))f(o(i))<f(o(j)) whenever 0≤i<j<n0\le i<j<n0≤i<j<n. Every vertex has 0≤b(v)<k0\le b(v)<k0≤b(v)<k, every natural label ℓ<k\ell<kℓ<k is attained by a vertex, and b(u)=b(v)b(u)=b(v)b(u)=b(v) holds exactly when there is a vertex zzz with p(z)=−1p(z)=-1p(z)=−1, A(z,u)A(z,u)A(z,u), and A(z,v)A(z,v)A(z,v). For roots u,vu,vu,v satisfying p(u)=p(v)=−1p(u)=p(v)=-1p(u)=p(v)=−1, b(u)<b(v)b(u)<b(v)b(u)<b(v) holds if and only if d(u)<d(v)d(u)<d(v)d(u)<d(v). These labels describe parent trees; no equivalence with strong connectivity is asserted. The postcondition imposes no contents on the six output sequences outside their vertex prefixes and does not specify the exact total amount of new storage. The work measure WWW is the natural-number difference between the final and initial values of the named heap counter graph_work, using subtraction truncated at zero; the preservation condition prevents a decrease here. It counts the explicit unit tick transitions, including those in nested calls, rather than all individual transitions or machine operations; the initial counters are arbitrary and are not reset. In particular, for the empty graph the quantified vertex conditions are vacuous but the postcondition still requires a fresh tagged result, six distinct fresh allocated sequences, preservation, and zero result counters and component count. This definition module gives no numerical total-work bound and no proof that an execution satisfies the postcondition.

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