Three representations of temporal graphs
Lax330177.Representations · concepts/Lax330177/Representations.lean · lax-330177
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural 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
In the paper
- page 1 of this submission's paper
Lean source view on GitHub
| 1 | import Mathlib |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Three representations of temporal graphs |
| 6 | type: definition |
| 7 | --- |
| 8 | A 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 | -/ |
| 16 | namespace Lax330177.Representations |
| 17 | noncomputable section |
| 18 | attribute [local instance] Classical.propDecidable |
| 19 | /-- A finite temporal graph with exactly `n` vertices. -/ |
| 20 | structure 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. -/ |
| 26 | def IsUndirected {n : ℕ} (G : Graph n) : Prop := |
| 27 | ∀ t u v, G.edge t u v ↔ G.edge t v u |
| 28 | |
| 29 | |
| 30 | inductive Direction where |
| 31 | | directed | undirected |
| 32 | deriving DecidableEq |
| 33 | |
| 34 | inductive TraversalMode where |
| 35 | | strict | nonstrict |
| 36 | deriving DecidableEq |
| 37 | |
| 38 | def TimeLE (mode : TraversalMode) (a b : ℕ) : Prop := |
| 39 | match mode with |
| 40 | | .strict => a < b |
| 41 | | .nonstrict => a ≤ b |
| 42 | |
| 43 | def ValidDirection {n : ℕ} (d : Direction) (G : Graph n) : Prop := |
| 44 | match d with |
| 45 | | .directed => True |
| 46 | | .undirected => IsUndirected G |
| 47 | |
| 48 | def 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. -/ |
| 51 | structure 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 | |
| 58 | def 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 | |
| 65 | def 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 | |
| 75 | structure 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 | |
| 81 | def 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 | |
| 88 | def 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 | |
| 91 | def 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 | |
| 107 | end |
| 108 | end Lax330177.Representations |
| 109 | |
| 110 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments