database - Google App Engine上的无向图和遍历

我想知道在Google App Engine上实现无向图(从而实现图遍历)的最佳方法是什么。我目前正在将边缘作为列表存储在数据库中，即

class Relation(db.Model):
    connect = db.ListProperty(str, required=True)

但这是众所周知的低效。

我知道所提出的有向图问题here，但我发现它不适用于无向图。

最佳答案

我会将图形存储为有向图，这使您可以更有效地使用查询。显然，您需要具有以下约束:所有有向边都必须具有沿相反方向延伸的伙伴边。

Class Vertex(db.Model):
   #Vertex specific stuff

Class Edge(db.Model):
   Start = db.ReferenceProperty(Vertex)
   End = db.ReferenceProperty(Vertex)

然后，您可以通过简单的查询拉出与特定顶点有关的所有边:

#getting all neighbours of a vertex called "foo"
Neighbours = Edge.all()
Neighbours.filter("Start = ", foo)
#neighbours now contains a set of all edges leading from foo

简洁明了，充分利用了您正在使用appengine的事实，因此您可以让索引为您完成很多工作；)

如果要确保有向约束仍然为真，显然可以使用一种方法来创建边，如下所示:

LinkVertices(A, B) #A and B are vertices
   edgeOne = Edge()
   edgeOne.Start = A
   edgeOne.End = B
   edgeOne.put()

   edgeTwo = Edge()
   edgeTwo.Start = B
   edgeTwo.End = A
   edgeTwo.put()

为了解决有关将所有边缘存储两次的担忧，您可以尝试执行以下操作:

Class Edge(db.Model):
    A = db.ReferenceProperty(Vertex)
    B = db.ReferenceProperty(Vertex)

#getting all neighbours of a vertex called "foo"
Neighbours = Edge.all()
Neighbours.filter("A = ", foo)
OtherNeighbours = Edge.all()
OtherNeighbours.filter("B = ", foo)
#these two queries now contains all edges leading from foo.

这种方法基本上可以节省您的存储空间(每个边缘仅存储一次)，但代价是查询时间略长，代码也更困惑。我认为这不是一个很好的折衷方案，因为您可以为每个边缘节省大约64字节的存储空间。

关于database - Google App Engine上的无向图和遍历，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/1971464/