用于动态图形的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++库？

回答

相关问题