用於動態圖形的C/C++庫？

我正在尋找一個庫來操作動態圖。我有一個模擬，我必須重複計算圖形的平均測地線長度，然後對其結構進行一些更改（添加和刪除邊，在無向圖上，所有邊具有相同的權重）。用於動態圖形的C/C++庫？

我正在使用一個快速的C++包裝在我製作的igraph上。 igraph適用於靜態圖形，因此每次更改圖形時都要重新計算從頭開始的測地距離。這是一個蒙特卡羅模擬，所以我必須做這個數百萬次才能恢復一些統計數據。它開始變得很慢。

因此，我查找了動態圖的算法庫，可以在刪除或添加邊後重新計算剛更新的平均長度。我發現了關於這個主題的一些論文，但我真的沒有專家（我只是一個物理學家，我只是偶然地在一個問題上使用圖表......我幾乎沒有關於數據結構和算法的知識），所以我可以甚至不讀報紙，更不用說實施這些算法了。

我發現這個庫LEDA（http://www.algorithmic-solutions.com/leda/）似乎有一個動態圖形擴展，但它似乎沒有維護（下載免費版本的鏈接被破壞）並且它是專有的。

有沒有其他的選擇？我正在尋找C/C++庫。也許Haskell，如果我必須的，我絕對絕望。

來源

2011-07-06 Rafael S. Calsaverini

你是如何解決這個問題的？六年後，我仍然找不到這樣的（高性能）圖書館。 – javaLover

這個問題在提問時是在話題上，但它現在已經脫離主題。與此同時......我真的很想得到這個答案。它會讓我工作的東西容易得多。好吧。 –

-1

你有沒有看着Boost Graph Library

我沒有用它自己，但作爲加速的一部分，你可以期望它是非常高的質量，但它要求的C++專業技術措施。

來源

2011-07-06 21:53:10 antlersoft

Boost中有動態圖的算法嗎？在我看來，它只適用於靜態圖。 –

來自BGL文檔：「它是高度參數化的，因此它可以針對不同情況進行優化：圖形是有向或無向的，允許或不允許平行邊緣，有效地訪問邊緣或邊緣，快速以額外空間開銷爲代價的頂點插入和移除等。「不確定這是否是您需要的，或者您是否在尋找不需要訪問整個圖來說明變化的算法？ – antlersoft

是的，我感興趣的算法，可以快速計算測地線路徑的變化，基於我知道刪除或添加邊緣之前的測地線路徑作爲示例。根據本文的內容：http://www.ams.org/mathscinet-getitem?mr=2145260。 –

既然你在做蒙特卡洛，我認爲接近平均最短路徑長度是可以接受的。在每一步中，您都可以對少數幾個節點進行採樣，並報告從其中一個節點開始的路徑的平均最短路徑長度，這些路徑具有相同的期望值和希望的合理差異。另外，您在動態最短路徑上提到的JACM論文的參考文獻[3]是2004年的一項實驗性研究;也許作者會讓你使用他們的代碼。

來源

2011-07-07 02:08:57 xyzzy

現在我有一個評論的地方，它可能會有助於未來的答案知道你的圖表有多密集。 – xyzzy

嗨。我的圖形範圍從星形到完全連接。 :( –

如果我基於它們的連通性對節點進行採樣來計算平均路徑長度，我會引入偏差嗎？ –

我知道這個晚了，但你看過嗎LEMON？

來源

2012-02-15 21:48:15 Deathbreath

它使用呼吸第一次搜索。在幻燈片中，它使用「Bfs」。 http://lemon.cs.elte.hu/pub/doc/lemon-intro-presentation.pdf :( – javaLover

用於動態圖形的C/C++庫？

回答

相關問題