我想知道在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()
解决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字节的存储空间.
