A Dynamic Topological Sort Algorithm for Directed Acyclic Graphs

A Dynamic Topological Sort Algorithm for Directed Acyclic Graphs DAVID J. PEARCE Victoria University of Wellington and PAUL H. J. KELLY Imperial College London We consider the problem of maintaining the topological order of a directed acyclic graph (DAG) in the presence of edge insertions and deletions. We present a new algorithm and, although this has inferior time complexity compared with the best previously known result, we find that its simplicity leads to better performance in practice. In addition, we

provide an empirical comparison against the three main alternatives over a large number of random DAGs. The results show our algorithm is the best for sparse digraphs and only a constant factor slower than the best on dense digraphs. Categories and Subject Descriptors: E.1 [Data Structures]: Graphs and Networks; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems—Compu- tations on discrete structures; G.2.2 [Discrete Mathematics]: Graph Theory—Graph algorithms General Terms: Algorithms, Experimentation, Theory Additional Key Words and Phrases: Dynamic graph algorithms, topological sort 1. INTRODUCTION A topological ordering, ord D , of a directed acyclic graph D = (V, E) maps each vertex to a priority value such that ord D (x) < ord D ( y) holds for all edges This work was supported by the UK Engineering and Physical Sciences Research Council (EPSRC) through a PhD studentship and grant number GR/R15566. A preliminary version of this paper was presented at the 3rd International Workshop on Efficient and Experimental Algorithms (WEA04), 2004. This work includes a more detailed analysis of algo- rithms for the dynamic topological order problem and an improved experimental study. We must also report that, since the WEA04 workshop, an error in our implementation of algorithm AHRSZ was found. As a result, the performance data reported for AHRSZ in this paper differs from that shown in the workshop paper. Authors’ Addresses: David J. Pearce, School of Mathematics, Statistics and Computer Science, Victoria University of Wellington, Wellington, New Zealand; email: david.pearce@mcs.vuw.ac.nz; Paul H.J. Kelly, Department of Computing, 180 Queen’s Gate, South Kensington Campus, Imperial College London, SW7 2AZ, United Kingdom; email: p.kelly@imperial.ac.uk. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or direct commercial advantage and that copies show this notice on the first page or initial screen of a display along with the full citation. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, to redistribute to lists, or to use any component of this work in other works requires prior specific permission and/or a fee. Permissions may be requested from Publications Dept., ACM, Inc., 2 Penn Plaza, Suite 701, New York, NY 10121-0701 USA, fax +1 (212) 869-0481, or permissions@acm.org....

Website: www.doc.ic.ac.uk | Filesize: -
No of Page(s): 24
Download A Dynamic Topological Sort Algorithm for Directed Acyclic Graphs.pdf