在大型DAG上進行拓撲分類的示例

Question

我在尋找真實世界的應用，其中拓撲分類在大圖大小上執行。

一些我可以找到這種實例的領域是生物信息學，依賴關係解析，數據庫，硬件設計，數據倉庫......但是我希望你們中的一些人可能遇到或聽說過任何特定的算法/項目/應用程序/需要topsort的數據集。

即使數據/項目可能無法公開訪問，任何提示（以及對潛在圖形大小數量級的估計）都可能有所幫助。

Answer 1

下面是一些例子迄今拓撲排序我看到：

• 雖然在分佈式系統調度的任務圖，它通常是 需要的任務拓撲排序，然後將其分配給 資源。我知道任務圖中包含超過100,000個要按拓撲順序排序的 任務。在這方面請參閱this。

• 曾幾何時，我一直致力於文檔管理系統。該系統上的每個 文檔對其他文檔的一組文檔具有某種優先約束，例如，其內容類型或字段引用。 然後，系統應該能夠生成具有保留的拓撲順序的文檔 的順序。據我記憶，兩年前有大約5,000,000個文件可用 !!!

• 在社交網絡領域，有着名的查詢知道了網絡中最大的友誼距離 。此問題需要 通過BFS方法遍歷圖形，等於拓撲排序的成本。考慮Facebook的成員，並找到你的答案 。

如果您需要更多的實例，請不要猶豫，問我。我曾在許多在大型圖表上工作的項目工作過。

P.S.對於大型DAG數據集，您可以查看Stanford Large Network Dataset Collection和Graphics@ Illinois頁面。

Answer 2

我不確定這是否符合您的要求，但您知道嗎Bio4j項目？

並非存儲在基於圖的數據庫中的所有內容都適合於拓撲排序（在圖的重要部分存在定向循環），但是存在子圖，如基因本體論和分類標準，其中該排序可能具有感。

Answer 3

TopoR是一種商用拓撲PCB路由器，首先將PCB路由爲拓撲問題，然後將拓撲轉換爲物理空間。它們支持多達32個電子層，因此它應該能夠有數千個連接（例如10^4）。

我懷疑集成電路可能會使用類似的方法。

Answer 4

company where I work管理軟件漏洞和補丁的（專有）數據庫。修補程序通常由軟件供應商（如Microsoft，Adobe等）定期發佈，而「新的和改進的」修補程序「替代」較舊的修補程序，因爲如果將新修補程序應用於主機，則舊補丁不再需要。

這產生了一個DAG，其中每個軟件補丁是一個節點，每個「替代」補丁的弧都指向一個節點。圖中目前接近10K個節點，並且每週都會添加新的修補程序。

拓撲排序在此上下文中用於驗證圖形不包含循環 - 如果它們確實存在，則意味着在添加新的數據庫記錄時出現錯誤，或者由於錯誤的數據複製而引入損壞數據庫實例之間。