<分区>
我目前正在处理图形实现的性能问题。
使用的技术
它是用 C++ 编写的。目前，该图是通过 BGL 实现的。
关于图表
托管图是动态的和无向的。它有两种结构:大量的完全子图和少量的单边图。唯一需要的信息是顶点的直接邻域。
问题陈述
一开始，完整的子图很小(大约10个顶点)而且很多(大约13k)。 BGL 的邻接表实现非常完美。但是现在，它被要求管理 5000 个顶点的几个子图。这意味着 5000x5000 条边。现在在时间和空间上的表现都很差。
被拒绝的解决方案
我的第一个想法是使用 BGL 提供的邻接矩阵实现。但它不允许动态图。为了解决这个约束，有两种解决方案:为动态图提供邻接矩阵的新实现，或者在静态图中使用可用顶点池。经过反射(reflection)，我认为这不是一个好主意:空间复杂度仍然是VxV/2。
最终解决方案和问题
所以，这是我的最终解决方案:不使用 BGL，实现顶点包来表示完整的子图(不需要边)并直接连接少数单个边的顶点。通过这样做，最大子图的空间复杂度下降到它的顶点数，大约 5000。
- 您认为最后一个解决方案好吗？
- 如果不是，我可以使用哪个实现？为什么？
更新 1
有关图表的更多信息: 该图具有约 100k 个顶点，约 3 个顶点的约 13k 个完整子图，以及大小范围 [10-5000] 的约 100 个完整子图。每条边都有捆绑属性。
更新2
我最近学会了感谢Salim Jouilli节点包是 hypergraph 的坦率方法其中超边包含节点的子集。
更新3
我已完成解决方案的实现。我有效地减少了内存消耗和运行时间:从 6GB 到 24MB，从 50 分钟到 2 分钟 30。