在谷歌appengine数据存储中存储有向图

Question

我需要在谷歌appengine中存储一个大而动态的无向图，什么是最好的方式来做到这一点？ 图形表示必须能够支持快速提取一组顶点（用于在页面上呈现）以及来自特定顶点的所有链接，以及跨图形的路径查找（尽管最佳路径并非真正需要，只是一个相当好的一个）

我对这个问题的看法： 最明显的方法是有一个顶点模型和引用两个顶点的边缘模型，但是这听起来像最终会使用很多查询每一个操作，我想知道是否有更好的方法（可能建立的链接信息到每个顶点不知）

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) 

Answer 2

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

一个用于顶点，一个从顶点的链接（因为你已经说的）和一个额外的一个地方的路径已经预先计算。

GAE效果最好，如果您存储信息被规格化，所以你不必做任何计算。

Answer 3

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

如果您认为顶点数足够高，您可以使用表示连接的列表创建顶点模型。