Armazenando um grafo orientado em Google appengine armazenamento de dados

Question

Eu preciso armazenar uma grande e dinâmica grafo não direcionado no google appengine, qual é a melhor maneira de fazer isso? A representação gráfica deve ser capaz de suportar rapidamente puxando para fora um conjunto de vértices (para processar em uma página) e todas as ligações a partir de um vértice específico, e pathfinding através do gráfico (embora o caminho ideal não é realmente necessário, apenas um bastante bom)

Os meus pensamentos sobre o assunto: A maneira mais óbvia é ter um modelo de vértice, e um modelo de ponta que referências dois vértices, no entanto, que soa como ele vai acabar usando uma enorme quantidade de consultas para cada operação, eu estou querendo saber se existe uma maneira melhor ( talvez criar as informações link em cada vértice de alguma forma)

Answer 1

Aqui é a maneira mais simples:

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

Agora você pode explorar o gráfico sem qualquer dúvida em tudo - apenas chamar db.get em 1 ou mais teclas para recuperar os vértices relevantes:

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

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

Answer 2

Dependendo do número de vértice / links que você pode querer listas de uso apenas em vez de criar um monte de novas entidades. Verifique os amigos gráfico problemas descritos no segundo semestre deste vídeo do Google IO 2009: http: // www.youtube.com/watch?v=AgaL6NGpkB8

Se você acha que o número de vértice é alta o suficiente, você pode simplesmente criar um modelo Vertex com uma lista que representa as ligações.

Answer 3

Considerando que você está usando o Google App Engine que seria melhor se você armazenou as informações em tabelas separadas:

Um para os vértices, uma para os links de um vértice (como você já disse) e um adicional onde os caminhos já estão pré-computados.

GAE funciona melhor se as informações armazenadas é desnormalizada para que você não tem que fazer todos os cálculos sobre ele.