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

Three representations of temporal graphs

Lax330177.Representations · concepts/Lax330177/Representations.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 finite lifetime includes empty snapshots. Chronological lists enumerate distinct arc occurrences. Ties can be permuted. Undirected edges have both orientations.

    • Snapshots to labels and back. Starting from snapshots, collecting the appearance times of each arc and reconstructing the snapshots recovers the original graph, including its lifetime.
    • Labels to snapshots and back. Starting from a time-labelled footprint, taking its snapshots and collecting the labels again recovers the original footprint, label sets, and lifetime.
    • Events and adjacency. At every time t, the snapshot reconstructed from the chronological event list contains the arc from u to v exactly when the original snapshot at t contains that arc.
    • Recovering an event list. Converting a chronological event list to snapshots and back preserves every event with its multiplicity. Only the order of events at the same time can change.
    • Snapshot adjacency and edge labels. An arc is active at time t exactly when its label set contains t.
    Concept map
    1 concept
    100%
    DefinitionThis conceptDescendants 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
    2
    3/-!
    4---
    5title: Three representations of temporal graphs
    6type: definition
    7---
    8A finite lifetime includes empty snapshots. Chronological lists enumerate distinct arc occurrences. Ties can be permuted. Undirected edges have both orientations.
    9
    10- [Snapshots to labels and back.](Lax330177Proofs.Basic.snapshots_labels.html) Starting from snapshots, collecting the appearance times of each arc and reconstructing the snapshots recovers the original graph, including its lifetime.
    11- [Labels to snapshots and back.](Lax330177Proofs.Basic.labels_snapshots.html) Starting from a time-labelled footprint, taking its snapshots and collecting the labels again recovers the original footprint, label sets, and lifetime.
    12- [Events and adjacency.](Lax330177Proofs.Basic.stream_edges.html) At every time t, the snapshot reconstructed from the chronological event list contains the arc from u to v exactly when the original snapshot at t contains that arc.
    13- [Recovering an event list.](Lax330177Proofs.Basic.stream_roundtrip.html) Converting a chronological event list to snapshots and back preserves every event with its multiplicity. Only the order of events at the same time can change.
    14- [Snapshot adjacency and edge labels.](Lax330177.ActiveLabel.html) An arc is active at time t exactly when its label set contains t.
    15-/
    16namespace Lax330177.Representations
    17noncomputable section
    18attribute [local instance] Classical.propDecidable
    19/-- A finite temporal graph with exactly `n` vertices. -/
    20structure Graph (n : ℕ) where
    21 lifetime : ℕ
    22 edge : Fin lifetime → Fin n → Fin n → Prop
    23 loopless : ∀ t u, ¬ edge t u u
    24
    25/-- Symmetric snapshots represent undirected edges. -/
    26def IsUndirected {n : ℕ} (G : Graph n) : Prop :=
    27 ∀ t u v, G.edge t u v ↔ G.edge t v u
    28
    29
    30inductive Direction where
    31 | directed | undirected
    32 deriving DecidableEq
    33
    34inductive TraversalMode where
    35 | strict | nonstrict
    36 deriving DecidableEq
    37
    38def TimeLE (mode : TraversalMode) (a b : ℕ) : Prop :=
    39 match mode with
    40 | .strict => a < b
    41 | .nonstrict => a ≤ b
    42
    43def ValidDirection {n : ℕ} (d : Direction) (G : Graph n) : Prop :=
    44 match d with
    45 | .directed => True
    46 | .undirected => IsUndirected G
    47
    48def Footprint {n : ℕ} (G : Graph n) (u v : Fin n) : Prop := ∃ t, G.edge t u v
    49
    50/-- Explicit footprint and finite labels, with no unused footprint edges. -/
    51structure LabeledGraph (n : ℕ) where
    52 lifetime : ℕ
    53 footprint : Fin n → Fin n → Prop
    54 labels : Fin n → Fin n → Finset (Fin lifetime)
    55 supported : ∀ u v, footprint u v ↔ (labels u v).Nonempty
    56 loopless : ∀ u, ¬ footprint u u
    57
    58def toLabels {n : ℕ} (G : Graph n) : LabeledGraph n where
    59 lifetime := G.lifetime
    60 footprint := Footprint G
    61 labels u v := Finset.univ.filter (fun t => G.edge t u v)
    62 supported := by intro u v; simp [Footprint, Finset.Nonempty]
    63 loopless := by intro u ⟨t, h⟩; exact G.loopless t u h
    64
    65def LabeledGraph.toSnapshots {n : ℕ} (G : LabeledGraph n) : Graph n where
    66 lifetime := G.lifetime
    67 edge t u v := t ∈ G.labels u v
    68 loopless := by
    69 intro t u h
    70 exact G.loopless u ((G.supported u u).mpr ⟨t, h⟩)
    71
    72
    73
    74
    75structure EventStream (n h : ℕ) where
    76 events : List (Fin h × Fin n × Fin n)
    77 chronological : events.Pairwise (fun a b => a.1 ≤ b.1)
    78 unique : events.Nodup
    79 loopless : ∀ e ∈ events, e.2.1 ≠ e.2.2
    80
    81def EventStream.snapshots {n h} (s : EventStream n h) : Graph n where
    82 lifetime := h
    83 edge t u v := (t,u,v) ∈ s.events
    84 loopless := by intro t u he; exact s.loopless _ he rfl
    85
    86
    87
    88def occurrences {n} (G : Graph n) :=
    89 Finset.univ.filter (fun e : Fin G.lifetime × Fin n × Fin n => G.edge e.1 e.2.1 e.2.2)
    90
    91def streamOf {n} (G : Graph n) : EventStream n G.lifetime := by
    92 let xs := (occurrences G).toList
    93 let cmp (a b : Fin G.lifetime × Fin n × Fin n) := decide (a.1 ≤ b.1)
    94 refine ⟨xs.mergeSort cmp, ?_, ?_, ?_⟩
    95 · have h := List.pairwise_mergeSort (le := cmp)
    96 (by simpa [cmp] using (fun a b c => @le_trans _ _ a.1 b.1 c.1 : ∀ a b c : Fin G.lifetime × Fin n × Fin n, _))
    97 (by intro a b; simpa [cmp] using le_total a.1 b.1) xs
    98 simpa [cmp] using h
    99 · exact (List.mergeSort_perm xs cmp).nodup_iff.mpr (Finset.nodup_toList _)
    100 · rintro ⟨t,u,v⟩ he huv
    101 change u = v at huv
    102 subst v
    103 exact G.loopless t u (by simpa [xs, occurrences] using he)
    104
    105
    106
    107end
    108end Lax330177.Representations
    109
    110

    Discussion

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

    Loading discussion…