Reachability
Encyclopedia
In graph theory
, reachability is the notion of being able to get from one vertex
in a directed graph
to some other vertex. Note that reachability in undirected graphs is trivial — it is sufficient to find the connected components in the graph, which can be done in linear time.
of D is the transitive closure
of its arc set A, which is to say the set of all ordered pairs (s, t) of vertices in V for which there exist vertices v0 = s, v1, …, vd = t such that (vi - 1, vi ) is in A for all 1 ≤ i ≤ d.
is a partial order; any partial order may be defined in this way, for instance as the reachability relation of its transitive reduction
. If a directed graph is not acyclic, its reachability relation will be a preorder
but not a partial order.
.
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).
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, reachability is the notion of being able to get from one vertex
Vertex (graph theory)
In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...
in a directed graph
Directed graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
to some other vertex. Note that reachability in undirected graphs is trivial — it is sufficient to find the connected components in the graph, which can be done in linear time.
Definition
For a directed graph D = (V, A), the reachability relationRelation (mathematics)
In set theory and logic, a relation is a property that assigns truth values to k-tuples of individuals. Typically, the property describes a possible connection between the components of a k-tuple...
of D is the transitive closure
Transitive closure
In mathematics, the transitive closure of a binary relation R on a set X is the transitive relation R+ on set X such that R+ contains R and R+ is minimal . If the binary relation itself is transitive, then the transitive closure will be that same binary relation; otherwise, the transitive closure...
of its arc set A, which is to say the set of all ordered pairs (s, t) of vertices in V for which there exist vertices v0 = s, v1, …, vd = t such that (vi - 1, vi ) is in A for all 1 ≤ i ≤ d.
DAGs and partial orders
The reachability relation of a directed acyclic graphDirected acyclic graph
In mathematics and computer science, a directed acyclic graph , is a directed graph with no directed cycles. That is, it is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no way to start at some vertex v and follow a sequence of...
is a partial order; any partial order may be defined in this way, for instance as the reachability relation of its transitive reduction
Transitive reduction
In mathematics, a transitive reduction of a binary relation R on a set X is a minimal relation R' on X such that the transitive closure of R' is the same as the transitive closure of R. If the transitive closure of R is antisymmetric and finite, then R' is unique...
. If a directed graph is not acyclic, its reachability relation will be a preorder
Preorder
In mathematics, especially in order theory, preorders are binary relations that are reflexive and transitive.For example, all partial orders and equivalence relations are preorders...
but not a partial order.
Algorithms
Algorithms for reachability fall into two classes: those that require preprocessing and those that do not. For the latter case, resolving a single reachability query can be done in linear time using algorithms such as breadth first search or iterative deepening depth-first searchIterative deepening depth-first search
Iterative deepening depth-first search is a state space search strategy in which a depth-limited search is run repeatedly, increasing the depth limit with each iteration until it reaches d, the depth of the shallowest goal state...
.
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).