Reachability
In graph theory, reachability refers to the ability to get from one vertex to another within a graph. A vertex formula_1 can reach a vertex formula_2 (and formula_2 is reachable from formula_1) if there exists a sequence of adjacent vertices (i.e. a walk) which starts with formula_1 and ends with formula_2. 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; therefore, in such a  graph, reachability is symmetric (formula_1 reaches formula_2 iff formula_2 reaches formula_1). 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 (which, incidentally, need not be symmetric). Definition. For a directed graph formula_11, with vertex set formula_12 and edge set formula_13, the reachability relation of formula_14 is the transitive closure of formula_13, which is to say the set of all ordered pairs formula_16 of vertices in formula_12 for which there exists a sequence of vertices formula_18 such that  the edge formula_19 is in formula_13 for all formula_21. If formula_14 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 formula_1 can reach formula_2, then we know that formula_2 "cannot" reach formula_1. Intuitively, if we could travel from formula_1 to formula_2 and back to formula_1, then formula_14 would contain a cycle, contradicting that it is acyclic. If formula_14 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. 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 formula_32 time. Three different algorithms and data structures for three different, increasingly specialized situations are outlined below. Floyd-Warshall Algorithm. 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 formula_33 time and formula_34 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. Thorup's Algorithm. For planar digraphs, a much faster method is available, as described by Mikkel Thorup in 2004. This method can answer reachability queries on a planar graph in formula_32 time after spending formula_36 preprocessing time to create a data structure of formula_36 size. This algorithm can also supply  approximate shortest path distances, as well as route information. The overall approach is to associate with each vertex a relatively small set of so-called separator paths such that any path from a vertex formula_38 to any other vertex formula_39 must go through at least one of the separators associated with formula_38 or formula_39. An outline of the reachability related sections follows. Given a graph formula_14, the algorithm begins by organizing the vertices into layers starting from an arbitrary vertex formula_43. The layers are built in alternating steps by first considering all vertices reachable "from" the previous step (starting with  just formula_43) and then all vertices which reach "to" the previous step until all vertices have been assigned to a layer. By construction of the layers, every vertex appears at most two layers, and every directed path, or dipath, in formula_14 is contained within two adjacent layers formula_46 and formula_47. Let formula_48 be the last layer created, that is, the lowest value for formula_48 such that formula_50. The graph is then re-expressed as a series of digraphs formula_51 where each formula_52 and where formula_53 is the contraction of all previous levels formula_54 into a single vertex. Because every dipath  appears in at most two consecutive layers, and because each formula_55 is formed by two consecutive layers, every dipath in formula_14 appears in its entirety in at least one formula_55 (and no more than 2 consecutive such graphs) For each formula_55, three separators are identified which, when removed, break the graph into three components which each contain at most formula_59 the vertices of the original. As formula_55 is built from two layers of opposed dipaths, each separator may consist of up to 2 dipaths, for a total of up to 6 dipaths over all of the separators. Let formula_61 be  this set of dipaths. The proof that such separators can always be found is related to the Planar Separator Theorem of Lipton and Tarjan, and these separators can be located in linear time. For each formula_62, the directed nature of formula_63 provides for a natural indexing of its vertices from the start to the end of the path. For each vertex formula_38 in formula_55, we locate the first vertex in formula_63 reachable by formula_38, and the last vertex in formula_63 that reaches to formula_38. That is, we are looking at how early into formula_63 we can get from formula_38, and  how far we can stay in formula_63 and still get back to formula_38. This information is stored with each formula_38. Then for any pair of vertices formula_75 and formula_39, formula_75 can reach formula_39 "via" formula_63 if formula_75 connects to formula_63 earlier than formula_39 connects from formula_63. Every vertex is labelled as above for each step of the recursion which builds formula_84. As this recursion has logarithmic depth, a total of formula_85 extra information is stored per vertex. From this point, a logarithmic time query for reachability is as simple as looking over each pair of labels for a common, suitable  formula_63. The original paper then works to tune the query time down to formula_32. In summarizing the analysis of this method, first consider that the layering approach partitions the vertices so that each vertex is considered only formula_32 times. The separator phase of the algorithm breaks the graph into components which are at most formula_59 the size of the original graph, resulting in a logarithmic recursion depth. At each level of the recursion, only linear work is needed to identify the separators as well as the connections possible between vertices. The overall result is formula_90 preprocessing time with only formula_85  additional information stored for each vertex. Kameda's Algorithm. An even faster method for pre-processing, due to T. Kameda in 1975, can be used if the graph is planar, acyclic, and also exhibits the following additional properties: all 0-indegree and all 0-outdegree vertices appear on the same face (often assumed to be the outer face), and it is possible to partition the boundary of that face into two parts such that all 0-indegree vertices appear on one part, and all 0-outdegree vertices appear on the other (i.e. the two types of vertices do not alternate ). If formula_14 exhibits these properties, then we can preprocess the graph in only formula_93 time, and store only formula_85 extra bits per vertex, answering reachability queries for any pair of vertices in formula_32 time with a simple comparison. Preprocessing performs the following steps. We add a new vertex formula_1 which has an edge to each 0-indegree vertex, and another new vertex formula_2 with edges from each 0-outdegree vertex. Note that the properties of formula_14 allow us to do so while maintaining planarity, that is, there will still be no edge crossings after these additions. For each vertex we  store the list of adjacencies (out-edges) in order of the planarity of the graph (for example, clockwise with respect to the graph's embedding). We then initialize a counter formula_99 and begin a Depth-First Traversal from formula_1. During this traversal, the adjacency list of each vertex is visited from left-to-right as needed. As vertices are popped from the traversal's stack, they are labelled with the value formula_101, and formula_101 is then decremented. Note that formula_2 is always labelled with the value formula_104 and formula_1 is always labelled with formula_106. The depth-first traversal is then  repeated, but this time the adjacency list of each vertex is visited from right-to-left. When completed, formula_1 and formula_2, and their incident edges, are removed. Each remaining vertex stores a 2-dimensional label with values from formula_109 to formula_110. Given two vertices formula_75 and formula_38, and their labels formula_113 and formula_114, we say that formula_115 if and only if formula_116, formula_117, and there exists at least one component formula_118 or formula_119 which is strictly less than formula_120 or formula_121, respectively. The main result of this method then states that formula_38 is reachable from formula_75 if and only if  formula_115, which is easily calculated in formula_32 time. Related problems. A related problem is to solve reachability queries with some number formula_48 of vertex failures. For example: "Can vertex formula_75 still reach vertex formula_38 even though vertices formula_129 have failed and can no longer be used?" A similar problem may consider edge failures rather than vertex failures, or a mix of the two. The breadth-first search technique works just as well on such queries, but constructing an efficient oracle is more challenging. Another problem related to reachability queries is in quickly recalculating changes to reachability relationships when some portion  of the graph is changed. For example, this is a relevant concern to garbage collection which needs to balance the reclamation of memory (so that it may be reallocated) with the performance concerns of the running application.