Talk:Reachability

Oracles?

In the "Algorithms" section:

"Typically algorithms for reachability that require preprocessing (and their corresponding data structures) are called oracles (similarly there are oracles for distance and approximate distance queries). "

The link to "oracles" needs to be reviewed. There are many Oracle pages in the disambiguation, but I believe that none of them match the usage invoked here. --Matt Westwood 07:00, 17 July 2010 (UTC)

Is reachability reflexive?

The article seems to be unclear regarding whether the reachability relation on a directed graph is reflexive. The definition section defines the reachability relation as the transitive closure of the edge set; this would mean that no vertex in a DAG is reachable from itself, since the transitive closure of the edge set of a DAG contains no pairs $(v,v)$.

• If this is intentional, it would be beneficial to note in the following paragraph that the reachability relation is a strict or irreflexive partial order, and to note that this diverges from the introduction's definition of reachability on undirected graphs via connected components.
• If it is unintentional, then the reachability relation should instead be defined as the reflexive-transitive closure, and the following paragraph should note that "if $s$ can reach $t$, then $t$ cannot reach $s$" applies only if $s\neq t$.

Tibia mariner (talk) 00:44, 3 February 2026 (UTC)