SCC: exact component partition and an explicit event bound
ProvedCLRS.SCC.scc_correctness_and_explicit_running_timeFor every represented graph, establish a terminating call to the displayed two-pass SCC program. Its fresh labels must agree exactly for mutually reachable vertices, range over 0,…,k−1 with every label used, satisfy k≤n and k=0 exactly when n=0, and preserve caller storage. For the same call, prove
including both DFS passes, transposition, and linear reversal of finish order. The result is an open theorem with no assumed-correct DFS hypothesis.
import Definitions.Def_CLRS_SCC_Program set_option autoImplicit false open Algo2LeanGenerated CLRS.GraphTraversal CLRS.SCC
theorem CLRS.SCC.scc_correctness_and_explicit_running_time
(before : Heap) (graph : ObjectRef) (g : Graph)
(represented : GraphRep before graph g) :
∃ after result,
Algo.scc.scc.Call before graph after result ∧
Post before after result g ∧
work before after ≤ 20 + 21 * g.size + 6 * edgeCount g := by
sorry
Read-back
What the Lean code literally says, in plain math · GPT-6 (Codex, independent fresh-context agent)
For every initial heap , object reference , and finite directed multigraph , under exactly the representation hypothesis described below, the following conclusion holds; there is no additional graph, heap, or typeclass hypothesis. 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. For every such represented input there exist a final heap and result reference for a completed call of scc on , satisfying all the following requirements together. A completed call means that, for every suspended caller stack, some finite sequence of the specified program transitions takes the entry frame with heap to the return configuration with the same chosen final heap and result reference ; for an empty stack this is a completed top-level return. Thus the final heap and result can depend on the input but are chosen uniformly over caller stacks; the transcript may depend on the stack. This is existence of these completed executions, not a separately stated universal property of all possible runs. 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. The work of this same call is at most , with these fixed coefficients applying uniformly to all represented inputs. 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. The empty graph is included: the input still needs its allocated graph object, valid outer collection, and allocated degree array, while the output still needs a fresh result object and fresh component array, with component count zero and vacuous vertex-label conditions. The supplied declaration ends in sorry; this is the proposition of an open proof goal, not a proved algorithm-correctness result.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.