Two-pass SCC program, graph transpose, and component specifications
DefinitionCLRS_SCC_ProgramThe concrete Kosaraju-style program calls DFS, constructs a transpose with separate adjacency rows, reverses the first finish-order prefix, and calls ordered DFS again. The transposition specification preserves vertex count, total arc occurrences, and every reversed arc multiplicity. The SCC postcondition requires a fresh component array and result object, labels in a contiguous range with every label used, and equal labels exactly when two original vertices are mutually reachable. The number of components is at most n and is zero exactly for an empty graph. All initial caller storage is preserved. Only the component fields of the returned DFSResult are specified by the SCC postcondition. Definitions fix the actual executed program; all associated theorems are open.
import Definitions.Def_Algo2LeanLib_Modules
import Definitions.Def_CLRS_Graph_Input
import Definitions.Def_CLRS_DFS_Program
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.«scc»
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__a2l_import_1_DFSResult := Algo.«dfs».Algo2LeanGenerated.Ref_DFSResult
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
abbrev is__a2l_import_1_DFSResult := Algo.«dfs».Algo2LeanGenerated.is_DFSResult
abbrev create__a2l_import_1_DFSResult := Algo.«dfs».Algo2LeanGenerated.create_DFSResult
abbrev field__a2l_import_1_DFSResult_color := Algo.«dfs».Algo2LeanGenerated.field_DFSResult_color
abbrev set__a2l_import_1_DFSResult_color := Algo.«dfs».Algo2LeanGenerated.set_DFSResult_color
abbrev field__a2l_import_1_DFSResult_parent := Algo.«dfs».Algo2LeanGenerated.field_DFSResult_parent
abbrev set__a2l_import_1_DFSResult_parent := Algo.«dfs».Algo2LeanGenerated.set_DFSResult_parent
abbrev field__a2l_import_1_DFSResult_discover := Algo.«dfs».Algo2LeanGenerated.field_DFSResult_discover
abbrev set__a2l_import_1_DFSResult_discover := Algo.«dfs».Algo2LeanGenerated.set_DFSResult_discover
abbrev field__a2l_import_1_DFSResult_finish := Algo.«dfs».Algo2LeanGenerated.field_DFSResult_finish
abbrev set__a2l_import_1_DFSResult_finish := Algo.«dfs».Algo2LeanGenerated.set_DFSResult_finish
abbrev field__a2l_import_1_DFSResult_order := Algo.«dfs».Algo2LeanGenerated.field_DFSResult_order
abbrev set__a2l_import_1_DFSResult_order := Algo.«dfs».Algo2LeanGenerated.set_DFSResult_order
abbrev field__a2l_import_1_DFSResult_component := Algo.«dfs».Algo2LeanGenerated.field_DFSResult_component
abbrev set__a2l_import_1_DFSResult_component := Algo.«dfs».Algo2LeanGenerated.set_DFSResult_component
abbrev field__a2l_import_1_DFSResult_clock := Algo.«dfs».Algo2LeanGenerated.field_DFSResult_clock
abbrev set__a2l_import_1_DFSResult_clock := Algo.«dfs».Algo2LeanGenerated.set_DFSResult_clock
abbrev field__a2l_import_1_DFSResult_finished := Algo.«dfs».Algo2LeanGenerated.field_DFSResult_finished
abbrev set__a2l_import_1_DFSResult_finished := Algo.«dfs».Algo2LeanGenerated.set_DFSResult_finished
abbrev field__a2l_import_1_DFSResult_components := Algo.«dfs».Algo2LeanGenerated.field_DFSResult_components
abbrev set__a2l_import_1_DFSResult_components := Algo.«dfs».Algo2LeanGenerated.set_DFSResult_components
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_transpose where
v0 : Ref__a2l_import_0_UnweightedGraph := 0 -- graph
v1 : CollectionRef := 0 -- adj
v2 : SeqRef := 0 -- degree
v3 : Int := 0 -- u
v4 : SeqRef := 0 -- neighbors
v5 : Int := 0 -- j
v6 : Int := 0 -- v
t7 : Ref__a2l_import_0_UnweightedGraph := 0 -- temporary
t8 : Int := 0 -- temporary
t9 : CollectionRef := 0 -- temporary
t10 : SeqRef := 0 -- temporary
t11 : Bool := false -- temporary
t12 : Bool := false -- temporary
t13 : Bool := false -- temporary
t14 : SeqRef := 0 -- temporary
t15 : Int := 0 -- temporary
t16 : CollectionRef := 0 -- temporary
t17 : Int := 0 -- temporary
t18 : SeqRef := 0 -- temporary
t19 : Int := 0 -- temporary
t20 : CollectionRef := 0 -- temporary
t21 : SeqRef := 0 -- temporary
t22 : Int := 0 -- temporary
structure State_scc where
v0 : Ref__a2l_import_0_UnweightedGraph := 0 -- graph
v1 : Ref__a2l_import_1_DFSResult := 0 -- first
v2 : Ref__a2l_import_0_UnweightedGraph := 0 -- reversed_graph
v3 : SeqRef := 0 -- order
v4 : Int := 0 -- i
t5 : Ref__a2l_import_1_DFSResult := 0 -- temporary
t6 : Ref__a2l_import_0_UnweightedGraph := 0 -- temporary
t7 : SeqRef := 0 -- temporary
t8 : Bool := false -- temporary
t9 : SeqRef := 0 -- temporary
t10 : Int := 0 -- temporary
t11 : Ref__a2l_import_0_UnweightedGraph := 0 -- temporary
t12 : Ref__a2l_import_0_UnweightedGraph := 0 -- temporary
t13 : Ref__a2l_import_1_DFSResult := 0 -- temporary
t14 : Ref__a2l_import_0_UnweightedGraph := 0 -- temporary
inductive Frame where
| invalid
| fn_transpose (pc : Nat) (state : State_transpose)
| fn_scc (pc : Nat) (state : State_scc)
| import_0 (frame : Algo.«graph_input».Algo2LeanGenerated.Frame) (inner : Algo.«graph_input».Algo2LeanGenerated.Stack) (resume : Algo.«graph_input».Algo2LeanGenerated.Result → Frame)
| import_1 (frame : Algo.«dfs».Algo2LeanGenerated.Frame) (inner : Algo.«dfs».Algo2LeanGenerated.Stack) (resume : Algo.«dfs».Algo2LeanGenerated.Result → Frame)
inductive Result where
| fn_transpose (value : Ref__a2l_import_0_UnweightedGraph)
| fn_scc (value : Ref__a2l_import_1_DFSResult)
abbrev Configuration := Algo2LeanCore.Config Heap (Frame) Result
abbrev Stack := Algo2LeanCore.Stack (Frame) Result
abbrev Transcript := List (Configuration)
inductive Step : Configuration → Configuration → Prop where
| transpose_pc1 (h : Heap) (s : State_transpose) (stack : Stack) (defined : is__a2l_import_0_UnweightedGraph h s.t7) :
Step (.active h (Frame.fn_transpose 1 s) stack) (Algo2LeanCore.resumeConfig h (Result.fn_transpose (s.t7)) stack)
| transpose_pc2 (h : Heap) (s : State_transpose) (stack : Stack) :
Step (.active h (Frame.fn_transpose 2 s) stack) (.active h (Frame.import_0 (Algo.«graph_input».entry_UnweightedGraph (s.t8, s.t9, s.t10)) [] (fun value => match value with | .fn_UnweightedGraph result => (Frame.fn_transpose 1 { s with t7 := result }) | _ => .invalid)) stack)
| transpose_pc3 (h : Heap) (s : State_transpose) (stack : Stack) :
Step (.active h (Frame.fn_transpose 3 s) stack) (.active h (Frame.fn_transpose 2 { s with t10 := s.v2 }) stack)
| transpose_pc4 (h : Heap) (s : State_transpose) (stack : Stack) :
Step (.active h (Frame.fn_transpose 4 s) stack) (.active h (Frame.fn_transpose 3 { s with t9 := s.v1 }) stack)
| transpose_pc5 (h : Heap) (s : State_transpose) (stack : Stack) (defined : (((field__a2l_import_0_UnweightedGraph_size h (s.v0)).isSome = true))) :
Step (.active h (Frame.fn_transpose 5 s) stack) (.active h (Frame.fn_transpose 4 { s with t8 := ((field__a2l_import_0_UnweightedGraph_size h (s.v0)).getD 0) }) stack)
| transpose_pc6 (h : Heap) (s : State_transpose) (stack : Stack) :
Step (.active h (Frame.fn_transpose 6 s) stack) (.active (h.tick "graph_work" 1) (Frame.fn_transpose 5 s) stack)
| transpose_pc7_true (h : Heap) (s : State_transpose) (stack : Stack) (condition : s.t11 = true) :
Step (.active h (Frame.fn_transpose 7 s) stack) (.active h (Frame.fn_transpose 22 s) stack)
| transpose_pc7_false (h : Heap) (s : State_transpose) (stack : Stack) (condition : s.t11 = false) :
Step (.active h (Frame.fn_transpose 7 s) stack) (.active h (Frame.fn_transpose 6 s) stack)
| transpose_pc8 (h : Heap) (s : State_transpose) (stack : Stack) (defined : ((((field__a2l_import_0_UnweightedGraph_size h (s.v0)).isSome = true)))) :
Step (.active h (Frame.fn_transpose 8 s) stack) (.active h (Frame.fn_transpose 7 { s with t11 := (decide ((s.v3 < ((field__a2l_import_0_UnweightedGraph_size h (s.v0)).getD 0)))) }) stack)
| transpose_pc9 (h : Heap) (s : State_transpose) (stack : Stack) :
Step (.active h (Frame.fn_transpose 9 s) stack) (.active (h.tick "graph_work" 1) (Frame.fn_transpose 8 s) stack)
| transpose_pc10 (h : Heap) (s : State_transpose) (stack : Stack) :
Step (.active h (Frame.fn_transpose 10 s) stack) (.active h (Frame.fn_transpose 9 { s with v3 := (s.v3 + (1 : Int)) }) stack)
| transpose_pc11_true (h : Heap) (s : State_transpose) (stack : Stack) (condition : s.t12 = true) :
Step (.active h (Frame.fn_transpose 11 s) stack) (.active h (Frame.fn_transpose 18 s) stack)
| transpose_pc11_false (h : Heap) (s : State_transpose) (stack : Stack) (condition : s.t12 = false) :
Step (.active h (Frame.fn_transpose 11 s) stack) (.active h (Frame.fn_transpose 10 s) stack)
| transpose_pc12 (h : Heap) (s : State_transpose) (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_transpose 12 s) stack) (.active h (Frame.fn_transpose 11 { s with t12 := (decide ((s.v5 < (h.read ((field__a2l_import_0_UnweightedGraph_degree h (s.v0)).getD 0) s.v3)))) }) stack)
| transpose_pc13 (h : Heap) (s : State_transpose) (stack : Stack) :
Step (.active h (Frame.fn_transpose 13 s) stack) (.active (h.tick "graph_work" 1) (Frame.fn_transpose 12 s) stack)
| transpose_pc14 (h : Heap) (s : State_transpose) (stack : Stack) :
Step (.active h (Frame.fn_transpose 14 s) stack) (.active h (Frame.fn_transpose 13 { s with v5 := (s.v5 + (1 : Int)) }) stack)
| transpose_pc15 (h : Heap) (s : State_transpose) (stack : Stack) (defined : ((((s.v2 < h.nextRef)))) ∧ (s.v2 < h.nextRef)) :
Step (.active h (Frame.fn_transpose 15 s) stack) (.active (h.write s.v2 s.v6 ((h.read s.v2 s.v6) + (1 : Int))) (Frame.fn_transpose 14 s) stack)
| transpose_pc16 (h : Heap) (s : State_transpose) (stack : Stack) (defined : ((((seq_Seq_Int.get h s.v1 s.v6).isSome = true)) ∧ ((s.v2 < h.nextRef))) ∧ (((seq_Seq_Int.get h s.v1 s.v6).getD 0) < h.nextRef)) :
Step (.active h (Frame.fn_transpose 16 s) stack) (.active (h.write ((seq_Seq_Int.get h s.v1 s.v6).getD 0) (h.read s.v2 s.v6) s.v3) (Frame.fn_transpose 15 s) stack)
| transpose_pc17 (h : Heap) (s : State_transpose) (stack : Stack) (defined : (s.v4 < h.nextRef)) :
Step (.active h (Frame.fn_transpose 17 s) stack) (.active h (Frame.fn_transpose 16 { s with v6 := (h.read s.v4 s.v5) }) stack)
| transpose_pc18 (h : Heap) (s : State_transpose) (stack : Stack) :
Step (.active h (Frame.fn_transpose 18 s) stack) (.active (h.tick "graph_work" 1) (Frame.fn_transpose 17 s) stack)
| transpose_pc19 (h : Heap) (s : State_transpose) (stack : Stack) :
Step (.active h (Frame.fn_transpose 19 s) stack) (.active (h.tick "graph_work" 1) (Frame.fn_transpose 12 s) stack)
| transpose_pc20 (h : Heap) (s : State_transpose) (stack : Stack) :
Step (.active h (Frame.fn_transpose 20 s) stack) (.active h (Frame.fn_transpose 19 { s with v5 := (0 : Int) }) stack)
| transpose_pc21 (h : Heap) (s : State_transpose) (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)) :
Step (.active h (Frame.fn_transpose 21 s) stack) (.active h (Frame.fn_transpose 20 { s with v4 := ((seq_Seq_Int.get h ((field__a2l_import_0_UnweightedGraph_adj h (s.v0)).getD 0) s.v3).getD 0) }) stack)
| transpose_pc22 (h : Heap) (s : State_transpose) (stack : Stack) :
Step (.active h (Frame.fn_transpose 22 s) stack) (.active (h.tick "graph_work" 1) (Frame.fn_transpose 21 s) stack)
| transpose_pc23 (h : Heap) (s : State_transpose) (stack : Stack) :
Step (.active h (Frame.fn_transpose 23 s) stack) (.active (h.tick "graph_work" 1) (Frame.fn_transpose 8 s) stack)
| transpose_pc24 (h : Heap) (s : State_transpose) (stack : Stack) :
Step (.active h (Frame.fn_transpose 24 s) stack) (.active h (Frame.fn_transpose 23 { s with v3 := (0 : Int) }) stack)
| transpose_pc25_true (h : Heap) (s : State_transpose) (stack : Stack) (condition : s.t13 = true) :
Step (.active h (Frame.fn_transpose 25 s) stack) (.active h (Frame.fn_transpose 34 s) stack)
| transpose_pc25_false (h : Heap) (s : State_transpose) (stack : Stack) (condition : s.t13 = false) :
Step (.active h (Frame.fn_transpose 25 s) stack) (.active h (Frame.fn_transpose 24 s) stack)
| transpose_pc26 (h : Heap) (s : State_transpose) (stack : Stack) (defined : ((((field__a2l_import_0_UnweightedGraph_size h (s.v0)).isSome = true)))) :
Step (.active h (Frame.fn_transpose 26 s) stack) (.active h (Frame.fn_transpose 25 { s with t13 := (decide ((s.v3 < ((field__a2l_import_0_UnweightedGraph_size h (s.v0)).getD 0)))) }) stack)
| transpose_pc27 (h : Heap) (s : State_transpose) (stack : Stack) :
Step (.active h (Frame.fn_transpose 27 s) stack) (.active (h.tick "graph_work" 1) (Frame.fn_transpose 26 s) stack)
| transpose_pc28 (h : Heap) (s : State_transpose) (stack : Stack) :
Step (.active h (Frame.fn_transpose 28 s) stack) (.active h (Frame.fn_transpose 27 { s with v3 := (s.v3 + (1 : Int)) }) stack)
| transpose_pc29 (h : Heap) (s : State_transpose) (stack : Stack) (defined : (seq_Seq_Int.valid h s.t16)) :
Step (.active h (Frame.fn_transpose 29 s) stack) (.active (seq_Seq_Int.set h s.t16 s.t15 s.t14) (Frame.fn_transpose 28 s) stack)
| transpose_pc30 (h : Heap) (s : State_transpose) (stack : Stack) :
Step (.active h (Frame.fn_transpose 30 s) stack) (.active h (Frame.fn_transpose 29 { s with t15 := s.v3 }) stack)
| transpose_pc31 (h : Heap) (s : State_transpose) (stack : Stack) :
Step (.active h (Frame.fn_transpose 31 s) stack) (.active h (Frame.fn_transpose 30 { s with t16 := s.v1 }) stack)
| transpose_pc32 (h : Heap) (s : State_transpose) (stack : Stack) :
Step (.active h (Frame.fn_transpose 32 s) stack) (.active (h.allocate (fun _ => s.t17)) (Frame.fn_transpose 31 { s with t14 := h.nextRef }) stack)
| transpose_pc33 (h : Heap) (s : State_transpose) (stack : Stack) :
Step (.active h (Frame.fn_transpose 33 s) stack) (.active h (Frame.fn_transpose 32 { s with t17 := (0 : Int) }) stack)
| transpose_pc34 (h : Heap) (s : State_transpose) (stack : Stack) :
Step (.active h (Frame.fn_transpose 34 s) stack) (.active (h.tick "graph_work" 1) (Frame.fn_transpose 33 s) stack)
| transpose_pc35 (h : Heap) (s : State_transpose) (stack : Stack) :
Step (.active h (Frame.fn_transpose 35 s) stack) (.active (h.tick "graph_work" 1) (Frame.fn_transpose 26 s) stack)
| transpose_pc36 (h : Heap) (s : State_transpose) (stack : Stack) :
Step (.active h (Frame.fn_transpose 36 s) stack) (.active h (Frame.fn_transpose 35 { s with v3 := (0 : Int) }) stack)
| transpose_pc37 (h : Heap) (s : State_transpose) (stack : Stack) :
Step (.active h (Frame.fn_transpose 37 s) stack) (.active h (Frame.fn_transpose 36 { s with v2 := s.t18 }) stack)
| transpose_pc38 (h : Heap) (s : State_transpose) (stack : Stack) :
Step (.active h (Frame.fn_transpose 38 s) stack) (.active (h.allocate (fun _ => s.t19)) (Frame.fn_transpose 37 { s with t18 := h.nextRef }) stack)
| transpose_pc39 (h : Heap) (s : State_transpose) (stack : Stack) :
Step (.active h (Frame.fn_transpose 39 s) stack) (.active h (Frame.fn_transpose 38 { s with t19 := (0 : Int) }) stack)
| transpose_pc40 (h : Heap) (s : State_transpose) (stack : Stack) :
Step (.active h (Frame.fn_transpose 40 s) stack) (.active h (Frame.fn_transpose 39 { s with v1 := s.t20 }) stack)
| transpose_pc41 (h : Heap) (s : State_transpose) (stack : Stack) :
Step (.active h (Frame.fn_transpose 41 s) stack) (.active (seq_Seq_Int.const h s.t21).1 (Frame.fn_transpose 40 { s with t20 := h.nextCollection }) stack)
| transpose_pc42 (h : Heap) (s : State_transpose) (stack : Stack) :
Step (.active h (Frame.fn_transpose 42 s) stack) (.active (h.allocate (fun _ => s.t22)) (Frame.fn_transpose 41 { s with t21 := h.nextRef }) stack)
| transpose_pc43 (h : Heap) (s : State_transpose) (stack : Stack) :
Step (.active h (Frame.fn_transpose 43 s) stack) (.active h (Frame.fn_transpose 42 { s with t22 := (0 : Int) }) stack)
| transpose_pc44 (h : Heap) (s : State_transpose) (stack : Stack) :
Step (.active h (Frame.fn_transpose 44 s) stack) (.active (h.tick "graph_work" 1) (Frame.fn_transpose 43 s) stack)
| scc_pc1 (h : Heap) (s : State_scc) (stack : Stack) (defined : is__a2l_import_1_DFSResult h s.t5) :
Step (.active h (Frame.fn_scc 1 s) stack) (Algo2LeanCore.resumeConfig h (Result.fn_scc (s.t5)) stack)
| scc_pc2 (h : Heap) (s : State_scc) (stack : Stack) :
Step (.active h (Frame.fn_scc 2 s) stack) (.active h (Frame.import_1 (Algo.«dfs».entry_dfs_ordered (s.t6, s.t7)) [] (fun value => match value with | .fn_dfs_ordered result => (Frame.fn_scc 1 { s with t5 := result }) | _ => .invalid)) stack)
| scc_pc3 (h : Heap) (s : State_scc) (stack : Stack) :
Step (.active h (Frame.fn_scc 3 s) stack) (.active h (Frame.fn_scc 2 { s with t7 := s.v3 }) stack)
| scc_pc4 (h : Heap) (s : State_scc) (stack : Stack) :
Step (.active h (Frame.fn_scc 4 s) stack) (.active h (Frame.fn_scc 3 { s with t6 := s.v2 }) stack)
| scc_pc5 (h : Heap) (s : State_scc) (stack : Stack) :
Step (.active h (Frame.fn_scc 5 s) stack) (.active (h.tick "graph_work" 1) (Frame.fn_scc 4 s) stack)
| scc_pc6_true (h : Heap) (s : State_scc) (stack : Stack) (condition : s.t8 = true) :
Step (.active h (Frame.fn_scc 6 s) stack) (.active h (Frame.fn_scc 11 s) stack)
| scc_pc6_false (h : Heap) (s : State_scc) (stack : Stack) (condition : s.t8 = false) :
Step (.active h (Frame.fn_scc 6 s) stack) (.active h (Frame.fn_scc 5 s) stack)
| scc_pc7 (h : Heap) (s : State_scc) (stack : Stack) (defined : ((((field__a2l_import_0_UnweightedGraph_size h (s.v0)).isSome = true)))) :
Step (.active h (Frame.fn_scc 7 s) stack) (.active h (Frame.fn_scc 6 { s with t8 := (decide ((s.v4 < ((field__a2l_import_0_UnweightedGraph_size h (s.v0)).getD 0)))) }) stack)
| scc_pc8 (h : Heap) (s : State_scc) (stack : Stack) :
Step (.active h (Frame.fn_scc 8 s) stack) (.active (h.tick "graph_work" 1) (Frame.fn_scc 7 s) stack)
| scc_pc9 (h : Heap) (s : State_scc) (stack : Stack) :
Step (.active h (Frame.fn_scc 9 s) stack) (.active h (Frame.fn_scc 8 { s with v4 := (s.v4 + (1 : Int)) }) stack)
| scc_pc10 (h : Heap) (s : State_scc) (stack : Stack) (defined : ((((((field__a2l_import_1_DFSResult_order h (s.v1)).isSome = true))) ∧ ((((((field__a2l_import_0_UnweightedGraph_size h (s.v0)).isSome = true))))) ∧ (((field__a2l_import_1_DFSResult_order h (s.v1)).getD 0) < h.nextRef))) ∧ (s.v3 < h.nextRef)) :
Step (.active h (Frame.fn_scc 10 s) stack) (.active (h.write s.v3 s.v4 (h.read ((field__a2l_import_1_DFSResult_order h (s.v1)).getD 0) ((((field__a2l_import_0_UnweightedGraph_size h (s.v0)).getD 0) - (1 : Int)) - s.v4))) (Frame.fn_scc 9 s) stack)
| scc_pc11 (h : Heap) (s : State_scc) (stack : Stack) :
Step (.active h (Frame.fn_scc 11 s) stack) (.active (h.tick "graph_work" 1) (Frame.fn_scc 10 s) stack)
| scc_pc12 (h : Heap) (s : State_scc) (stack : Stack) :
Step (.active h (Frame.fn_scc 12 s) stack) (.active (h.tick "graph_work" 1) (Frame.fn_scc 7 s) stack)
| scc_pc13 (h : Heap) (s : State_scc) (stack : Stack) :
Step (.active h (Frame.fn_scc 13 s) stack) (.active h (Frame.fn_scc 12 { s with v4 := (0 : Int) }) stack)
| scc_pc14 (h : Heap) (s : State_scc) (stack : Stack) :
Step (.active h (Frame.fn_scc 14 s) stack) (.active h (Frame.fn_scc 13 { s with v3 := s.t9 }) stack)
| scc_pc15 (h : Heap) (s : State_scc) (stack : Stack) :
Step (.active h (Frame.fn_scc 15 s) stack) (.active (h.allocate (fun _ => s.t10)) (Frame.fn_scc 14 { s with t9 := h.nextRef }) stack)
| scc_pc16 (h : Heap) (s : State_scc) (stack : Stack) :
Step (.active h (Frame.fn_scc 16 s) stack) (.active h (Frame.fn_scc 15 { s with t10 := (-(1 : Int)) }) stack)
| scc_pc17 (h : Heap) (s : State_scc) (stack : Stack) :
Step (.active h (Frame.fn_scc 17 s) stack) (.active (h.tick "graph_work" 1) (Frame.fn_scc 16 s) stack)
| scc_pc18 (h : Heap) (s : State_scc) (stack : Stack) :
Step (.active h (Frame.fn_scc 18 s) stack) (.active h (Frame.fn_scc 17 { s with v2 := s.t11 }) stack)
| scc_pc19 (h : Heap) (s : State_scc) (stack : Stack) :
Step (.active h (Frame.fn_scc 19 s) stack) (.active h (Frame.fn_transpose 44 ({ v0 := s.t12 } : State_transpose)) ((fun value => match value with | .fn_transpose result => (Frame.fn_scc 18 { s with t11 := result }) | _ => .invalid) :: stack))
| scc_pc20 (h : Heap) (s : State_scc) (stack : Stack) :
Step (.active h (Frame.fn_scc 20 s) stack) (.active h (Frame.fn_scc 19 { s with t12 := s.v0 }) stack)
| scc_pc21 (h : Heap) (s : State_scc) (stack : Stack) :
Step (.active h (Frame.fn_scc 21 s) stack) (.active (h.tick "graph_work" 1) (Frame.fn_scc 20 s) stack)
| scc_pc22 (h : Heap) (s : State_scc) (stack : Stack) :
Step (.active h (Frame.fn_scc 22 s) stack) (.active h (Frame.fn_scc 21 { s with v1 := s.t13 }) stack)
| scc_pc23 (h : Heap) (s : State_scc) (stack : Stack) :
Step (.active h (Frame.fn_scc 23 s) stack) (.active h (Frame.import_1 (Algo.«dfs».entry_dfs s.t14) [] (fun value => match value with | .fn_dfs result => (Frame.fn_scc 22 { s with t13 := result }) | _ => .invalid)) stack)
| scc_pc24 (h : Heap) (s : State_scc) (stack : Stack) :
Step (.active h (Frame.fn_scc 24 s) stack) (.active h (Frame.fn_scc 23 { s with t14 := s.v0 }) stack)
| scc_pc25 (h : Heap) (s : State_scc) (stack : Stack) :
Step (.active h (Frame.fn_scc 25 s) stack) (.active (h.tick "graph_work" 1) (Frame.fn_scc 24 s) stack)
| import_0 (h : Heap) (frame : Algo.«graph_input».Algo2LeanGenerated.Frame) (inner : Algo.«graph_input».Algo2LeanGenerated.Stack)
(resume : Algo.«graph_input».Algo2LeanGenerated.Result → Frame) (caller : Stack) (after : Algo.«graph_input».Algo2LeanGenerated.Configuration)
(transition : Algo.«graph_input».Algo2LeanGenerated.Step (.active h frame inner) after) :
Step (.active h (Frame.import_0 frame inner resume) caller)
(Algo2LeanCore.ModuleCall.config Frame.import_0 resume caller after)
| import_1 (h : Heap) (frame : Algo.«dfs».Algo2LeanGenerated.Frame) (inner : Algo.«dfs».Algo2LeanGenerated.Stack)
(resume : Algo.«dfs».Algo2LeanGenerated.Result → Frame) (caller : Stack) (after : Algo.«dfs».Algo2LeanGenerated.Configuration)
(transition : Algo.«dfs».Algo2LeanGenerated.Step (.active h frame inner) after) :
Step (.active h (Frame.import_1 frame inner resume) caller)
(Algo2LeanCore.ModuleCall.config Frame.import_1 resume caller after)
theorem terminal (h : Heap) (result : Result) :
Algo2LeanCore.Terminal Step (.done h result) := by
intro next transition
cases transition
theorem import_0_simulates :
Algo2LeanCore.ModuleCall.Simulates Frame.import_0 Algo.«graph_input».Algo2LeanGenerated.Step Step := by
apply Algo2LeanCore.ModuleCall.Delegates.simulates
· exact Step.import_0
· exact Algo.«graph_input».Algo2LeanGenerated.terminal
theorem import_1_simulates :
Algo2LeanCore.ModuleCall.Simulates Frame.import_1 Algo.«dfs».Algo2LeanGenerated.Step Step := by
apply Algo2LeanCore.ModuleCall.Delegates.simulates
· exact Step.import_1
· exact Algo.«dfs».Algo2LeanGenerated.terminal
end Algo2LeanGenerated
open Algo2LeanGenerated
def entry_transpose (input : Ref__a2l_import_0_UnweightedGraph) : Frame :=
(Frame.fn_transpose 44 ({ v0 := input } : State_transpose))
def transpose.ValidInput (h : Heap) (input : Ref__a2l_import_0_UnweightedGraph) : Prop := is__a2l_import_0_UnweightedGraph h input
def transpose.initial (h : Heap) (input : Ref__a2l_import_0_UnweightedGraph) : Configuration :=
Algo2LeanCore.start h (Frame.fn_transpose 44 ({ v0 := input } : State_transpose))
def transpose.Run (h : Heap) (input : Ref__a2l_import_0_UnweightedGraph) (h' : Heap) (output : Ref__a2l_import_0_UnweightedGraph) : Prop :=
_root_.Algo.«scc».transpose.ValidInput h input ∧ Algo2LeanCore.Reaches Step (_root_.Algo.«scc».transpose.initial h input) (.done h' (Result.fn_transpose output))
def transpose.ValidHeapTranscript (h : Heap) (input : Ref__a2l_import_0_UnweightedGraph) (trace : Transcript) : Prop :=
_root_.Algo.«scc».transpose.ValidInput h input ∧ ∃ final, Algo2LeanCore.Valid Step (_root_.Algo.«scc».transpose.initial h input) trace final
def transpose.Call (h : Heap) (input : Ref__a2l_import_0_UnweightedGraph) (h' : Heap) (output : Ref__a2l_import_0_UnweightedGraph) : Prop :=
_root_.Algo.«scc».transpose.ValidInput h input ∧ Algo2LeanCore.Summary Step h (Frame.fn_transpose 44 ({ v0 := input } : State_transpose)) h' (Result.fn_transpose output)
-- Complete this function from the supplied local state, under any caller stack.
def transpose.CallFrom (state : Configuration) (finalHeap : Heap) (output : Ref__a2l_import_0_UnweightedGraph) : Prop :=
match state with
| .active heap (Frame.fn_transpose pc locals) _ =>
Algo2LeanCore.Summary Step heap (Frame.fn_transpose pc locals) finalHeap (Result.fn_transpose output)
| _ => False
-- Object inputs carry their heap, preserving shared references and cycles.
def transpose.load (input : Heap × (Ref__a2l_import_0_UnweightedGraph)) : Heap × (Ref__a2l_import_0_UnweightedGraph) := input
def transpose.ValidTranscript (my_input : Heap × (Ref__a2l_import_0_UnweightedGraph)) (trace : Transcript) : Prop :=
let loaded := _root_.Algo.«scc».transpose.load my_input
_root_.Algo.«scc».transpose.ValidHeapTranscript loaded.1 loaded.2 trace
def transpose.Returns (my_input : Heap × (Ref__a2l_import_0_UnweightedGraph)) (my_output : Heap × (Ref__a2l_import_0_UnweightedGraph)) : Prop :=
let loaded := _root_.Algo.«scc».transpose.load my_input
_root_.Algo.«scc».transpose.Run loaded.1 loaded.2 my_output.1 my_output.2
-- Output and clock increments from one completed execution.
def transpose.ReturnsWithCost (my_input : Heap × (Ref__a2l_import_0_UnweightedGraph)) (my_output : Heap × (Ref__a2l_import_0_UnweightedGraph)) (costs : Clocks) : Prop :=
let loaded := _root_.Algo.«scc».transpose.load my_input
_root_.Algo.«scc».transpose.Run loaded.1 loaded.2 my_output.1 my_output.2 ∧ Heap.cost loaded.1 my_output.1 = costs
theorem transpose.ReturnsWithCost.returns {input output costs}
(run : _root_.Algo.«scc».transpose.ReturnsWithCost input output costs) : _root_.Algo.«scc».transpose.Returns input output := by
obtain ⟨execution, _⟩ := run
exact execution
theorem transpose.Returns.withCost {input output}
(run : _root_.Algo.«scc».transpose.Returns input output) : ∃ costs, _root_.Algo.«scc».transpose.ReturnsWithCost input output costs := by
exact ⟨Heap.cost (_root_.Algo.«scc».transpose.load input).1 output.1, run, rfl⟩
theorem transpose.Call.run {before input after output}
(call : _root_.Algo.«scc».transpose.Call before input after output) :
_root_.Algo.«scc».transpose.Run before input after output :=
⟨call.1, call.2.root⟩
def entry_scc (input : Ref__a2l_import_0_UnweightedGraph) : Frame :=
(Frame.fn_scc 25 ({ v0 := input } : State_scc))
def scc.ValidInput (h : Heap) (input : Ref__a2l_import_0_UnweightedGraph) : Prop := is__a2l_import_0_UnweightedGraph h input
def scc.initial (h : Heap) (input : Ref__a2l_import_0_UnweightedGraph) : Configuration :=
Algo2LeanCore.start h (Frame.fn_scc 25 ({ v0 := input } : State_scc))
def scc.Run (h : Heap) (input : Ref__a2l_import_0_UnweightedGraph) (h' : Heap) (output : Ref__a2l_import_1_DFSResult) : Prop :=
_root_.Algo.«scc».scc.ValidInput h input ∧ Algo2LeanCore.Reaches Step (_root_.Algo.«scc».scc.initial h input) (.done h' (Result.fn_scc output))
def scc.ValidHeapTranscript (h : Heap) (input : Ref__a2l_import_0_UnweightedGraph) (trace : Transcript) : Prop :=
_root_.Algo.«scc».scc.ValidInput h input ∧ ∃ final, Algo2LeanCore.Valid Step (_root_.Algo.«scc».scc.initial h input) trace final
def scc.Call (h : Heap) (input : Ref__a2l_import_0_UnweightedGraph) (h' : Heap) (output : Ref__a2l_import_1_DFSResult) : Prop :=
_root_.Algo.«scc».scc.ValidInput h input ∧ Algo2LeanCore.Summary Step h (Frame.fn_scc 25 ({ v0 := input } : State_scc)) h' (Result.fn_scc output)
-- Complete this function from the supplied local state, under any caller stack.
def scc.CallFrom (state : Configuration) (finalHeap : Heap) (output : Ref__a2l_import_1_DFSResult) : Prop :=
match state with
| .active heap (Frame.fn_scc pc locals) _ =>
Algo2LeanCore.Summary Step heap (Frame.fn_scc pc locals) finalHeap (Result.fn_scc output)
| _ => False
-- Object inputs carry their heap, preserving shared references and cycles.
def scc.load (input : Heap × (Ref__a2l_import_0_UnweightedGraph)) : Heap × (Ref__a2l_import_0_UnweightedGraph) := input
def scc.ValidTranscript (my_input : Heap × (Ref__a2l_import_0_UnweightedGraph)) (trace : Transcript) : Prop :=
let loaded := _root_.Algo.«scc».scc.load my_input
_root_.Algo.«scc».scc.ValidHeapTranscript loaded.1 loaded.2 trace
def scc.Returns (my_input : Heap × (Ref__a2l_import_0_UnweightedGraph)) (my_output : Heap × (Ref__a2l_import_1_DFSResult)) : Prop :=
let loaded := _root_.Algo.«scc».scc.load my_input
_root_.Algo.«scc».scc.Run loaded.1 loaded.2 my_output.1 my_output.2
-- Output and clock increments from one completed execution.
def scc.ReturnsWithCost (my_input : Heap × (Ref__a2l_import_0_UnweightedGraph)) (my_output : Heap × (Ref__a2l_import_1_DFSResult)) (costs : Clocks) : Prop :=
let loaded := _root_.Algo.«scc».scc.load my_input
_root_.Algo.«scc».scc.Run loaded.1 loaded.2 my_output.1 my_output.2 ∧ Heap.cost loaded.1 my_output.1 = costs
theorem scc.ReturnsWithCost.returns {input output costs}
(run : _root_.Algo.«scc».scc.ReturnsWithCost input output costs) : _root_.Algo.«scc».scc.Returns input output := by
obtain ⟨execution, _⟩ := run
exact execution
theorem scc.Returns.withCost {input output}
(run : _root_.Algo.«scc».scc.Returns input output) : ∃ costs, _root_.Algo.«scc».scc.ReturnsWithCost input output costs := by
exact ⟨Heap.cost (_root_.Algo.«scc».scc.load input).1 output.1, run, rfl⟩
theorem scc.Call.run {before input after output}
(call : _root_.Algo.«scc».scc.Call before input after output) :
_root_.Algo.«scc».scc.Run before input after output :=
⟨call.1, call.2.root⟩
end Algo.«scc»
set_option autoImplicit false
namespace CLRS.SCC
open Algo2LeanGenerated CLRS.GraphTraversal
/-- The same returning call supplies a fresh component array and a contiguous,
nonempty label for every strongly connected component of the original graph.
Labels themselves are not canonical. The result object is the DFS result of
the second pass on the transpose; only its component fields are specified here.
All previously allocated caller storage and every other clock are preserved. -/
def Post (before after : Heap) (result : ObjectRef) (g : Graph) : Prop :=
Algo.dfs.Algo2LeanGenerated.is_DFSResult after result ∧
FreshObject before after result ∧
Preserves before after ∧
∃ (component : SeqRef) (count : Nat),
Algo.dfs.Algo2LeanGenerated.field_DFSResult_component after result = some component ∧
Algo.dfs.Algo2LeanGenerated.field_DFSResult_components after result = some (count : Int) ∧
FreshArrays before after [component] ∧
count ≤ g.size ∧
(count = 0 ↔ g.size = 0) ∧
(∀ vertex, Vertex g vertex →
0 ≤ after.read component vertex ∧ after.read component vertex < (count : Int)) ∧
(∀ label : Nat, label < count →
∃ vertex, Vertex g vertex ∧ after.read component vertex = (label : Int)) ∧
(∀ u v, Vertex g u → Vertex g v →
(after.read component u = after.read component v ↔ StronglyConnected g u v))
/-- Transposition returns a newly allocated graph representing all reversed
adjacency occurrences, including their multiplicities. Its vertex and total
occurrence counts are unchanged. The original caller storage is preserved. -/
def TransposePost (before after : Heap) (result : ObjectRef) (g : Graph) : Prop :=
FreshObject before after result ∧
Preserves before after ∧
∃ transposed : Graph,
GraphRep after result transposed ∧
IsTranspose g transposed ∧
edgeCount transposed = edgeCount g
end CLRS.SCC
Read-back
What the Lean code literally says, in plain math · GPT-6 (Codex, independent fresh-context agent)
This bundle defines heap transitions for transposition and a two-pass component procedure, together with two output predicates; these definitions do not by themselves establish their correctness or running-time bounds. Let be a finite directed multigraph with vertices numbered , whose adjacency lists contain only these vertices, and let be the sum of the lengths of these lists, counting parallel occurrences and self-loops. Its rows at other natural-number indices are irrelevant. A represented input consists of an arbitrary initial heap and a natural-number object reference below its object-allocation counter, of class graph_input.UnweightedGraph, with integer size field , a valid allocated outer collection tagged Seq[Int], and an allocated integer-array reference for degrees. For each vertex , the degree entry equals the length of 's adjacency list at , the outer collection entry decodes to an allocated integer-array reference, and that array's declared prefix equals that list entry by entry. Arrays are total functions from integers to integers; values outside the declared prefixes are unrestricted, and the input arrays may alias. Transposition allocates a zero-filled default integer row, a typed outer collection initially containing that reference at every integer index, and a zero-filled degree array; it then replaces each of the first outer entries with a separately allocated zero-filled row. Scanning original vertices in increasing order and each declared adjacency prefix in order, each encountered occurrence appends to the current end of new row and increments its degree. It then invokes the imported graph constructor with the original size and the new collection and degree references. The component procedure first invokes the imported default DFS on the original graph, computes a transpose, allocates a priority array whose first entries reverse the first pass's finish-order array, invokes imported ordered DFS on the transpose with that priority, and returns that second DFS result object. Imported calls delegate the imported module's actual transitions over the same heap and clocks and keep the caller's outer stack; the bundle does not replace them with an assumed correctness relation. Both procedures' low-level validity checks require only an allocated graph object of the expected class. Their Run predicates require shallow validity and a finite entry-to-return transition sequence, their Call predicates require shallow validity and a return to the same chosen final heap and result under every caller stack, and their CallFrom predicates use a matching active function's supplied locals and program counter under every stack, being false for other configurations. Valid transcripts may be unfinished prefixes. Loaders use the supplied heap unchanged; return predicates expose the final heap and object, and cost-decorated return predicates use named-clock increments from that very execution. Work is the final graph_work clock minus its initial value, using natural-number subtraction; the preservation requirement makes this an ordinary nonnegative increment. It counts only explicit unit markers in the transition rules, including nested calls, from the caller's actual initial clock; it is not the number of transitions, elapsed time, bit complexity, or a bound on memory use. For arbitrary heaps , result , and graph , the component postcondition is precisely the following, together with preservation; it does not itself assert that a call occurred or that was represented initially. The returned is an allocated object of class dfs.DFSResult, fresh in the sense that its reference is at least 's initial object counter and below 's final object counter. Its component field names an allocated integer array with reference at least 's initial array counter and below 's final array counter, and its integer components field equals a natural number . One has if and only if . Every valid vertex's component value is an integer in , and every natural label less than occurs at some valid vertex. For every pair of valid vertices , their component values are equal if and only if there is a finite directed walk in the original graph from to and a finite directed walk from to ; walks may repeat vertices and include the zero-edge walk at a valid vertex. Thus the stated equivalence uses the original graph and both directions of reachability. The postcondition gives no canonical numbering of labels, no constraint on the component array outside valid vertices, and no mathematical requirements on the returned object's other fields. Preservation means that every integer array below 's initial array-allocation counter is unchanged at every integer index, every initially allocated object and typed collection is unchanged in full, all three allocation counters do not decrease, the natural-number graph_work clock does not decrease, and every differently named clock is exactly unchanged. For the same arbitrary parameters, the transpose postcondition requires preservation and the following. The returned is a fresh object reference, at least 's initial object counter and below 's object counter. It represents some finite directed multigraph in by the same class, field, allocated-collection, degree, and adjacency-prefix conditions used for the input. The graph has vertices, and for every natural , the number of occurrences of in 's row equals the number of occurrences of in 's row . Its total number of adjacency occurrences equals . This specifies reversal with multiplicity, while permitting a different adjacency order. The postcondition requires the graph object to be fresh but does not separately require its degree array, outer collection, or row arrays to be fresh or mutually distinct. Both postconditions include ; the component count must then be zero, and transpose edge-multiplicity conditions have no vertex instances, while the respective fresh-object, representation, component-array, and preservation requirements remain. All three supplied SCC/transpose correctness/running-time goals are open and end in sorry; the proved import-simulation and wrapper lemmas do not discharge those goals.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.