Dynamic Topological Sort
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:
A topological sort of this graph is:
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.
A Batch Algorithm for Maintaining a Topological Order. David J. Pearce and Paul H.J. Kelly. In Australasian Computer Science Conference (ACSC), pages 79--88, 2010. ©Australian Computer Society, Inc.
A Dynamic Topological Sort Algorithm for Directed Acyclic Graphs. David J. Pearce and Paul H.J. Kelly. In ACM Journal of Experimental Algorithmics (JEA), 11 pages 1.7, 2007. ©ACM Press
Some directed graph algorithms and their application to pointer analysis.. David J. Pearce. PhD Thesis, Imperial College of Science, Technology and Medicine, University of London, 2005.