在Google appengine数据存储中存储有向图 [英] Storing a directed graph in google appengine datastore

问题描述

我需要在google appengine中存储一个大而动态的无向图，最好的方法是什么？
图形表示必须能够支持快速拉出一组顶点（用于在页面上呈现）和来自特定顶点的所有链接以及跨图形的寻路（尽管最终路径不是真正需要的） ，只是一个很好的一个）

I need to store a large and dynamic undirected graph in google appengine, what's the best way to do this? The graph representation must be able to support rapidly pulling out a set of vertices (for rendering on a page) and all the links from a specific vertex, and pathfinding across the graph (although the optimal path isn't really needed, just a fairly good one)

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

My thoughts on the subject: The most obvious way is to have a vertex model, and an edge model which references two vertices, however that sounds like it's going to end up using an awful lot of queries for every operation, I'm wondering if there is a better way (maybe build the link information into each vertex somehow)

推荐答案

这是最简单的方法：

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

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

Now you can explore the graph without any queries at all - just call db.get on 1 or more keys to retrieve the relevant vertices:

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

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

这篇关于在Google appengine数据存储中存储有向图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！