Мне нужно сохранить большой и динамический неориентированный граф в Google appengine, что лучший способ сделать это? Представление графа должно поддерживать быстрое вытягивание набора вершин (для рендеринга на странице) и всех ссылок из определенной вершины и отслеживания пути по графику (хотя оптимальный путь на самом деле не нужен, просто хороший)
Мои мысли по этому вопросу: Наиболее очевидным способом является наличие вершинной модели и краевой модели, которая ссылается на две вершины, однако, похоже, что она будет заканчиваться использованием огромного количества запросов для каждой операции, мне интересно, есть ли лучший способ ( возможно, каким-то образом создать информацию о связях в каждой вершине)
Вот простейший способ:
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)
В зависимости от количества вершин/ссылок вы можете просто использовать списки, а не создавать кучу новых объектов. Проверьте проблемы с друзьями, описанные во второй половине этого видео с Google IO 2009: http://www.youtube.com/watch?v=AgaL6NGpkB8
Если вы считаете, что число вершин достаточно велико, вы можете просто создать модель Vertex со списком, который представляет соединения.
Учитывая, что вы используете движок Google, было бы лучше, если бы вы сохранили информацию в отдельных таблицах:
Один для вершин, один для ссылок из вершины (как вы уже сказали), и еще один, где пути уже предварительно вычислены.
GAE лучше всего работает, если хранящаяся информация денормализуется, поэтому вам не нужно делать какие-либо вычисления на ней.