Неориентированные графы и обход на Google App Engine
Я задавался вопросом, каков будет лучший способ реализовать неориентированных графов (и следовательно обход графика) на Google App Engine. Я в настоящее время храню края в базе данных как список, т.е.
class Relation(db.Model):
connect = db.ListProperty(str, required=True)
но это известно неэффективно.
Я знаю о вопросе об ориентированном графе, как изложено здесь, но я нахожу, что это не так подошло бы для неориентированного графа.
3 ответа
Я бы сохранил график в виде направленного графика, что позволяет более эффективно использовать запросы. Очевидно, что необходимо иметь ограничение на то, что все направленные рёбра должны иметь партнерскую кромку, идущую в противоположном направлении.
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
Прекрасно и просто, воспользовавшись тем, что вы используете программу, чтобы позволить индексированию сделать за вас большую работу;)
Если вы хотите убедиться, что направленное ограничение остается верным, очевидно, используйте метод для создания рёбер, подобных этому:
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 байт места на краю.
.Можно хранить концы вершин как список ключей, но для создания нового соединения необходимо обновить две вершины.
class Vertex(db.Model):
ends= db.ListProperty(db.Key)
# Other information about the vertex here
Если вас не беспокоит время записи, это может быть хорошим решением.
.Простите, если это что-то пропустило в проблеме, но почему вы не можете иметь класс краев, который вмещает в список не более двух вершин? Это позволит вам использовать запрос равенства для получения всех рёбер для заданной вершины и не требует дублирования.
Class Edge(db.Model):
Vertices = db.ListProperty(db.ReferenceProperty(Vertex))
...
edges = Edge.all()
edges.filter("Vertices = ", foo)