Lax Lean Archive

Bounded reachability

Lax733996.Reachability · concepts/Lax733996/Reachability.lean · lax-733996

definition

Loading review…

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

    A directed graph on NN vertices is given by its Boolean adjacency matrix. A walk may repeat vertices. The recursive reachability test divides the length bound in two and enumerates possible middle vertices.

    Concept map
    1 concept; 11 descendants 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 Mathlib.Data.List.FinRange
    2import Mathlib.Logic.Relation
    3
    4set_option backward.isDefEq.respectTransparency false
    5
    6/-!
    7---
    8title: Bounded reachability
    9type: definition
    10---
    11A directed graph on NN vertices is given by its Boolean adjacency matrix.
    12A walk may repeat vertices. The recursive reachability test divides the
    13length bound in two and enumerates possible middle vertices.
    14-/
    15
    16namespace Lax733996.Reachability
    17
    18abbrev Graph (N : ℕ) := Fin N → Fin N → Bool
    19
    20inductive Walk {α : Type} (R : α → α → Prop) : ℕ → α → α → Prop
    21 | nil (a : α) : Walk R 0 a a
    22 | tail {n : ℕ} {a b c : α} : Walk R n a b → R b c → Walk R (n + 1) a c
    23
    24def Within {α : Type} (R : α → α → Prop) (n : ℕ) (a b : α) : Prop :=
    25 ∃ k ≤ n, Walk R k a b
    26
    27def Reachable {N : ℕ} (G : Graph N) (a b : Fin N) : Prop :=
    28 Relation.ReflTransGen (fun u v => G u v = true) a b
    29
    30def search {N : ℕ} (G : Graph N) : ℕ → Fin N → Fin N → Bool
    31 | 0, a, b => decide (a = b) || G a b
    32 | k + 1, a, b => (List.finRange N).any fun m => search G k a m && search G k m b
    33
    34end Lax733996.Reachability
    35
    Builds on

    none

    Used by
    From Mathlib

    Discussion

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

    Loading discussion…