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

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

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

Ответ 1

Вот простейший способ:

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

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

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

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

Ответ 2

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

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

Ответ 3

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

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

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