Сохранение ориентированного графа в хранилище данных Google Appengine

Question

Мне нужно сохранить большой динамический неориентированный граф в Google Appengine. Как лучше всего это сделать?Представление в виде графа должно поддерживать быстрое извлечение набора вершин (для рендеринга на странице) и всех ссылок из определенной вершины, а также поиск путей по графу (хотя оптимальный путь на самом деле не нужен, достаточно просто Неплохо)

Мои мысли на эту тему:Самый очевидный способ — это иметь модель вершин и модель ребер, которая ссылается на две вершины, однако похоже, что в конечном итоге для каждой операции будет использоваться очень много запросов. Мне интересно, есть ли лучший способ ( возможно, каким-то образом встроить информацию о ссылках в каждую вершину)

Answer 1

Вот самый простой способ:

class Vertex(db.Model):
  outedges = db.ListProperty(db.Key)
  # Other information about the vertex here

Теперь вы можете исследовать граф вообще без каких-либо запросов — просто вызовите db.get по одному или нескольким ключам, чтобы получить соответствующие вершины:

# Get the first referenced vertex
vertex2 = db.get(vertex1.outedges[0])

# Get all referenced vertices
vertices = db.get(vertex1.outedges)

Answer 2

В зависимости от количества вершин/ссылок вы можете просто использовать списки вместо создания множества новых объектов.Проверьте проблемы с графом друзей, описанные во второй половине этого видео из Google IO 2009: http://www.youtube.com/watch?v=AgaL6NGpkB8

Если вы считаете, что количество вершин достаточно велико, вы можете просто создать модель вершин со списком, представляющим соединения.

Answer 3

Учитывая, что вы используете движок приложений Google, было бы лучше, если бы вы сохранили информацию в отдельных таблицах:

Один для вершин, один для ссылок из вершины (как вы уже сказали) и дополнительный, где пути уже заранее рассчитаны.

GAE работает лучше всего, если хранимая вами информация денормализована, и вам не нужно выполнять с ней какие-либо вычисления.