The temporal reachability graph
Lax330177.ReachabilityGraph · concepts/Lax330177/ReachabilityGraph.lean · lax-330177
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
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.
Concept map
In the paper
- page 1 of this submission's paper
Lean source view on GitHub
| 1 | import Lax330177.Paths |
| 2 | import Mathlib.Combinatorics.Digraph.Basic |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: The temporal reachability graph |
| 7 | type: definition |
| 8 | --- |
| 9 | Fix a traversal mode. The reachability graph is the static directed graph on the |
| 10 | original vertex set with an arc from u to v exactly when u and v are distinct |
| 11 | and a temporal path in that mode goes from u to v. Each arc records a whole |
| 12 | journey. Even undirected temporal graphs can have asymmetric reachability. |
| 13 | The zero-edge path witnesses reflexivity of the relation, while the graph omits |
| 14 | diagonal arcs. |
| 15 | |
| 16 | [Strict and nonstrict reachability graphs on proper graphs.](Lax330177.ProperReachGraphs.html) |
| 17 | -/ |
| 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 |
Builds on
Used by
From Mathlib
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments