This article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Mathematics Mid‑priority This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics Mid This article has been rated as Mid-priority on the project's priority scale.

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)[reply]

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 ${\displaystyle (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 ${\displaystyle s}$ can reach ${\displaystyle t}$, then ${\displaystyle t}$ cannot reach ${\displaystyle s}$" applies only if ${\displaystyle s\neq t}$.

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