Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Two-pass SCC program, graph transpose, and component specifications

Definition
CLRS_SCC_Program

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

algo2leanalgorithmsclrsgraph-theoryrunning-timetextbook

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

Definition code
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
Source
CLRS, Introduction to Algorithms, fourth edition (MIT Press, 2022), Chapter 20, §20.5. https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/ ; new arrays-of-arrays implementation compiled with Algo2Lean v0.1.4, https://www.algo2lean.com/versions/v0.1.4/ . Source filenames and full code are in the mission description.
Read-back

What the Lean code literally says, in plain math · GPT-6 (Codex, independent fresh-context agent)

This bundle defines 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 ggg be a finite directed multigraph with nnn vertices numbered 0,…,n−10,\ldots,n-10,…,n−1, whose adjacency lists contain only these vertices, and let mmm be the sum of the lengths of these nnn 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 HHH and a natural-number object reference rrr below its object-allocation counter, of class graph_input.UnweightedGraph, with integer size field nnn, a valid allocated outer collection tagged Seq[Int], and an allocated integer-array reference for degrees. For each vertex uuu, the degree entry equals the length of ggg's adjacency list at uuu, 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 nnn 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 u→vu\to vu→v appends uuu to the current end of new row vvv 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 nnn 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 H,H′H,H'H,H′, result qqq, and graph ggg, the component postcondition is precisely the following, together with preservation; it does not itself assert that a call occurred or that ggg was represented initially. The returned qqq is an allocated object of class dfs.DFSResult, fresh in the sense that its reference is at least HHH's initial object counter and below H′H'H′'s final object counter. Its component field names an allocated integer array with reference at least HHH's initial array counter and below H′H'H′'s final array counter, and its integer components field equals a natural number k≤nk\le nk≤n. One has k=0k=0k=0 if and only if n=0n=0n=0. Every valid vertex's component value is an integer in {0,…,k−1}\{0,\ldots,k-1\}{0,…,k−1}, and every natural label less than kkk occurs at some valid vertex. For every pair of valid vertices u,vu,vu,v, their component values are equal if and only if there is a finite directed walk in the original graph from uuu to vvv and a finite directed walk from vvv to uuu; 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 HHH'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 qqq is a fresh object reference, at least HHH's initial object counter and below H′H'H′'s object counter. It represents some finite directed multigraph ttt in H′H'H′ by the same class, field, allocated-collection, degree, and adjacency-prefix conditions used for the input. The graph ttt has nnn vertices, and for every natural u,v<nu,v<nu,v<n, the number of occurrences of vvv in ttt's row uuu equals the number of occurrences of uuu in ggg's row vvv. Its total number of adjacency occurrences equals mmm. 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 n=0n=0n=0; 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.

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