Dr. David J. Pearce

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 directed graph with an invalid topological order

A topological sort of this graph is:

A directed graph with a corrected topological order

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.

Downloads

Version 1.0 (Oct 2005)
Version 0.8 (Jan 2005)
Version 0.5 (Aug 2003)

Related Publication(s)