AFTD Auto-Formalizing Theoretical Domains

directedDistENN

def

The shortest path distance directedDistENN G ℓ u v from vertex u to vertex v in a directed multigraph G with edge lengths ℓ : E → ENNReal, defined as the infimum of walkLengthENN ℓ p over all directed walks p from u to v.

Statement

noncomputable def directedDistENN {V E : Type*} (G : DirectedMultigraph V E) (ℓ : E → ENNReal) (u v : V) : ENNReal
Defined in
arXiv:2611.12330 Section 2
Verified
13 Nov 2026
Axioms
none listed
Built on 3
  • DirectedMultigraphA directed multigraph parameterized by vertex type V and edge type E, with source and target maps src : E → V and tgt : E → V.
  • IsDirectedWalkAn inductive predicate IsDirectedWalk G u w p stating that a list of edges p : List E forms a directed walk from vertex u to vertex w in…
  • walkLengthENNThe length of a walk represented as a list of edges p : List E under edge-length function ℓ : E → ENNReal, defined as (p.map ℓ).sum.
Used by 1
  • SatisfiesC4Real-valued capacities u : E → ℝ and demands d : K → ℝ satisfy condition (C4) on topology (G, H) if for every binary edge-length function…

Read back from the Lean

Given types V and E, a directed multigraph G with vertices in V and edges in E, an edge length function ℓ : E → ENNReal, and vertices u, v : V, directedDistENN G ℓ u v is defined as the infimum (in ENNReal, where the infimum of the empty set is ⊤) of the set of walk lengths walkLengthENN ℓ p over all edge lists p : List E that form a directed walk from u to v in G (IsDirectedWalk G u v p).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- Shortest path distance between two vertices in ENNReal, or top if unreachable. -/
noncomputable def directedDistENN {V E : Type*} (G : DirectedMultigraph V E) (ℓ : E → ENNReal) (u v : V) : ENNReal :=
  sInf { walkLengthENN ℓ p | (p : List E) (_ : IsDirectedWalk G u v p) }
See it in the graphDiscuss this resultChallenge it