Dummies的迭代/動態拓撲排序

Question

我目前正在C++中實現一個動態DAG圖形 - 它將通過用戶界面顯示給用戶，插入/移除節點/邊界將是常用操作。

圖的大小可能範圍從真正的小規模到大規模 - 我旨在支持數百萬個節點。因此，我正在尋找一種最佳的數據結構，它不會佔用太多的內存空間，但也可以通過在拓撲排序的節點上進行快速多線程迭代來快速插入/刪除（所以多個節點可以並行執行）。

我還沒有做過任何分析，看看是否每次修改完成後重新計算拓撲排序的完整圖的樸素方法會削減它，但爲了學習，我想我寧願找到一個「更聰明」的方式。

我不知道如何處理圖的多線程迭代，但一開始我偶然發現了一些與迭代/動態拓撲排序步驟相關的論文，問題在於它們是有點太聰明，我不明白。它進入了理論/數學方面，缺乏具體的實施例子，可以幫助我理解正在發生的事情。

下面是這種紙的例子：A Labeling Approach to Incremental Cycle Detection。

由於缺乏像「迭代/動態拓撲排序傻瓜」這樣的論文，有沒有人有任何關於主題的提示？

Answer 1

動態toposort算法（未經測試）。

從拓撲排序的頂點序列開始。

1. 如果添加了沒有邊的頂點，請將其插入序列中的任何位置。
2. 如果刪除邊或頂點，則不執行任何操作。
3. 如果添加了前向邊（從較低排序到較高排序的頂點），則不執行任何操作。
4. 如果添加了新的後沿A → B，請在A之後直接移動B.將B的出邊標記爲新。根據需要重複第3點和第4點。 （如果可以移動幾個頂點，則從最低排序頂點開始;如果要移動的頂點具有多個新輸入邊，則從排序最高的頂點中選擇一個頂點）。如果在此過程中遇到同一個頂點兩次，請報告一個循環。

該算法本身不檢測週期，但可以將週期搜索限制爲移動的頂點的子集。

Answer 2

確實有動態托架的工作。

Pearce & Kelly http://homepages.ecs.vuw.ac.nz/~djp/dts.html有一個算法，他們聲稱既簡單又實用高效。他們還提供了一個C++實現。通過介紹，他們討論更簡單的變體。

下面是一些關於這個問題的後續工作，按照時間順序。後來的方法往往比以前的方法更復雜。即使不是這樣，後面的文章可能會認爲你已經閱讀過較早的文章。你顯然是從這份名單上的最後一篇文章開始的，這篇文章可能已經深入到了最後。

• http://www.cs.princeton.edu/~sssix/papers/dto-icalp08.pdf
• http://dl.acm.org/citation.cfm?ID=1496890
• http://dl.acm.org/citation.cfm?ID=2071382
• http://arxiv.org/pdf/1310.8381.pdf（你在你的問題提）