An Experimental Study of Dynamic Algorithms for Directed Graphs

Dynamic graph algorithms maintain a certain property (e.g., connectivity) of a graph that changes dynamically over time. Typical changes include insertion of a new edge and deletion of an existing edge. The challenge for a dynamic algorithm is to maintain, in an environment of dynamic changes, the desired graph property efficiently, i.e., without recomputing everything from scratch after each change. A problem is fully dynamic if both edge insertions and deletions are allowed, and it is partially dynamic if either edge insertions or edge deletions (but not both) are allowed. In the case of edge insertions (resp. deletions), the partially dynamic algorithm is called incremental (resp. decremental). In this paper, we are making a step forward in bridging the gap between theoretical results for directed graphs and their implementation by studying the practical properties of several dynamic algorithms for transitive closure on digraphs and depth first search and topological sorting on directed acyclic graphs (DAGs). The main goal of the paper is to confirm in practice the theoretical evidence that dynamic algorithms for digraphs are more efficient than their static counterparts, and characterize their behaviour in a given range of parameters.