performance - 用于高性能、低占用空间的图形查询的库？

Question

我自己已经很接近实现这个了，但在实现之前我仍然想知道这个轮子是否已经被发明了:我需要的是一个库，它允许我表示 DAG(有向无环图)，并且允许以非常高的性能对直接或间接连接的节点进行查询。到目前为止我已经比较了两种方法。

该图的大小将是数百万个节点，大约有 10-2000 万条边。大多数节点只有一两条边，但几千个节点可能有 10000 条或更多边。

用例是:创建图表的工作量并不重要，并且一旦创建它就不需要更新，或者更新不需要很快。然而，找到长度为 2(一个中间节点)的直接连接或特定间接连接应该非常快，并且边应该能够具有标签(例如权重、计数等)。此外，内存占用应该很小，并且查询应该是线程安全的。

我已经尝试使用一些标准软件包来实现此目的，例如Neo4J 或关系数据库，但对于某些事情来说，两者都太慢了:当涉及具有大量边的节点(巨大的连接集)时，关系数据库很难找到间接关系。 Neo4j 可以更好地处理这种情况，但仅查找直接连接的基本速度比关系数据库解决方案慢数千倍。在工作站上，关系数据库可以在不到 5 毫秒的时间内返回直接查询和许多间接查询的结果，但某些间接查询可能需要长达一分钟的时间。在同一系统上使用 Neo4j 时，那些间接查询只需要几秒钟，但直接查询都需要超过 100 毫秒。我希望能够将直接查询时间控制在 1 毫秒以下，将最差的间接查询时间控制在 1 秒以下(平均而言)。

我认为，如果做得巧妙，这一切都可以在内存中表示并执行，只需几GB堆空间，甚至对于更大的图，也会有策略通过巧妙的缓存和将部分图持久保存到磁盘的巧妙方法来非常快速地完成这些事情。但我找不到任何可以提供此功能的解决方案或库(最好是开源的)。我错过了什么吗？

Answer 1

具有数百万个节点和数千万条边的图在本世纪制造的任何台式计算机的内存中都可以轻松容纳。我建议使用 FORTRAN 风格

int ia[NVERT+1];
int ja[NEDGE];

其中边按尾部顶点排序，尾部位于 v 的边的索引 ia[v] 一直到 ia[v+1]-1，并且 ja[e] 列出第 e 边的头端。请注意，这大约需要 4(NVERT+NEDGE+1) 字节的内存，这比“只有几 GB”要少得多。

检查从一个顶点到另一个顶点是否存在边很简单；您查看第一个顶点的传出边。检查是否存在从一个顶点到另一个顶点的两条边路径也很简单；您找到第一个顶点的所有邻居，并检查它们中是否有任何一个有指向第二个顶点的出边。在最坏的情况下，这就是对你所有边缘的扫描。几乎可以肯定，您自己执行此操作的代码量也比连接数据库所需的代码量要少。

对于您所描述的任何类型的查询来说，花费超过几毫秒的软件都不值得用于此目的。