Paper
Temporal graphs, temporal settings, traversal times, reachability, and optimal temporal paths
3 pages · 22 marked passages · pdflatex · download PDF · lax-330177
-
Three representations of temporal graphs
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.
1 import Mathlib 2 … module docstring, 13 lines 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 -
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.
1 import Lax330177.Representations 2 … module docstring, 9 lines 12 namespace Lax330177.SnapshotsLabels 13 14 open Lax330177.Representations 15 16 axiom snapshots_labels {n} (G : Graph n) : (toLabels G).toSnapshots = G 17 end Lax330177.SnapshotsLabels 18 -
no assumptions
Fix a time and an ordered pair of vertices. The label set of that pair contains the time exactly when the original snapshot contains the arc. Reconstructing the snapshot tests this same membership, so it recovers every arc at every time. The lifetime is copied as well, even when the final snapshot is empty.
-
Temporal graph settings
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.
1 import Mathlib 2 import Lax330177.Representations 3 … module docstring, 7 lines 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 -
Paths, walks and reachability
Walks may revisit vertices. Paths have injective vertex sequences. Departure times increase strictly or weakly according to the traversal mode.
- Walks and paths have the same reachability. In either traversal mode, a temporal walk from u to v exists exactly when a temporal path from u to v exists.
- Strict paths give nonstrict reachability. If u can reach v by a strict temporal path, then u can also reach v by a nonstrict temporal path in the same graph.
- Departure times on a proper graph. On a proper directed or undirected graph, every nonstrict temporal path already has strictly increasing departure times.
- Reachability on a proper graph. On a proper directed or undirected graph, u reaches v strictly exactly when u reaches v nonstrictly.
- Replacing undirected edges by opposite arcs. Replacing each undirected edge occurrence by both directed orientations preserves exactly the same timed paths of every length in the chosen traversal mode.
- Path supports determine reachability. If two graphs on the same vertices realize exactly the same ordered vertex sequences as temporal paths in their respective modes, then they have the same reachability relation.
- Temporal reachability is reflexive. Every vertex reaches itself in both modes, including at lifetime zero.
- Enlarging the allowed vertex set. A path restricted to C remains feasible in any vertex superset D.
- Allowing all vertices. Restricting the path to the full vertex set recovers ordinary temporal reachability.
- Paths are static-edge trails. A vertex-simple path never uses a footprint edge twice, even counting reverse traversals as the same undirected edge.
- Static-edge trails are temporal-edge trails. A walk that never repeats a static edge never repeats an edge-time occurrence.
- Strict walks are temporal-edge trails. A strict walk never repeats an edge-time occurrence.
- Properness of symmetric snapshots. On symmetric snapshots, directed properness is equivalent to undirected properness.
1 import Mathlib 2 import Lax330177.Representations 3 import Lax330177.Settings 4 … module docstring, 21 lines 26 namespace Lax330177.Paths 27 open Lax330177.Representations 28 open Lax330177.Settings 29 noncomputable section 30 attribute [local instance] Classical.propDecidable 31 structure Walk {n : ℕ} (G : Graph n) (mode : TraversalMode) (k : ℕ) where 32 vertex : Fin (k + 1) → Fin n 33 time : Fin k → Fin G.lifetime 34 available : ∀ i, G.edge (time i) (vertex i.castSucc) (vertex i.succ) 35 ordered : ∀ i j, i < j → TimeLE mode (time i).val (time j).val 36 37 namespace Walk 38 variable {n k : ℕ} {G : Graph n} {mode : TraversalMode} 39 40 def start (w : Walk G mode k) := w.vertex 0 41 def finish (w : Walk G mode k) := w.vertex (Fin.last k) 42 def support (w : Walk G mode k) := List.ofFn w.vertex 43 def IsPath (w : Walk G mode k) : Prop := Function.Injective w.vertex 44 def IsStaticEdgeTrail (d : Direction) (w : Walk G mode k) : Prop := 45 ∀ i j : Fin k, SameStaticEdge d (w.vertex i.castSucc) (w.vertex i.succ) 46 (w.vertex j.castSucc) (w.vertex j.succ) → i = j 47 def IsTemporalEdgeTrail (d : Direction) (w : Walk G mode k) : Prop := 48 ∀ i j : Fin k, SameStaticEdge d (w.vertex i.castSucc) (w.vertex i.succ) 49 (w.vertex j.castSucc) (w.vertex j.succ) → w.time i = w.time j → i = j 50 51 def StaysIn (w : Walk G mode k) (C : Finset (Fin n)) : Prop := ∀ i, w.vertex i ∈ C 52 def InWindow (w : Walk G mode k) (a b : ℕ) : Prop := 53 ∀ i, a ≤ (w.time i).val ∧ (w.time i).val < b 54 def IsClosed (w : Walk G mode k) : Prop := w.start = w.finish 55 def IsCircuit (d : Direction) (w : Walk G mode k) : Prop := 56 0 < k ∧ w.IsClosed ∧ w.IsStaticEdgeTrail d 57 /-- Positive closed walk without repeated vertices except the final return. 58 Undirected cycles also have at least three edges, directed cycles at least two. -/ 59 def IsCycle (d : Direction) (w : Walk G mode k) : Prop := 60 (match d with | .directed => 2 ≤ k | .undirected => 3 ≤ k) ∧ 61 w.IsClosed ∧ Function.Injective (fun i : Fin k => w.vertex i.castSucc) 62 63 def nil (G : Graph n) (mode : TraversalMode) (v : Fin n) : Walk G mode 0 where 64 vertex _ := v 65 time := Fin.elim0 66 available := by intro i; exact Fin.elim0 i 67 ordered := by intro i; exact Fin.elim0 i 68 69 70 def forgetStrict (w : Walk G .strict k) : Walk G .nonstrict k where 71 vertex := w.vertex 72 time := w.time 73 available := w.available 74 ordered := by intro i j h; exact Nat.le_of_lt (w.ordered i j h) 75 76 77 78 79 80 81 82 /-- A contiguous segment, including its two endpoints. -/ 83 def segment (w : Walk G mode k) (a len : ℕ) (h : a + len ≤ k) : 84 Walk G mode len where 85 vertex i := w.vertex ⟨a + i.val, by omega⟩ 86 time i := w.time ⟨a + i.val, by omega⟩ 87 available i := w.available ⟨a + i.val, by omega⟩ 88 ordered := by intro i j hij; apply w.ordered; change a + i.val < a + j.val; omega 89 90 def take (w : Walk G mode k) (len : ℕ) (h : len ≤ k) := w.segment 0 len (by omega) 91 def suffix (w : Walk G mode k) (a : ℕ) (h : a ≤ k) := 92 w.segment a (k - a) (by omega) 93 94 /-- Boundary condition for concatenation; empty operands impose no time constraint. -/ 95 def CanAppend {l : ℕ} (w : Walk G mode k) (z : Walk G mode l) : Prop := 96 w.finish = z.start ∧ ∀ i j, TimeLE mode (w.time i).val (z.time j).val 97 98 end Walk 99 100 def Reaches {n : ℕ} (G : Graph n) (mode : TraversalMode) (u v : Fin n) : Prop := 101 ∃ k, ∃ w : Walk G mode k, w.IsPath ∧ w.start = u ∧ w.finish = v 102 def WalkReaches {n : ℕ} (G : Graph n) (mode : TraversalMode) (u v : Fin n) : Prop := 103 ∃ k, ∃ w : Walk G mode k, w.start = u ∧ w.finish = v 104 def ReachesIn {n : ℕ} (G : Graph n) (mode : TraversalMode) 105 (C : Finset (Fin n)) (u v : Fin n) : Prop := 106 ∃ k, ∃ w : Walk G mode k, w.IsPath ∧ w.StaysIn C ∧ w.start = u ∧ w.finish = v 107 def ReachesDuring {n : ℕ} (G : Graph n) (mode : TraversalMode) 108 (a b : ℕ) (u v : Fin n) : Prop := 109 ∃ k, ∃ w : Walk G mode k, w.IsPath ∧ w.InWindow a b ∧ w.start = u ∧ w.finish = v 110 111 112 113 114 115 116 117 abbrev TemporalPath {n} (G : Graph n) (m : TraversalMode) (k : ℕ) := {w : Walk G m k // w.IsPath} 118 abbrev StrictPath {n} (G : Graph n) := TemporalPath G .strict 119 abbrev NonstrictPath {n} (G : Graph n) := TemporalPath G .nonstrict 120 abbrev StrictReachability {n} (G : Graph n) := Reaches G .strict 121 abbrev NonstrictReachability {n} (G : Graph n) := Reaches G .nonstrict 122 123 def graphReaches {n s} (G : InterpretedGraph n s) := Reaches G.graph s.mode 124 125 126 127 def bidirect {n} {s : Setting} (G : InterpretedGraph n s) : 128 InterpretedGraph n { s with direction := .directed } where 129 graph := G.graph 130 admitted := ⟨trivial, G.admitted.2.1, fun h => ⟨trivial, (G.admitted.2.2 h).2⟩⟩ 131 132 133 134 135 def Realizes {n k} (G : Graph n) (m : TraversalMode) (x : Fin (k+1) → Fin n) := 136 ∃ w : TemporalPath G m k, w.val.vertex = x 137 138 def SupportEquivalent {n} (G H : Graph n) (m l : TraversalMode) := 139 ∀ k (x : Fin (k+1) → Fin n), Realizes G m x ↔ Realizes H l x 140 141 142 end 143 end Lax330177.Paths 144 -
The temporal reachability graph
Fix a traversal mode. The reachability graph is the static directed graph on the original vertex set with an arc from u to v exactly when u and v are distinct and a temporal path in that mode goes from u to v. Each arc records a whole journey. Even undirected temporal graphs can have asymmetric reachability. The zero-edge path witnesses reflexivity of the relation, while the graph omits diagonal arcs.
1 import Lax330177.Paths 2 import Mathlib.Combinatorics.Digraph.Basic 3 … module docstring, 14 lines 18 namespace Lax330177.ReachabilityGraph 19 open Lax330177.Representations Lax330177.Paths Lax330177.Settings 20 21 def reachabilityGraph {n : ℕ} (G : Graph n) (mode : TraversalMode) : Digraph (Fin n) where 22 Adj u v := u ≠ v ∧ Reaches G mode u v 23 24 def ofSetting {n : ℕ} {s : Setting} (G : InterpretedGraph n s) : Digraph (Fin n) := 25 reachabilityGraph G.graph s.mode 26 27 end Lax330177.ReachabilityGraph 28 -
Departure times on a proper graph
On a proper directed or undirected graph, every nonstrict temporal path already has strictly increasing departure times.
1 import Lax330177.Paths 2 … module docstring, 9 lines 12 namespace Lax330177.ProperPathTimes 13 open Lax330177.Representations 14 open Lax330177.Settings 15 open Lax330177.Paths 16 17 axiom proper_path_times {n k} (G : Graph n) (d : Direction) (hg : IsProper d G) (w : TemporalPath G .nonstrict k) : StrictMono w.val.time 18 end Lax330177.ProperPathTimes 19 -
no assumptions
Consecutive steps have the form u → v → w with u and w distinct because the path never repeats a vertex. Properness forbids equal departure times for these two steps. Since the times are already weakly increasing, each is strictly smaller than its successor.
-
Reachability on a proper graph
On a proper directed or undirected graph, u reaches v strictly exactly when u reaches v nonstrictly.
1 import Lax330177.Paths 2 … module docstring, 9 lines 12 namespace Lax330177.ProperModes 13 open Lax330177.Representations 14 open Lax330177.Settings 15 open Lax330177.Paths 16 17 axiom proper_modes {n} (G : Graph n) (d : Direction) (h : IsProper d G) (u v) : Reaches G .strict u v ↔ Reaches G .nonstrict u v 18 end Lax330177.ProperModes 19 -
A strict path also satisfies the nonstrict timing rule. For the converse, take a nonstrict path. Consecutive edges form a two-step path with distinct outer vertices. Properness prevents both steps from using the same time. Their weakly increasing times must therefore increase strictly, giving a strict path with the same endpoints.
-
A proper graph can have a walk with equal departure times
On a proper undirected graph, a nonstrict walk can traverse one edge and immediately traverse it back at the same time.
1 import Lax330177.Examples 2 … module docstring, 9 lines 12 namespace Lax330177.BounceSameTime 13 open Lax330177.Representations 14 open Lax330177.Settings 15 open Lax330177.Paths 16 open Lax330177.Examples 17 18 axiom bounce_same_time : IsProper .undirected repeatedEdge ∧ ¬ StrictMono simultaneousBounce.time 19 end Lax330177.BounceSameTime 20 -
no assumptions
Use a graph on two vertices with one undirected edge. It is proper because there is no second edge incident to either endpoint. A walk can cross that edge and immediately cross it back at the same timestamp. Its two equal departure times satisfy the nonstrict rule and violate the strict rule.
-
Traversal times
Each occurrence has a natural traversal time. The next departure may occur at arrival. The lifetime bounds departure times and the final arrival may fall outside it.
- Feasible departure times. For integer timestamps, a departure sequence is feasible with traversal time zero exactly when it is weakly increasing. With traversal time one, it is feasible exactly when it is strictly increasing.
- The same timed paths. Fix the vertex sequence and every departure time. They form a path with uniform traversal time zero exactly when they form a nonstrict temporal path, and with uniform time one exactly when they form a strict temporal path.
- The same reachable pairs. For every pair of vertices, reachability with uniform traversal time zero is equivalent to nonstrict reachability, and reachability with uniform time one is equivalent to strict reachability.
1 import Mathlib 2 import Lax330177.Representations 3 import Lax330177.Paths 4 … module docstring, 11 lines 16 namespace Lax330177.Durations 17 open Lax330177.Representations 18 open Lax330177.Paths 19 noncomputable section 20 attribute [local instance] Classical.propDecidable 21 22 def Feasible {k : ℕ} (time duration : Fin k → ℕ) : Prop := 23 ∀ i j, i < j → time i + duration i ≤ time j 24 25 def DurationPath {n k} (G : Graph n) (δ : Fin G.lifetime → Fin n → Fin n → ℕ) 26 (x : Fin (k+1) → Fin n) (t : Fin k → Fin G.lifetime) : Prop := 27 Function.Injective x ∧ (∀ i, G.edge (t i) (x i.castSucc) (x i.succ)) ∧ 28 Feasible (fun i => (t i).val) (fun i => δ (t i) (x i.castSucc) (x i.succ)) 29 30 31 def DurationReaches {n} (G : Graph n) (δ : Fin G.lifetime → Fin n → Fin n → ℕ) 32 (u v : Fin n) : Prop := 33 ∃ k, ∃ x : Fin (k+1) → Fin n, ∃ t : Fin k → Fin G.lifetime, 34 DurationPath G δ x t ∧ x 0 = u ∧ x (Fin.last k) = v 35 36 37 38 end 39 end Lax330177.Durations 40 -
The same timed paths
Fix the vertex sequence and every departure time. They form a path with uniform traversal time zero exactly when they form a nonstrict temporal path, and with uniform time one exactly when they form a strict temporal path.
1 import Lax330177.Durations 2 … module docstring, 9 lines 12 namespace Lax330177.UniformPaths 13 open Lax330177.Representations 14 open Lax330177.Paths 15 open Lax330177.Durations 16 17 axiom uniform_paths {n k} (G : Graph n) (m : TraversalMode) (x : Fin (k+1) → Fin n) (t : Fin k → Fin G.lifetime) : DurationPath G (fun _ _ _ => if m = .strict then 1 else 0) x t ↔ ∃ w : TemporalPath G m k, w.val.vertex = x ∧ w.val.time = t 18 end Lax330177.UniformPaths 19 -
no assumptions
Fix the vertex sequence and its departure times. Both path definitions require distinct vertices and an available edge at every departure. For uniform time zero, arrival before or at the next departure means that departure times are weakly increasing. For uniform time one, it means that the integer times are strictly increasing. Thus the same sequences satisfy either description exactly in the stated mode.
-
Optimal temporal paths
Fix two vertices, traversal times, a release time and an inclusive arrival deadline. A shortest path minimizes traversals. A fastest path minimizes elapsed time from first departure to final arrival. Foremost paths minimize arrival, and latest departure paths maximize departure. Minimum waiting paths minimize the sum of idle gaps at internal vertices. Initial waiting and time after arrival do not contribute. A zero-edge path occupies its vertex at any one instant in the window. Every feasible query admits an optimizer for each of the five criteria.
- Each objective attains its optimum. Fix the endpoints, traversal times, release time and arrival deadline. If at least one feasible path exists, then each of the five criteria has an optimal path. The optimizing path may depend on the criterion.
1 import Lax330177.Durations 2 import Mathlib.Order.Filter.Extr 3 import Mathlib.Algebra.BigOperators.Group.Finset.Basic 4 … module docstring, 15 lines 20 namespace Lax330177.OptimalPaths 21 open Lax330177.Representations Lax330177.Durations 22 23 structure Query {n : ℕ} (G : Graph n) where 24 source : Fin n 25 target : Fin n 26 release : ℕ 27 deadline : ℕ 28 transit : Fin G.lifetime → Fin n → Fin n → ℕ 29 30 variable {n : ℕ} {G : Graph n} (q : Query G) 31 32 structure Candidate where 33 hops : ℕ 34 vertex : Fin (hops+1) → Fin n 35 time : Fin hops → Fin G.lifetime 36 feasible : DurationPath G q.transit vertex time 37 starts : vertex 0 = q.source 38 ends : vertex (Fin.last hops) = q.target 39 departure : ℕ 40 arrival : ℕ 41 released : q.release ≤ departure 42 inOrder : departure ≤ arrival 43 onTime : arrival ≤ q.deadline 44 first : ∀ h : 0 < hops, departure = (time ⟨0,h⟩).val 45 last : ∀ h : 0 < hops, 46 let i : Fin hops := ⟨hops-1, by omega⟩ 47 arrival = (time i).val + q.transit (time i) (vertex i.castSucc) (vertex i.succ) 48 instantaneous : hops = 0 → departure = arrival 49 50 variable {q} 51 def Candidate.elapsed (p : Candidate q) := p.arrival - p.departure 52 53 def Candidate.waiting (p : Candidate q) : ℕ := 54 ∑ i : Fin p.hops, if h : i.val + 1 < p.hops then 55 (p.time ⟨i.val+1,h⟩).val - ((p.time i).val + q.transit (p.time i) (p.vertex i.castSucc) (p.vertex i.succ)) 56 else 0 57 58 def Shortest (p : Candidate q) := IsMinOn Candidate.hops Set.univ p 59 def Fastest (p : Candidate q) := IsMinOn Candidate.elapsed Set.univ p 60 def Foremost (p : Candidate q) := IsMinOn Candidate.arrival Set.univ p 61 abbrev EarliestArrival (p : Candidate q) := Foremost p 62 def LatestDeparture (p : Candidate q) := IsMaxOn Candidate.departure Set.univ p 63 def MinimumWaiting (p : Candidate q) := IsMinOn Candidate.waiting Set.univ p 64 65 end Lax330177.OptimalPaths 66 67 -
Elapsed time splits into travel and waiting
If every available traversal takes c time units, every feasible path has elapsed time equal to its total internal waiting time plus c times its number of hops.
1 import Lax330177.UniformCosts 2 … module docstring, 9 lines 12 namespace Lax330177.ElapsedEq 13 open Lax330177.Representations Lax330177.OptimalPaths 14 open Lax330177.UniformCosts 15 variable {n : ℕ} {G : Graph n} {q : Query G} 16 17 axiom elapsed_eq (p : Candidate q) (c : ℕ) (h : Uniform q c) : 18 p.elapsed = p.waiting + p.hops * c 19 end Lax330177.ElapsedEq 20 -
no assumptions
Split the interval from first departure to final arrival into the traversals and the gaps between them. Each traversal contributes c time units. Each gap runs from one arrival to the next departure and contributes exactly the waiting time there. These pieces cover the interval in order, so elapsed time equals total waiting plus c times the hop count. A zero-hop path departs and arrives at the same instant, making both sides zero.
-
Zero traversal time
With uniform traversal time zero, a feasible path is fastest exactly when it minimizes total internal waiting time.
1 import Lax330177.UniformCosts 2 … module docstring, 9 lines 12 namespace Lax330177.ZeroOptima 13 open Lax330177.Representations Lax330177.OptimalPaths 14 open Lax330177.UniformCosts 15 variable {n : ℕ} {G : Graph n} {q : Query G} 16 17 axiom zero_optima (p : Candidate q) (h : Uniform q 0) : Fastest p ↔ MinimumWaiting p 18 end Lax330177.ZeroOptima 19 -
Set c to zero in the elapsed-time identity. Every path then has elapsed time equal to its own waiting time. Consequently two feasible paths compare in exactly the same order under the two criteria, including ties, and their sets of minimizers coincide.
-
A detour with no waiting
On the three-vertex chain and its shortcut triangle, each traversal takes c units, where c is zero or one. In the triangle, the two-hop path departing at 0 and c minimizes waiting for either traversal cost and uses more hops than the shortcut. It is fastest exactly when c is zero.
1 import Lax330177.CostExamples 2 … module docstring, 9 lines 12 namespace Lax330177.NoWaitDetour 13 open Lax330177.Representations Lax330177.Durations Lax330177.OptimalPaths 14 open Lax330177.CostExamples 15 16 axiom no_wait_detour (c : Fin 2) : MinimumWaiting (via true false c) ∧ 17 ¬ Shortest (via true false c) ∧ (Fastest (via true false c) ↔ c.val = 0) 18 end Lax330177.NoWaitDetour 19 -
no assumptions
Depart on the two arcs at times 0 and c. The second departure is exactly the first arrival, so total waiting is zero, the least possible. The direct arc uses one hop instead of two. With c equal to zero the detour also takes zero elapsed time and is fastest. With c equal to one it takes two units, while the direct arc takes only one.