BFS: shortest paths and an explicit linear event bound
ProvedCLRS.BFS.correctness_and_explicit_running_timeFor every heap representing the input graph and every valid source, establish one terminating BFS Call with the complete shortest-path, predecessor, fresh-result, and caller-preservation postcondition. For the same call, prove
Here T is the increment of graph_work and m counts adjacency occurrences. The initial clock values are arbitrary. This stronger numerical bound is an open supporting task.
import Definitions.Def_CLRS_BFS_Program set_option autoImplicit false open Algo2LeanGenerated CLRS.GraphTraversal CLRS.BFS
theorem CLRS.BFS.correctness_and_explicit_running_time
(before : Heap) (graph : ObjectRef) (g : Graph) (source : Int)
(represented : GraphRep before graph g) (sourceValid : Vertex g source) :
∃ after result,
Algo.bfs.bfs.Call before (graph, source) after result ∧
Post before after result g source ∧
work before after ≤ 6 * g.size + 2 * edgeCount g + 5 := 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 object reference, mathematical graph consisting of a natural number and a finite neighbor list for each natural-number index whose entries are all below whenever its index is below , and integer source , assume the heap represents that graph at the given object reference and . Representation means that the reference names an allocated graph_input.UnweightedGraph object with size field and fields naming an allocated Seq[Int] adjacency collection and an allocated integer degree sequence; for each , the degree entry is the neighbor-list length, the adjacency entry decodes to an allocated row sequence, and that row's prefix of this length equals the neighbor list in order. The conclusion asserts existence of a final heap and a result-object reference such that the generated BFS function, from this input heap, graph reference, and source, has a finite execution returning that same final heap and result under every suspended caller stack, including completion at the top level. That very final heap contains an allocated bfs.BFSResult object whose reference is at least the initial object-allocation counter and strictly below the final one. Its distance and parent fields name distinct integer sequences whose references are each at least the initial sequence counter and strictly below the final one. Writing and for their final values, the source has and , and every vertex integer in has . Its distance is exactly when there is no directed walk from to ; if its distance is nonnegative, a walk of that natural-number length exists and no shorter walk exists. Walks use neighbor-list membership as directed edges, may repeat vertices, and allow a zero-length walk at any valid vertex. A vertex of distance also has parent . Every nonsource vertex of nonnegative distance has a valid parent vertex with an edge to it and satisfies . The final heap preserves the entire contents of every initially allocated integer sequence, object, and collection; none of the three allocation counters decreases, the graph_work clock does not decrease, and every other named clock stays unchanged. The difference between the final and initial graph_work clocks is at most , where is the sum of the neighbor-list lengths over , counting repeated adjacency occurrences. The bound is on the explicit instrumented ticks of this same execution, measured from arbitrary initial clock values; it does not count a prior construction of the supplied graph or separately charge every transition or integer operation. The premises permit self-loops, parallel arcs, and compatible sharing of adjacency-row storage; they do not constrain unused row entries, graph-list indices outside the vertex range, or unrelated heap contents. The valid-source premise makes the implication vacuous for . The output specification imposes no requirements on output entries outside the vertex range and no exact count of additional allocated objects or sequences. This is an unproved goal: its body is sorry, so the displayed declaration supplies no proof of the asserted existence, correctness, preservation, freshness, or bound.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.