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

Paths, walks and reachability

Lax330177.Paths · concepts/Lax330177/Paths.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

    Walks may revisit vertices. Paths have injective vertex sequences. Departure times increase strictly or weakly according to the traversal mode.

    Concept map
    3 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
    3import Lax330177.Settings
    4
    5/-!
    6---
    7title: Paths, walks and reachability
    8type: definition
    9---
    10Walks 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-/
    26namespace Lax330177.Paths
    27open Lax330177.Representations
    28open Lax330177.Settings
    29noncomputable section
    30attribute [local instance] Classical.propDecidable
    31structure 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
    37namespace Walk
    38variable {n k : ℕ} {G : Graph n} {mode : TraversalMode}
    39
    40def start (w : Walk G mode k) := w.vertex 0
    41def finish (w : Walk G mode k) := w.vertex (Fin.last k)
    42def support (w : Walk G mode k) := List.ofFn w.vertex
    43def IsPath (w : Walk G mode k) : Prop := Function.Injective w.vertex
    44def 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
    47def 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
    51def StaysIn (w : Walk G mode k) (C : Finset (Fin n)) : Prop := ∀ i, w.vertex i ∈ C
    52def InWindow (w : Walk G mode k) (a b : ℕ) : Prop :=
    53 ∀ i, a ≤ (w.time i).val ∧ (w.time i).val < b
    54def IsClosed (w : Walk G mode k) : Prop := w.start = w.finish
    55def 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.
    58Undirected cycles also have at least three edges, directed cycles at least two. -/
    59def 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
    63def 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
    70def 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. -/
    83def 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
    90def take (w : Walk G mode k) (len : ℕ) (h : len ≤ k) := w.segment 0 len (by omega)
    91def 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. -/
    95def 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
    98end Walk
    99
    100def 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
    102def 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
    104def 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
    107def 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
    117abbrev TemporalPath {n} (G : Graph n) (m : TraversalMode) (k : ℕ) := {w : Walk G m k // w.IsPath}
    118abbrev StrictPath {n} (G : Graph n) := TemporalPath G .strict
    119abbrev NonstrictPath {n} (G : Graph n) := TemporalPath G .nonstrict
    120abbrev StrictReachability {n} (G : Graph n) := Reaches G .strict
    121abbrev NonstrictReachability {n} (G : Graph n) := Reaches G .nonstrict
    122
    123def graphReaches {n s} (G : InterpretedGraph n s) := Reaches G.graph s.mode
    124
    125
    126
    127def 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
    135def 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
    138def 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
    142end
    143end Lax330177.Paths
    144

    Discussion

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

    Loading discussion…