在GAE数据存储中存储有向加权完全图

Question

我有一个有向加权的完整图，里面有100个顶点。每个顶点代表一部电影，而边则表示两部电影之间的偏好关系。每当用户访问我的网站时，我会查询一组5个顶点来展示给用户（这组顶点经常变化）。我们可以把这些顶点叫做A、B、C、D、E。用户会对这些电影进行排序（也就是从最喜欢到最不喜欢进行排名）。比如，他可能会把它们排序为D、B、A、C、E。接下来，我需要更新这个图：

Graph[D][B] +=1
Graph[B][A] +=1
Graph[A][C] +=1
Graph[C][E] +=1

所以，Graph[V1][V2]这个计数最终表示有多少用户把（电影）V1排在（电影）V2的上面。当数据收集完成后，我可以进行各种离线图分析，比如找出图中的源和汇，以识别出最受欢迎和最不受欢迎的电影。

问题是：我该如何在数据存储中存储这个有向加权的完整图呢？显而易见的答案是：

class Vertex(db.Model):
    name = db.StringProperty()

class Edge(db.Model):
    better = db.ReferenceProperty(Vertex, collection_name = 'better_set')
    worse = db.ReferenceProperty(Vertex, collection_name = 'worse_set')
    count = db.IntegerProperty()

但我看到的问题是，我必须进行4个独立的复杂查询，类似于：

edge = Edge.all().filter('better =', vertex1).filter('worse =', vertex2).get()

然后我还需要在第五个查询中更新并放入新的边。

一种更高效（查询更少）但有点黑科技的实现方式是使用成对的列表来模拟字典：

class Vertex(db.Model):
    name = db.StringProperty()
    better_keys = db.ListProperty(db.Key)
    better_values = db.ListProperty(int)

所以，如果我想添加一个分数，表示A比B更好，我会这样做：

index = vertexA.index(vertexB.key())
vertexA.better_values[index] += 1

有没有更高效的方法来建模这个呢？

Answer 1

我通过对我在问题中提到的第一个设计做了一个小改动，解决了自己的问题。

我了解到一个叫做 key_name 的参数，它让我可以自己设置键名。所以每次我创建一个新的边时，我都会在构造函数中传入这个参数：

key_name = vertex1.name + ' > ' + vertex2.name

然后，我就不需要多次运行这个查询了：

edge = Edge.all().filter('better =', vertex1).filter('worse =', vertex2).get()

因为我知道怎么构造它们的键，所以我可以很轻松地获取这些边。使用 Key.from_path() 方法，我构建了一个指向边的键的列表。每个键都是通过以下方式获得的：

db.Key.from_path('Edge', vertex1.name + ' > ' + vertex2.name)

然后，我把这个键的列表传入，就可以一次性获取所有对象了。