Reachability

In graph theory, reachability refers to the ability to get from one vertex to another within a graph. A vertex s {displaystyle s} can reach a vertex t {displaystyle t} (and t {displaystyle t} is reachable from s {displaystyle s} ) if there exists a sequence of adjacent vertices (i.e. a path) which starts with s {displaystyle s} and ends with t {displaystyle t} . In graph theory, reachability refers to the ability to get from one vertex to another within a graph. A vertex s {displaystyle s} can reach a vertex t {displaystyle t} (and t {displaystyle t} is reachable from s {displaystyle s} ) if there exists a sequence of adjacent vertices (i.e. a path) which starts with s {displaystyle s} and ends with t {displaystyle t} . In an undirected graph, reachability between all pairs of vertices can be determined by identifying the connected components of the graph. Any pair of vertices in such a graph can reach each other if and only if they belong to the same connected component. The connected components of an undirected graph can be identified in linear time. The remainder of this article focuses on the more difficult problem of determining pairwise reachability in a directed graph. For a directed graph G = ( V , E ) {displaystyle G=(V,E)} , with vertex set V {displaystyle V} and edge set E {displaystyle E} , the reachability relation of G {displaystyle G} is the transitive closure of E {displaystyle E} , which is to say the set of all ordered pairs ( s , t ) {displaystyle (s,t)} of vertices in V {displaystyle V} for which there exists a sequence of vertices v 0 = s , v 1 , v 2 , . . . , v k = t {displaystyle v_{0}=s,v_{1},v_{2},...,v_{k}=t} such that the edge ( v i − 1 , v i ) {displaystyle (v_{i-1},v_{i})} is in E {displaystyle E} for all 1 ≤ i ≤ k {displaystyle 1leq ileq k} . If G {displaystyle G} is acyclic, then its reachability relation is a partial order; any partial order may be defined in this way, for instance as the reachability relation of its transitive reduction. A noteworthy consequence of this is that since partial orders are anti-symmetric, if s {displaystyle s} can reach t {displaystyle t} , then we know that t {displaystyle t} cannot reach s {displaystyle s} . Intuitively, if we could travel from s {displaystyle s} to t {displaystyle t} and back to s {displaystyle s} , then G {displaystyle G} would contain a cycle, contradicting that it is acyclic.If G {displaystyle G} is directed but not acyclic (i.e. it contains at least one cycle), then its reachability relation will correspond to a preorder instead of a partial order. Algorithms for determining reachability fall into two classes: those that require preprocessing and those that do not. If you have only one (or a few) queries to make, it may be more efficient to forgo the use of more complex data structures and compute the reachability of the desired pair directly. This can be accomplished in linear time using algorithms such as breadth first search or iterative deepening depth-first search. If you will be making many queries, then a more sophisticated method may be used; the exact choice of method depends on the nature of the graph being analysed. In exchange for preprocessing time and some extra storage space, we can create a data structure which can then answer reachability queries on any pair of vertices in as low as O ( 1 ) {displaystyle O(1)} time. Three different algorithms and data structures for three different, increasingly specialized situations are outlined below. The Floyd–Warshall algorithm can be used to compute the transitive closure of any directed graph, which gives rise to the reachability relation as in the definition, above. The algorithm requires O ( | V | 3 ) {displaystyle O(|V|^{3})} time and O ( | V | 2 ) {displaystyle O(|V|^{2})} space in the worst case. This algorithm is not solely interested in reachability as it also computes the shortest path distance between all pairs of vertices. For graphs containing negative cycles, shortest paths may be undefined, but reachability between pairs can still be noted.