SCC: correctness and uniform linear running time
ProvedCLRS.SCC.scc_correctness_and_running_timeThere is one positive natural constant C, uniform over all graph data, input heaps, and initial counters, such that the displayed SCC program terminates and returns a fresh exact partition into strongly connected components with preserved caller storage and
Equal labels are equivalent to mutual reachability in the original graph; labels are contiguous and all used, but their numeric values are not canonical. Empty and disconnected graphs, parallel arcs, and self-loops are included. The bound covers both DFS passes and graph preparation. This is an open task; no correctness or runtime proof is supplied.
import Definitions.Def_CLRS_SCC_Program set_option autoImplicit false open Algo2LeanGenerated CLRS.GraphTraversal CLRS.SCC
theorem CLRS.SCC.scc_correctness_and_running_time :
∃ C : Nat, 0 < C ∧
∀ (before : Heap) (graph : ObjectRef) (g : Graph),
GraphRep before graph g →
∃ after result,
Algo.scc.scc.Call before graph after result ∧
Post before after result g ∧
work before after ≤ C * (1 + g.size + edgeCount g) := by
sorry
Read-back
What the Lean code literally says, in plain math · GPT-6 (Codex, independent fresh-context agent)
There exists one positive natural-number constant , chosen before and independently of every initial heap, graph object reference, graph, size, adjacency list, and initial clock, with the following property. 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 . 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.