Almacenamiento de un grafo dirigido en Google almacén de datos appengine

Question

necesito para almacenar un grafo no dirigido grande y dinámico en google appengine, ¿cuál es la mejor manera de hacer esto? La representación gráfica debe ser capaz de soportar rápidamente sacando un conjunto de vértices (para la representación de una página) y todos los enlaces desde un vértice específica, y la búsqueda de caminos a través del gráfico (aunque el camino óptimo no es realmente necesario, a bastante buena)

Mis pensamientos sobre el tema: La manera más obvia es tener un modelo de vértice, y un modelo de borde que hace referencia a dos vértices, sin embargo, que suena como que va a terminar con un montón de consultas para cada operación, me pregunto si hay una manera mejor ( tal vez la construcción de la información de enlace en cada vértice de alguna manera)

Answer 1

Esta es la forma más sencilla:

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

Ahora usted puede explorar el gráfico sin ningún tipo de consultas a todos - acaba de llamar db.get en 1 o más claves para recuperar los vértices correspondientes:

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

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

Answer 2

En función del número de vértices / enlaces es posible que desee sólo tiene que utilizar listas en lugar de crear un montón de nuevas entidades. Compruebe los problemas de los amigos del gráfico que se describen en la segunda mitad de este video de Google IO 2009: http: // www.youtube.com/watch?v=AgaL6NGpkB8

Si cree que el número de vértice es lo suficientemente alto como usted puede crear un modelo Vertex con una lista que representa las conexiones.

Answer 3

Teniendo en cuenta que está utilizando el motor de aplicación de Google que sería mejor si se almacena la información en tablas separadas:

Uno para los vértices, uno para los enlaces de un vértice (como ya se ha dicho) y un adicional de uno donde los caminos ya están precalculados.

GAE funciona mejor si la información que se almacena desnormalizado por lo que no tiene que hacer ningún cálculo sobre el mismo.