Temporal graph settings
Lax330177.Settings · concepts/Lax330177/Settings.lean · lax-330177
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
A setting selects direction, traversal mode and restrictions on the labelling. At a fixed time, two composable arcs u → v and v → w may coexist only when w = u. Opposite arcs may share a time, as may arcs with a common tail or a common head. For symmetric snapshots this is exactly the matching condition. Happy graphs are both simple and proper.
Concept map
In the paper
- page 1 of this submission's paper
Lean source view on GitHub
| 1 | import Mathlib |
| 2 | import Lax330177.Representations |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Temporal graph settings |
| 7 | type: definition |
| 8 | --- |
| 9 | A setting selects direction, traversal mode and restrictions on the labelling. At a fixed time, two composable arcs u → v and v → w may coexist only when w = u. Opposite arcs may share a time, as may arcs with a common tail or a common head. For symmetric snapshots this is exactly the matching condition. Happy graphs are both simple and proper. |
| 10 | -/ |
| 11 | namespace Lax330177.Settings |
| 12 | open Lax330177.Representations |
| 13 | noncomputable section |
| 14 | attribute [local instance] Classical.propDecidable |
| 15 | /-- Identity of the static edge, respecting the selected direction convention. -/ |
| 16 | def SameStaticEdge (d : Direction) {n : ℕ} (u v x y : Fin n) : Prop := |
| 17 | match d with |
| 18 | | .directed => u = x ∧ v = y |
| 19 | | .undirected => (u = x ∧ v = y) ∨ (u = y ∧ v = x) |
| 20 | def IsSimple {n : ℕ} (G : Graph n) : Prop := |
| 21 | ∀ u v t s, G.edge t u v → G.edge s u v → t = s |
| 22 | |
| 23 | def IsProper {n : ℕ} (d : Direction) (G : Graph n) : Prop := |
| 24 | ValidDirection d G ∧ ∀ t u v w, G.edge t u v → G.edge t v w → u = w |
| 25 | |
| 26 | def IsHappy {n : ℕ} (d : Direction) (G : Graph n) : Prop := |
| 27 | IsSimple G ∧ IsProper d G |
| 28 | |
| 29 | def LabelMultiplicityBound {n : ℕ} (G : Graph n) (b : ℕ) : Prop := |
| 30 | ∀ u v, ((toLabels G).labels u v).card ≤ b |
| 31 | |
| 32 | structure Setting where |
| 33 | direction : Direction |
| 34 | mode : TraversalMode |
| 35 | requireSimple : Bool := false |
| 36 | requireProper : Bool := false |
| 37 | |
| 38 | def Setting.Admits {n : ℕ} (s : Setting) (G : Graph n) : Prop := |
| 39 | ValidDirection s.direction G ∧ (s.requireSimple = true → IsSimple G) ∧ |
| 40 | (s.requireProper = true → IsProper s.direction G) |
| 41 | |
| 42 | structure InterpretedGraph (n : ℕ) (s : Setting) where |
| 43 | graph : Graph n |
| 44 | admitted : s.Admits graph |
| 45 | |
| 46 | abbrev StrictTemporalGraph (n : ℕ) (d : Direction) (simple proper : Bool) := |
| 47 | InterpretedGraph n ⟨d, .strict, simple, proper⟩ |
| 48 | abbrev NonstrictTemporalGraph (n : ℕ) (d : Direction) (simple proper : Bool) := |
| 49 | InterpretedGraph n ⟨d, .nonstrict, simple, proper⟩ |
| 50 | |
| 51 | end |
| 52 | end Lax330177.Settings |
| 53 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments