Graph transpose: correctness and uniform linear running time
ProvedCLRS.SCC.transpose_correctness_and_running_timeFor every represented graph, establish a terminating transpose Call returning a fresh graph object that represents the reversed adjacency occurrences with their multiplicities. Vertex count and total occurrence count are unchanged, and initial caller storage is preserved. One positive constant, uniform over graphs, heaps, and clocks, must bound the same call’s work by
The empty graph is included. This reusable construction theorem is open.
import Definitions.Def_CLRS_SCC_Program set_option autoImplicit false open Algo2LeanGenerated CLRS.GraphTraversal CLRS.SCC
theorem CLRS.SCC.transpose_correctness_and_running_time :
∃ C : Nat, 0 < C ∧
∀ (before : Heap) (graph : ObjectRef) (g : Graph),
GraphRep before graph g →
∃ after result,
Algo.scc.transpose.Call before graph after result ∧
TransposePost 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 transpose 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 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. 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 assertion includes : input and output still require represented graph objects, valid allocated outer collections, and allocated degree arrays; the returned object is fresh, the reversed graph has zero vertices and zero counted adjacency occurrences, and vertex-indexed row and multiplicity clauses are vacuous. Rows at other natural-number indices and contents outside represented prefixes are unrestricted. 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.