AFTD Auto-Formalizing Theoretical Domains

DirectedMultigraph

structure

A directed multigraph parameterized by vertex type V and edge type E, with source and target maps src : E → V and tgt : E → V.

Statement

structure DirectedMultigraph (V E : Type*)
Defined in
arXiv:2611.12330 Section 2
Verified
13 Nov 2026
Axioms
none listed
Used by 7
  • HasFeasibleMultiflowAn instance (G, H, u, d) has a feasible multiflow if there exists some flow function f : K → E → ℝ satisfying IsFeasibleMultiflow G H u d f.
  • BelongsToS4A directed multiflow topology (G, H) belongs to S_4 if for every non-negative capacities u : E → ℝ and demands d : K → ℝ, satisfying…
  • SatisfiesC4Real-valued capacities u : E → ℝ and demands d : K → ℝ satisfy condition (C4) on topology (G, H) if for every binary edge-length function…
  • 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…
  • IsFeasibleMultiflowA multicommodity flow function f : K → E → ℝ is feasible for capacities u : E → ℝ and demands d : K → ℝ on topology (G, H) if f is…
  • HasIntegralMultiflowAn instance (G, H, u, d) has an integral multiflow if there exists a feasible multiflow f : K → E → ℝ such that every f i e is a natural…
  • directedDistENNThe shortest path distance directedDistENN G ℓ u v from vertex u to vertex v in a directed multigraph G with edge lengths ℓ : E → ENNReal,…

Read back from the Lean

A structure DirectedMultigraph parameterized by two types V and E, containing two fields: 1. src : E → V, a function mapping each edge in E to its source vertex in V. 2. tgt : E → V, a function mapping each edge in E to its target vertex in V.

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

/-- A directed multigraph with vertex type V and edge type E. -/
structure DirectedMultigraph (V E : Type*) where
  src : E → V
  tgt : E → V
See it in the graphDiscuss this resultChallenge it