Paths, walks and reachability
Lax330177.Paths · concepts/Lax330177/Paths.lean · lax-330177
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
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.
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 | import Lax330177.Settings |
| 4 | |
| 5 | /-! |
| 6 | --- |
| 7 | title: Paths, walks and reachability |
| 8 | type: definition |
| 9 | --- |
| 10 | Walks may revisit vertices. Paths have injective vertex sequences. Departure times increase strictly or weakly according to the traversal mode. |
| 11 | |
| 12 | - [Walks and paths have the same reachability.](Lax330177Proofs.Basic.walk_path_reach.html) In either traversal mode, a temporal walk from u to v exists exactly when a temporal path from u to v exists. |
| 13 | - [Strict paths give nonstrict reachability.](Lax330177Proofs.Basic.strict_inclusion.html) 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. |
| 14 | - [Departure times on a proper graph.](Lax330177Proofs.Basic.proper_path_times.html) On a proper directed or undirected graph, every nonstrict temporal path already has strictly increasing departure times. |
| 15 | - [Reachability on a proper graph.](Lax330177Proofs.Basic.proper_modes.html) On a proper directed or undirected graph, u reaches v strictly exactly when u reaches v nonstrictly. |
| 16 | - [Replacing undirected edges by opposite arcs.](Lax330177Proofs.Basic.bidirect_paths.html) Replacing each undirected edge occurrence by both directed orientations preserves exactly the same timed paths of every length in the chosen traversal mode. |
| 17 | - [Path supports determine reachability.](Lax330177Proofs.Basic.support_reach.html) 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. |
| 18 | - [Temporal reachability is reflexive.](Lax330177.Reflexivity.html) Every vertex reaches itself in both modes, including at lifetime zero. |
| 19 | - [Enlarging the allowed vertex set.](Lax330177.RestrictedMonotonicity.html) A path restricted to C remains feasible in any vertex superset D. |
| 20 | - [Allowing all vertices.](Lax330177.UnrestrictedVertices.html) Restricting the path to the full vertex set recovers ordinary temporal reachability. |
| 21 | - [Paths are static-edge trails.](Lax330177.PathTrail.html) A vertex-simple path never uses a footprint edge twice, even counting reverse traversals as the same undirected edge. |
| 22 | - [Static-edge trails are temporal-edge trails.](Lax330177.TrailInclusion.html) A walk that never repeats a static edge never repeats an edge-time occurrence. |
| 23 | - [Strict walks are temporal-edge trails.](Lax330177.StrictWalkTrail.html) A strict walk never repeats an edge-time occurrence. |
| 24 | - [Properness of symmetric snapshots.](Lax330177.SymmetricProper.html) On symmetric snapshots, directed properness is equivalent to undirected properness. |
| 25 | -/ |
| 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 |
Used by
Lax330177.BidirectPathsLax330177.DurationsLax330177.ExamplesLax330177.PathTrailLax330177.ProperModesLax330177.ProperPathTimesLax330177.ReachabilityGraphLax330177.ReflexivityLax330177.RestrictedMonotonicityLax330177.StrictInclusionLax330177.StrictWalkTrailLax330177.SupportReachLax330177.SymmetricProperLax330177.TrailInclusionLax330177.UnrestrictedVerticesLax330177.WalkPathReach
From Mathlib
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments