如何用大量的大完备子图有效地实现图？

Question

我目前正在处理图形实现的性能问题。

已使用技术

它是用C++编程的。目前，由于BGL实现了该图形。

关于图

托管图是动态的、无向的。它有两种结构:许多完备的子图和很少的单边。唯一需要的信息是顶点的直接邻域。

问题陈述

在开始时，完全子图是小的(约10个顶点)和许多(约13k)。一个邻接列表实现，BGL的一个，是完美的。但是现在，它被要求管理5000个顶点的少数子图。这意味着5000x5000边。当时在时间和空间上的表现很差。

被拒绝的解决方案

我的第一个想法是使用BGL提供的邻接矩阵实现。但它不允许动态图形。为了解决这个约束，有两种解决方案:为动态图提供邻接矩阵的新实现，或者在静态图中使用可用顶点池。经过思考，我认为这不是一个好主意:空间复杂性仍然是VxV/2。

最终解决方案和问题

因此，这里是我的最后解决方案:不要使用BGL，实现包的顶点来表示完整的子图(不需要边)，并直接连接几个单边的顶点。通过这样做，最大子图的空间复杂度下降到它的顶点数，大约5000。

1. 你认为最后这个解决方案是好的吗？
2. 如果没有，我可以使用哪个实现？为什么？

更新1

关于该图的更多信息:该图有~100 k个顶点，~13k约3个顶点的完全子图，以及~100个大小范围为10-5000的完全子图。每个边都有捆绑的属性。

更新2

感谢萨利姆·朱利，我最近了解到，节点包是超图的一种坦率的方法，其中超边包含在节点的子集中。

更新3

我已经完成了解决方案的实现。我有效地增加了内存消耗和运行时:从6GB增加到24MB，从50分钟增加到2min30。

Answer 1

你的最后一个解决方案就是我自己会去的那个。听起来很有效率。

Answer 2

如果您的问题在将来会增加(再次)，也许使用图形数据库的努力是值得的。这样，您就可以将存储和业务逻辑解耦，并将它们作为单独的问题处理。

Answer 3

一般来说，拥有2500万条边并不是什么大问题。但是我只在有很多节点的稀疏图上使用它(一个街道网络)。

如果内存使用和访问时间对您的需要变得非常关键，请尝试使用boost压缩稀疏图row.html。

使用起来有点烦人，因为它要求以有序的方式插入边缘，但可能没有办法显着地提高效率(最多只增加几个百分点)。