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

The temporal reachability graph

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

    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.

    Strict and nonstrict reachability graphs on proper graphs.

    Concept map
    4 concepts; 1 descendant hidden
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A

    In the paper

    • page 1 of this submission's paper

    Lean source view on GitHub

    1import Lax330177.Paths
    2import Mathlib.Combinatorics.Digraph.Basic
    3
    4/-!
    5---
    6title: The temporal reachability graph
    7type: definition
    8---
    9Fix a traversal mode. The reachability graph is the static directed graph on the
    10original vertex set with an arc from u to v exactly when u and v are distinct
    11and a temporal path in that mode goes from u to v. Each arc records a whole
    12journey. Even undirected temporal graphs can have asymmetric reachability.
    13The zero-edge path witnesses reflexivity of the relation, while the graph omits
    14diagonal arcs.
    15
    16[Strict and nonstrict reachability graphs on proper graphs.](Lax330177.ProperReachGraphs.html)
    17-/
    18namespace Lax330177.ReachabilityGraph
    19open Lax330177.Representations Lax330177.Paths Lax330177.Settings
    20
    21def reachabilityGraph {n : ℕ} (G : Graph n) (mode : TraversalMode) : Digraph (Fin n) where
    22 Adj u v := u ≠ v ∧ Reaches G mode u v
    23
    24def ofSetting {n : ℕ} {s : Setting} (G : InterpretedGraph n s) : Digraph (Fin n) :=
    25 reachabilityGraph G.graph s.mode
    26
    27end Lax330177.ReachabilityGraph
    28

    Discussion

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

    Loading discussion…