我非常接近自己实现这一点，但在我这样做之前，我仍然想知道这个轮子是否已经被发明了:我需要的是一个库，它允许我表示DAG(有向无环图)，并允许查询直接或间接连接的节点，性能非常高。到目前为止，我已经比较了两种方法。
这个图将有几百万个节点，大约有1000 - 2000万个边。大多数节点只有一条或两条边，但几千个节点可能有10000条或更多的边。
用例将是:创建图形的努力并不重要，并且一旦创建了它就不需要更新，或者更新不需要很快。然而，查找长度为2(一个中间节点)的直接连接或特定间接连接应该非常快，并且边应该能够有标签(例如权重，计数等)。此外，内存占用应该小，查询应该是线程安全的。
我已经尝试过使用一些标准软件包，例如Neo4J或关系数据库，但是对于某些事情来说，两者都太慢了:当涉及到有很多边的节点(巨大的连接集)时，关系数据库在寻找间接关系方面非常缓慢。Neo4j可以更好地处理这种情况，但是查找直接连接的基本速度比关系数据库解决方案慢数千倍。在工作站上，关系数据库可以在不到5毫秒的时间内返回直接查询和许多间接查询的结果，但是某些间接查询可能需要一分钟的时间。在同一个系统上使用Neo4j，这些间接查询只需要几秒钟，但是直接查询都需要超过100毫秒的时间。我希望能够让我的直接查询低于1毫秒，最糟糕的间接查询低于1秒(平均)。
我认为，如果做得很聪明，这些都可以在内存中表示和执行，只需要几gb的堆空间，甚至对于更大的图，也会有一些策略通过智能缓存和如何将部分图持久化到磁盘来非常快速地完成这些事情。但是我找不到任何解决方案或库(最好是开源的)来提供这一点。我错过什么了吗?
具有数百万个节点和数千万条边的图在本世纪制造的任何台式计算机的内存中都是微不足道的。我建议使用fortran样式的
int ia[NVERT+1];
int ja[NEDGE];
中按尾顶点排序的边，在v处有尾的边索引为ia[v]至ia[v+1]-1, ja[e]列e边的首端。注意，这需要大约4(NVERT+NEDGE+1)字节的内存，这比"仅仅几gb"要少得多。
检查从一个顶点到另一个顶点是否存在一条边很简单;你看从第一个顶点出来的边。检查是否存在从一个顶点到另一个顶点的两条边路径也很简单;找到第一个顶点的所有邻居并检查它们是否有一条指向第二个顶点的出射边。最坏的情况是，扫描你所有的边缘。你自己这样做几乎肯定比连接到数据库所需的代码要少。
对于您所描述的任何一种类型的查询，都不值得使用超过几毫秒的软件。
我不确定它是否符合您的要求，因为我自己没有使用过这个库，但也许GUERY，一个由我在新西兰的前同事设计的框架值得一看:https://code.google.com/p/gueryframework/