pearce-kelly
An implementation of the Pearce-Kelly dynamic topological sorting algorithm for directed acyclic graphs (DAG). The canonical application of topological sorting is in scheduling a sequence of jobs or tasks based on their dependencies.
Features
- Fast tracking (performing more activities in parallel)
- Cycle detection
- Dynamic edge insertions and deletions
References
- Ragnar Lárus Sigurðsson: Practical Performance of Incremental Topological Sorting and Cycle Detection Algorithms
- David J. Pearce, Paul H. J. Kelly: A Dynamic Topological Sort Algorithm for Directed Acyclic Graphs
- David J. Pearce, Paul H. J. Kelly: A Batch Algorithm for Maintaining a Topological Order