Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Algo.kruskal_scan.Analysis definitions

Definition
Algo_kruskal_scan_Analysis_SortedRevision

by lunjia · Oct 11, 2026 · Mathlib 0df444a (Lean v4.33.1)

algo2leanalgorithmsclrsdata-structuresrunning-timetextbook

Definitions and required structural lemmas from Algo.kruskal_scan.Analysis. Source declarations are retained by compiler-reported ranges; imports are redirected to the corresponding definition bundles. This bundle contains no theorem stubs.

<!-- algo2lean-provenance-v0.1.4 -->

Algo2Lean provenance and reproduction. These definitions target Algo2Lean v0.1.4, using the compiler source at public commit 0f79d5e4242e6477531c9ee4410409f5b1c92f76, and Lean 4.33.1. The versioned compiler location is Algo2Lean v0.1.4. Compile all supplied .algo files and imports to reproduce the raw generated definitions. Release publication and exact website parity require their separately recorded checks; this metadata alone does not assert them. Prove2Me imports and declaration packaging are mechanically adapted, with original hashes, compiler-reported source ranges, and adaptations recorded in transplant provenance. Exact reproduction does not prove the compiler correct.

Definition code
import Definitions.Def_Algo_kruskal_sorted_Generated
import Definitions.Def_Algo_kruskal_sorted_Facts
import Definitions.Def_Algo_kruskal_sorted_Points
import Definitions.Def_Algo_union_find_init_Analysis
import Definitions.Def_Algo2LeanLib_KruskalMath
import Definitions.Def_Algo2LeanLib_Footprint

set_option autoImplicit true
set_option backward.isDefEq.respectTransparency false
set_option backward.defeqAttrib.useBackward true



set_option backward.isDefEq.respectTransparency false
set_option backward.defeqAttrib.useBackward true

/-!
The post-sorting Kruskal entry point initializes singleton components and
compares representatives before selecting an edge and applying the verified union.
The graph argument is independent of the storage and transition machinery.
-/

namespace KruskalAnalysis

open Algo2LeanCore Algo2LeanGenerated
open Algo.kruskal_sorted Algo.kruskal_sorted.Algo2LeanGenerated
open UnionFindAnalysis
open Algo2Lean.Kruskal

/-- An accepted edge is marked; a rejected edge leaves the flags unchanged. -/
def selectHeap (heap : Heap) (chosen : SeqRef) (edge : Int) (accepted : Bool) : Heap :=
  if accepted then heap.write chosen edge 1 else heap

/-- The four client arrays and the separately represented union-find object. -/
structure ScanLayout where
  sets : UnionFindAnalysis.Layout
  sources : SeqRef
  targets : SeqRef
  order : SeqRef
  chosen : SeqRef

/-- A flag array records exactly the selected edge identifiers. -/
def Flags (values : Seq) (selected : List Edge) : Prop :=
  ∀ id : Int, values id = (if selected.any (fun edge => (edge.id : Int) == id) then 1 else 0)

/-- The unprocessed suffix of the identifier array. -/
inductive Order (heap : Heap) (ref : SeqRef) : Int → List Edge → Prop where
  | nil (index : Int) : Order heap ref index []
  | cons {index : Int} {edge : Edge} {rest : List Edge}
      (head : heap.read ref index = (edge.id : Int))
      (tail : Order heap ref (index + 1) rest) : Order heap ref index (edge :: rest)

/-- Storage, graph connectivity, and output flags agree at a scan boundary. -/
structure ScanInvariant (n : Nat) (data : ScanLayout) (heap : Heap)
    (model : Algo2Lean.UnionFind.State n) (index : Int) (pending selected : List Edge) : Prop where
  representation : Rep heap data.sets model
  partition : ∀ u v : Fin n, Algo2Lean.UnionFind.Connected model u v ↔
    Connected selected (u.val : Int) (v.val : Int)
  bounded : ∀ edge ∈ pending,
    (0 ≤ edge.source ∧ edge.source < (n : Int)) ∧ (0 ≤ edge.target ∧ edge.target < (n : Int))
  sources : ∀ edge ∈ pending, heap.read data.sources edge.id = edge.source
  targets : ∀ edge ∈ pending, heap.read data.targets edge.id = edge.target
  ordered : Order heap data.order index pending
  flags : Flags (heap.read data.chosen) selected
  sourceAllocated : data.sources < heap.nextRef
  targetAllocated : data.targets < heap.nextRef
  orderAllocated : data.order < heap.nextRef
  chosenAllocated : data.chosen < heap.nextRef
  sourceProtected : data.sources ∉ [data.sets.parent, data.sets.rank, data.chosen]
  targetProtected : data.targets ∉ [data.sets.parent, data.sets.rank, data.chosen]
  orderProtected : data.order ∉ [data.sets.parent, data.sets.rank, data.chosen]
  chosenProtected : data.chosen ∉ [data.sets.parent, data.sets.rank]

/-- Work performed by the scan and its union-find calls. Sorting is accounted
    for separately by its reusable sorting contract. -/
def work (clocks : Clocks) : Nat := UnionFindAnalysis.work clocks + clocks "kruskal"












/-- Source-facing values needed at the edge-loop boundary. -/
structure ScanLocals (data : ScanLayout) (index count : Int) (state : Configuration) : Prop where
  location : kruskal_sorted.At.scan state
  sets : kruskal_sorted.Local.sets state = some data.sets.object
  sources : kruskal_sorted.Local.sources state = some data.sources
  targets : kruskal_sorted.Local.targets state = some data.targets
  order : kruskal_sorted.Local.order state = some data.order
  chosen : kruskal_sorted.Local.chosen state = some data.chosen
  index : kruskal_sorted.Local.index state = some index
  count : kruskal_sorted.Local.count state = some count

/-- Complete the edge loop from any configuration with these local values.
    The caller's stack and irrelevant temporary variables remain unrestricted. -/
def ScanCall (data : ScanLayout) (heap : Heap) (index count : Int) (final : Heap) : Prop :=
  ∀ state, ScanLocals data index count state → state.heap = heap →
    kruskal_sorted.CallFrom state final data.chosen



/-- Two representative lookups precede the conditional selection and union.
    The union result is intentionally ignored, as in textbook MST-KRUSKAL. -/
def EdgeCalls (data : ScanLayout) (heap final : Heap) (edge a b : Int) : Prop :=
  ∃ first second left right,
    Algo.union_find.UnionFind.find.Call (heap.tick "kruskal") (data.sets.object, a) first left ∧
    Algo.union_find.UnionFind.find.Call first (data.sets.object, b) second right ∧
    (if left ≠ right then ∃ result,
      Algo.union_find.UnionFind.union.Call (second.write data.chosen edge 1)
        (data.sets.object, a, b) final result else final = second) ∧
    data.chosen < second.nextRef















/-- The empty edge set is allocated before initializing singleton components. -/
def initialHeap (heap : Heap) (size : Nat) : Heap :=
  newHeap (heap.allocate (fun _ => 0)) size

/-- Fresh result and disjoint-set arrays accompany the supplied edge order. -/
def initialLayout (heap : Heap) (_size : Nat) (sources targets order : SeqRef) : ScanLayout :=
  ⟨newLayout (heap.allocate (fun _ => 0)), sources, targets, order, heap.nextRef⟩











end KruskalAnalysis
Source
https://github.com/lunjiah/algo2lean/blob/9755b41d188977ae1aafdaf9eccdac0b0edb0420/examples/kruskal/analysis/kruskal_scan.lean

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