Google App Engine上的无向图和遍历

Question

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

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

但这是非常低效的.

我知道这里提出的有向图问题,但我发现它不适合无向图.

Answer 1

我会将图形存储为有向图,这样可以更有效地使用查询.显然,您需要具有约束,即所有有向边必须具有朝向相反方向的伙伴边.

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()

解决roffles关于将所有边缘存储两次的担忧,你可以尝试这样的事情:

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字节的存储空间.