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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!