Almacenar un gráfico dirigido en google appengine datastore

Question

Necesito almacenar un gráfico grande y dinámico no dirigido en google appengine, ¿cuál es la mejor manera de hacerlo? La representación gráfica debe ser capaz de soportar extraer rápidamente un conjunto de vértices (para renderizar en una página) y todos los enlaces desde un vértice específico, y la ruta a través del gráfico (aunque la ruta óptima no es realmente necesaria, solo una bastante bueno)

Mis pensamientos sobre el tema: La forma más obvia es tener un modelo de vértice y un modelo de borde que hace referencia a dos vértices, pero parece que va a terminar usando una gran cantidad de consultas para cada operación, me pregunto si hay una mejor manera (quizás de alguna manera construya la información del enlace en cada vértice)

Answer 1

Aquí es la forma más simple:

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

Ahora se puede explorar el gráfico sin alguna duda en absoluto - sólo llame 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

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

Uno para los vértices, uno para los enlaces de un vértice (como ya dijiste) y uno adicional donde las rutas ya están precalculadas.

GAE funciona mejor si la información que almacena se desnormaliza por lo que no tiene que hacer ningún cálculo al respecto.

Answer 3

Dependiendo del número de vértices/enlaces, es posible que desee usar listas en lugar de crear un grupo de entidades nuevas. Comprueba los problemas de gráficos de amigos descritos en la segunda mitad de este video de Google IO 2009: http://www.youtube.com/watch?v=AgaL6NGpkB8

Si crees que el número de vértices es lo suficientemente alto, puedes crear un modelo Vertex con una lista que represente las conexiones.