On-line graph algorithms for incremental compilation

Compilers usually construct various data structures which often vary only slightly from compilation run to compilation run. This paper describes in a compact and uniform way solutions to several problems arising in order to quickly update these data structures instead of building them from scratch each time. All the considered problems can be reduced to graph problems. Specifically, we give algorithms for the dynamic problems of loop detection, topological order, reachability from the start routine, and transitive closure. As far as the dynamic maintenance of a topological order is concerned, for which no previous solution is known to the authors, simple algorithms and data structures are provided, and the achieved upper bound is O(n) amortized time per update in a sequence of O(m) edge insertions, which favourably compares to the trivial O(n+m) worst case time bound (applying the off-line algorithm). The additional space requirement, besides the space to represent the graph itself, is O(n). We also discuss by an example the harder fully dynamic version of topological order.