在Google App Engine数据存储中存储有向图

Question

我需要在Google Appengine上存储一个大型动态的无向图，最好的方法是什么？ 图形表示必须能够支持快速提取一组顶点（用于在页面上呈现）和从特定顶点开始的所有链接，并跨图形进行路径查找（虽然不需要最佳路径，但只需相当好的路径即可）。

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

- Martin

Answer 1

这里是最简单的方法：

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

现在，您可以无需任何查询就可以浏览图形 - 只需调用db.get并检索相关顶点上的1个或多个键：

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

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

- Nick Johnson

Answer 2

根据顶点/链接的数量，您可能只想使用列表而不是创建大量新实体。请查看Google IO 2009视频的第二部分中描述的朋友图问题：http://www.youtube.com/watch?v=AgaL6NGpkB8 如果您认为顶点数量足够高，可以创建一个具有表示连接的列表的顶点模型。

- Federico Builes

Answer 3

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

一个用于顶点，一个用于从顶点链接（如您已经提到的），以及额外的一个表，在其中路径已经预先计算。

GAE 最好使用您存储的信息是非规范化的，这样您就不必对其进行任何计算。

- B.E.

---

问题在于，图表是动态的，重新计算所有这些路径变化将花费我大量的配额。 - Martin