A Dynamic Topological Sort Algorithm for Directed Acyclic Graphs
Author(s). David J. Pearce and Paul H.J. Kelly.
Venue. In ACM Journal of Experimental Algorithmics (JEA), 11 pages 1.7, 2007. ©ACM Press
Abstract. We consider the problem of maintaining the topological order of a directed acyclic graph (DAG) in the presence of edge insertions and deletions. We present a new algorithm and, although this has inferior time complexity compared with the best previously known result, we find that its simplicity leads to better performance in practice. In addition, we provide an empirical comparison against the three main alternatives over a large number of random DAGs. The results show our algorithm is the best for sparse digraphs and only a constant factor slower than the best on dense digraphs.
Notes. This algorithm is used in the C++ Abseil library (see here) and TensorFlow (see here), both of which were originally developed at Google and subsequently released as open source. The algorithm is also found in the widely used JGraphT library (see here), and in the SAT solver Monosat. There are also a number of implementations available (see e.g. here, here and here) as well as my own C++ implementation also available on GitHub. Finally, this algorithm has found interesting uses for multiple sequence alignment (see e.g. here and here.