<p>There is indeed work on dynamic toposort.</p>

<p>Pearce &amp; Kelly <a href="http://homepages.ecs.vuw.ac.nz/~djp/dts.html" rel="nofollow">http://homepages.ecs.vuw.ac.nz/~djp/dts.html</a> have an algorithm that they claim is both simple and practically efficient. They also provide a C++ implementation. By way of introduction, they discuss even simpler variants. </p>

<p>Here is some of the later work on this problem, in chronological order. Later methods tend to be more complicated than earlier ones. Even if not, the later papers may assume that you have already read the earlier ones. You apparently started with the last paper on this list, which might have been jumping into the deep end.</p>

<ul>
<li><a href="http://www.cs.princeton.edu/~sssix/papers/dto-icalp08.pdf" rel="nofollow">http://www.cs.princeton.edu/~sssix/papers/dto-icalp08.pdf</a></li>
<li><a href="http://dl.acm.org/citation.cfm?ID=1496890" rel="nofollow">http://dl.acm.org/citation.cfm?ID=1496890</a></li>
<li><a href="http://dl.acm.org/citation.cfm?ID=2071382" rel="nofollow">http://dl.acm.org/citation.cfm?ID=2071382</a></li>
<li><a href="http://arxiv.org/pdf/1310.8381.pdf" rel="nofollow">http://arxiv.org/pdf/1310.8381.pdf</a> (which you mention in your question)</li>
</ul>
Iterative/Dynamic Topological Sorting for Dummies
<p>I'm currently implementing a dynamic DAG graph in C++—it will be displayed through an UI to the user and insertion/removal of nodes/edges will be common operations.</p>

<p>The size of the graphs might potentially range from the really small scale to the large one—I'm aiming to support millions of nodes.</p>

<p>As such, I'm looking for an optimal data structure that won't take up too much space in memory but also for a way to have fast insertions/removals with a fast multi-threaded iteration over the topologically sorted nodes (so multiple nodes can be executed in parallel).</p>

<p>I haven't done any profiling to see if a naive approach of recomputing a topological sort of the full graph each time a modification is being done would cut it, but for the sake of learning, I thought I'd rather find a “smarter” way.</p>

<p>I've got no idea how to approach the multi-threaded iteration of the graph but for a start I've stumbled upon some papers related to the iterative/dynamic topological sorting step, and the problem is that they're a bit too smart for me to understand. It gets way into the theoretical/mathematical side and lacks concrete implementation examples that could help me to understand what's going on.</p>

<p>Here's an example of a such paper: <a href="http://arxiv.org/pdf/1310.8381.pdf" rel="nofollow">A Labeling Approach to Incremental Cycle Detection</a>.</p>

<p>Since there's a lack of papers such as “Iterative/Dynamic Topological Sorting for Dummies”, does anyone have any hint on subject?</p>