BFS: correctness and uniform linear running time
ProvedCLRS.BFS.correctness_and_running_timeThere is one positive natural constant C, independent of the graph, source, initial heap, and counters, such that every represented finite graph with a valid source has a terminating BFS call returning exact shortest distances, correct predecessors, fresh outputs, and preserved caller storage, with
The source must be in 0,…,n−1, excluding the empty graph. T counts the displayed graph_work events, not bit complexity or elapsed time. The algorithm proof and this uniform bound remain contributor tasks.
import Definitions.Def_CLRS_BFS_Program set_option autoImplicit false open Algo2LeanGenerated CLRS.GraphTraversal CLRS.BFS
theorem CLRS.BFS.correctness_and_running_time :
∃ C : Nat, 0 < C ∧
∀ (before : Heap) (graph : ObjectRef) (g : Graph) (source : Int),
GraphRep before graph g → Vertex g source →
∃ after result,
Algo.bfs.bfs.Call before (graph, source) after result ∧
Post before after result g source ∧
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 such that the following holds simultaneously for every initial heap, natural-number graph-object reference, mathematical graph consisting of a natural-number size and finite neighbor lists with all neighbors below at indices below , and integer source . If the heap represents this graph at the given reference and , there exist a final heap and result reference for which the generated BFS call from that input completes in finitely many transitions to that same final heap and result under every suspended caller stack, including completion with no caller. Here representation requires an allocated graph_input.UnweightedGraph object with size field , an allocated adjacency collection tagged Seq[Int], and an allocated degree sequence; at each the degree equals the neighbor-list length, the adjacency element decodes to an allocated row sequence, and its prefix of that length equals the neighbor list in order. The resulting object must be allocated with class bfs.BFSResult and have reference at least the old object counter and below the new one. Its distance and parent fields must name two distinct integer sequences with references at least the old sequence counter and below the new one. For their final contents and , one has and ; for every integer vertex with , one has , and holds exactly when no directed walk from to exists. A nonnegative is the length of an existing walk and is no greater than every other walk length between these endpoints. Walks follow neighbor-list edges, may repeat vertices, and include the zero-length walk at each valid vertex. Distance requires parent ; every nonsource vertex of nonnegative distance has a valid parent with an edge to it and obeys . All initially allocated integer-sequence, object, and collection contents must be preserved in full, all three allocation counters and the graph_work clock must be nondecreasing, and all other clocks must remain unchanged. For that same final heap, the final-minus-initial graph_work count is at most , where is the sum of neighbor-list lengths at indices below and includes repeated arcs. The quantifier order makes independent of the input heap, graph reference, graph, source, and initial clock values, while the final heap and result may depend on those inputs; no particular numerical value of is asserted. The count measures explicit program ticks, with no charge for constructing the caller-supplied graph and no separate assertion about elapsed time or arithmetic bit complexity. Self-loops, parallel arcs, arbitrary initial clock values, and compatible sharing of adjacency-row storage are allowed. Output entries outside the vertex range and the exact number of extra allocations are not specified. The source premise excludes every instance with ; unreachable vertices in a nonempty graph still fall within the output requirements. This is an unproved goal with body sorry; no proof of the uniform constant or of the accompanying existence and postconditions is supplied.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.