Ordered DFS: reusable forest and an explicit linear event bound
ProvedCLRS.DFS.ordered_correctness_and_explicit_running_timeFor any represented finite graph and any allocated sequence whose first n entries permute the vertices, establish a terminating ordered DFS Call with the full forest, timestamp, white-path, root-priority, increasing finish-order, and dense tree-label contract. Its six output arrays and result object must be fresh, and all initial caller storage must be preserved. For the same call, prove
The bound holds for every root permutation, initial heap, and initial clock value, including the empty graph. This explicit open contract can be reused by the identity-order DFS wrapper and a later SCC proof.
import Definitions.Def_CLRS_DFS_Program set_option autoImplicit false open Algo2LeanGenerated CLRS.GraphTraversal CLRS.DFS
theorem CLRS.DFS.ordered_correctness_and_explicit_running_time
(before : Heap) (graph : ObjectRef) (g : Graph) (inputOrder : SeqRef)
(represented : GraphRep before graph g)
(orderAllocated : inputOrder < before.nextRef)
(orderValid : VertexOrder g (before.read inputOrder)) :
∃ (after : Heap) (result : ObjectRef),
Algo.dfs.dfs_ordered.Call before (graph, inputOrder) after result ∧
Post before after result g (before.read inputOrder) ∧
work before after ≤ 4 + 6 * g.size + 2 * 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 , natural-number graph-object reference , graph , and natural-number sequence reference , assume that represents in , that is allocated in , and that has its first entries forming a permutation of . Here a graph consists of a natural number and, for each natural number , a finite ordered list of natural numbers, with every entry of less than whenever ; its vertices are the integers , an edge means that both endpoints are vertices and occurs in , and counts occurrences, including parallel edges and self-loops. No symmetry is required, and rows at indices are unrestricted. The representation hypothesis means that the initial heap contains the allocated graph object with class tag graph_input.UnweightedGraph, integer size field , an allocated collection of type Seq[Int] in its adjacency field, and an allocated integer sequence in its degree field; for each , the degree entry equals , the adjacency collection entry decodes to an allocated integer-sequence reference, and that row's entries equal the corresponding ordered entries of . Integer sequences are total functions ; only the stated prefixes are constrained, and allocated input sequences, including rows and the degree sequence, may share identities. Heap reference identities are natural numbers in separate sequence, object, and collection spaces, and allocation means that the identity is smaller than that space's allocation counter. The declaration asserts the existence of a final heap and object reference satisfying the completed-call relation for dfs_ordered on , the following postcondition with this original sequence , and the bound . The completed-call relation requires that the graph reference is an allocated object of the graph class (and, for ordered traversal, that the order sequence is allocated), and, for every finite stack of suspended caller continuations, the existence of a finite sequence of the program's individual transitions from the entry frame on that stack to the same final heap and tagged result returned to that stack: the empty stack yields a completed top-level configuration, and a nonempty stack applies its first continuation to the result and retains the remaining stack. Thus the assertion supplies a terminating execution for every such stack, with and chosen independently of the stack; it is not merely a conditional assertion about a supplied successful execution. The resulting heap contains an allocated object of class dfs.DFSResult whose identity is at least the initial object-allocation counter, and its six fields color, parent, discover, finish, order, and component point to pairwise distinct allocated integer sequences, each with identity at least the initial sequence-allocation counter. Write their contents as . Every initially allocated sequence retains its contents at every integer index, every initially allocated object and collection retains its entire stored value, all three allocation counters do not decrease, the named heap counter graph_work does not decrease, and all other named heap counters are unchanged. The result's separate integer fields clock and finished equal and , and for every vertex. There is a natural number such that the result's components field equals , and the following conditions hold. Each vertex has or an edge ; ; discovery times are pairwise distinct, finishing times are pairwise distinct, and for every pair of vertices. For every two vertices , either , or , or and , or and . Define to mean that there is a finite sequence of vertices starting at and ending at , possibly of length zero, such that each successive vertex has parent equal to its predecessor; thus every vertex is its own ancestor. For vertices , holds if and only if and , and also if and only if there is a directed graph walk from to , possibly of length zero, all of whose vertices satisfy . With the input-priority sequence denoted by , for every natural with , every natural satisfies . The prefix is a permutation of the vertices and satisfies whenever . Every vertex has , every natural label is attained by a vertex, and holds exactly when there is a vertex with , , and . For roots satisfying , holds if and only if . These labels describe parent trees; no equivalence with strong connectivity is asserted. The postcondition imposes no contents on the six output sequences outside their vertex prefixes and does not specify the exact total amount of new storage. The work measure is the natural-number difference between the final and initial values of the named heap counter graph_work, using subtraction truncated at zero; the preservation condition prevents a decrease here. It counts the explicit unit tick transitions, including those in nested calls, rather than all individual transitions or machine operations; the initial counters are arbitrary and are not reset. The order sequence may alias other input sequences. The case is included: the permutation requirement constrains no entries, must still be allocated, the result has and both integer event counters zero, and . The proof is left as an unproved goal.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.