The problem of topologically sorting a directed graph is about arranging its nodes so that all edges go in the same direction. For example, consider the following directed graph:

an example

A topological sort of this graph is:

example fixed

There are often many possible solutions for a given graph and we are simply interested in obtaining one of them. This is a well-known problem and optimal algorithms are known which need O(v+e) time, where v is the number of nodes and e the number of edges.

A variation on this, called the Dynamic Topological Sort (DTS) problem, is that of updating the topological sort after a new edge is added to the graph. For example, consider adding an edge from A to C in our sorted graph above. In this case, we need only swap the positions of A and C to update the sort. Here, the difficulty lies in performing the least amount of work to obtain a new topological sort. It turns out this problem has not been studied very much in the past and details of existing algorithms can be found in my papers below.

Publications

[PK04]
A Dynamic Algorithm for Topologically Sorting Directed Acyclic Graphs. David J. Pearce and Paul H. J. Kelly. In Proceedings of the 3rd international Workshop on Efficient and experimental Algorithms (WEA'04), volume 3059 of Lecture Notes in Computer Science, pages 383--398, 2004. © Springer-Verlag. [ Postscript / PDF / Powerpoint / SpringerLink ]

[PK05a]
A Dynamic Topological Sort Algorithm for Directed Acyclic Graphs. David J. Pearce and Paul H.J. Kelly. ACM Journal of Experimental Algorithmics (JEA), volume 11, pages 1.7, 2007. © ACM Press. This is an extended version of the WEA'04 paper and gives a better exposition and more accurate data. [ ACM Link ]. A preprint is also available [ Postscript / PDF ]

[Pea05]
David J. Pearce. Some directed graph algorithms and their application to pointer analysis. Ph.D. Thesis, Imperial College of Science, Technology and Medicine, University of London, February 2005. [postscript / PDF]

Software

The software used in the experiments detailed in the above papers is written in C++ and uses the BOOST Graph Library. The latest version is: oto-test-06102005.tgz. You'll probably also want my graphgen package to randomly generate the input files.

Related Work

[AHRSZ90]
Incremental Evaluation of Computational Circuits. Bowen Alpern and Roger Hoover and Barry K. Rosen and Peter F. Sweeney and F. Kenneth Zadeck. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 32--42, 1990. [ ACM Link ]

[MNR96]
Maintaining a topological order under edge insertions. Alberto Marchetti-Spaccamela and Umberto Nanni and Hans Rohnert. Information Processing Letters, 59(1):53--58, 1996.

[KB05]
Online Topological Ordering. Irit Katriel and Hans L. Bodlaender. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 443--450, 2005. [ ACM Link ]

[AFM06]
An O(n^{2.75}) algorithm for online topological ordering. Deepak Ajwani and Tobias Friedrich and Ulrich Meyer. In Proceedings of the Scandanavian Workshop on Algorithm Theory, pages 53--63, 2006, Springer-verlag.