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

2018-06-25 05:54:22

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

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

这是最简单的方法：

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

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

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

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

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

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

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

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

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

链接地址: http://www.djcxy.com/p/70681.html