在Google AppEngine数据存储中存储有向图

Question

我需要在 google appengine 中存储一个大型动态无向图，最好的方法是什么？ 图表示必须能够支持快速拉出一组顶点（用于在页面上渲染）以及来自特定顶点的所有链接，以及跨图的寻路（尽管实际上并不需要最佳路径，只是一个相当大的路径）好）

我对这个问题的想法： 最明显的方法是拥有一个顶点模型和一个引用两个顶点的边缘模型，但这听起来似乎最终会为每个操作使用大量查询，我想知道是否有更好的方法（也许以某种方式将链接信息构建到每个顶点中）

Answer 1

这是最简单的方法：

class Vertex(db.Model):
  outedges = db.ListProperty(db.Key)
  # Other information about the vertex here

现在您可以在没有任何查询的情况下探索图形 - 只需在 1 个或多个键上调用 db.get 即可检索相关顶点：

# Get the first referenced vertex
vertex2 = db.get(vertex1.outedges[0])

# Get all referenced vertices
vertices = db.get(vertex1.outedges)

Answer 2

根据顶点/链接的数量，您可能只想使用列表而不是创建一堆新实体。 检查 Google IO 2009 视频后半部分描述的朋友图问题：http:// www.youtube.com/watch?v=AgaL6NGpkB8

如果您认为顶点数量足够多，您可以创建一个带有代表连接的列表的顶点模型。

Answer 3

考虑到您正在使用谷歌应用程序引擎，最好将信息存储在单独的表中：

一个用于顶点，一个用于来自顶点的链接（正如您已经说过的），另一个表中路径已预先计算。

如果您存储的信息是非规范化的，那么 GAE 效果最佳，因此您无需对其进行任何计算。