While this submission is a draft, it cannot be used by other submissions.

Temporal graph settings

Lax330177.Settings · concepts/Lax330177/Settings.lean · lax-330177

definition

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural 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
    2 concepts
    100%
    DefinitionThis conceptRelated conceptA → B: B builds on ADescendants are omitted for concepts with more than 10 descendants.

    In the paper

    • page 1 of this submission's paper

    Lean source view on GitHub

    1import Mathlib
    2import Lax330177.Representations
    3
    4/-!
    5---
    6title: Temporal graph settings
    7type: definition
    8---
    9A 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-/
    11namespace Lax330177.Settings
    12open Lax330177.Representations
    13noncomputable section
    14attribute [local instance] Classical.propDecidable
    15/-- Identity of the static edge, respecting the selected direction convention. -/
    16def 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)
    20def IsSimple {n : ℕ} (G : Graph n) : Prop :=
    21 ∀ u v t s, G.edge t u v → G.edge s u v → t = s
    22
    23def 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
    26def IsHappy {n : ℕ} (d : Direction) (G : Graph n) : Prop :=
    27 IsSimple G ∧ IsProper d G
    28
    29def LabelMultiplicityBound {n : ℕ} (G : Graph n) (b : ℕ) : Prop :=
    30 ∀ u v, ((toLabels G).labels u v).card ≤ b
    31
    32structure Setting where
    33 direction : Direction
    34 mode : TraversalMode
    35 requireSimple : Bool := false
    36 requireProper : Bool := false
    37
    38def 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
    42structure InterpretedGraph (n : ℕ) (s : Setting) where
    43 graph : Graph n
    44 admitted : s.Admits graph
    45
    46abbrev StrictTemporalGraph (n : ℕ) (d : Direction) (simple proper : Bool) :=
    47 InterpretedGraph n ⟨d, .strict, simple, proper⟩
    48abbrev NonstrictTemporalGraph (n : ℕ) (d : Direction) (simple proper : Bool) :=
    49 InterpretedGraph n ⟨d, .nonstrict, simple, proper⟩
    50
    51end
    52end Lax330177.Settings
    53

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…