Reachability
In graph theory, reachability is the ability 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.
Definition
For a directed graph D = (V, A), the reachability relation 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.[1]
DAGs and partial orders
The reachability relation of a directed acyclic graph is a partial order; any partial order may be defined in this way, for instance as the reachability relation of its transitive reduction.[2] If a directed graph is not acyclic, its reachability relation will be a preorder but not a partial order.[3]
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 search.[4]
Preprocessing algorithms (such as a simplified Floyd–Warshall algorithm,[5] or Thorup's algorithm for planar digraphs,[6] which uses only O(n log n) time and space) create data structures which allow subsequent reachability queries to be answered in constant time (i.e., in a small fixed amount of time, independent of the size of the graph). Such algorithms (or their data structures) are sometimes called oracles, since the precomputed data structure allows any query to be answered immediately, similar to how Turing machine oracles answer questions. Many reachability algorithms (including the two mentioned above) can be easily extended to provide distance or approximate distance algorithms for graphs where each directed edge has a distance (usually called a weight).
Node failures
A related problem is to solve reachability queries with some number k of node failures. For example: "Can node u still reach node v even though nodes s1, ..., sk have failed and can no longer be used?" The breadth-first search technique works just as well on such queries, but constructing an efficient oracle is more challenging.[7]
See also
References
- ^ Skiena, Steven S. (2011), "15.5 Transitive Closure and Reduction", The Algorithm Design Manual (2nd ed.), Springer, pp. 495–497, ISBN 9781848000698.
- ^ Cohn, Paul Moritz (2003), Basic Algebra: Groups, Rings, and Fields, Springer, p. 17, ISBN 9781852335878.
- ^ Schmidt, Gunther (2010), Relational Mathematics, Encyclopedia of Mathematics and Its Applications, vol. 132, Cambridge University Press, p. 77, ISBN 9780521762687.
- ^ Gersting, Judith L. (2006), Mathematical Structures for Computer Science (6th ed.), Macmillan, p. 519, ISBN 9780716768647.
- ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), "Transitive closure of a directed graph", Introduction to Algorithms (2nd ed.), MIT Press and McGraw-Hill, pp. 632–634, ISBN 0-262-03293-7.
- ^ Thorup, Mikkel (2004), "Compact oracles for reachability and approximate distances in planar digraphs", Journal of the ACM, 51 (6): 993–1024, doi:10.1145/1039488.1039493, MR 2145261.
- ^ Demetrescu, Camil; Thorup, Mikkel; Chowdhury, Rezaul Alam; Ramachandran, Vijaya (2008), "Oracles for distances avoiding a failed node or link", SIAM Journal on Computing, 37 (5): 1299–1318, doi:10.1137/S0097539705429847, MR 2386269.