Le stockage d'un graphe orienté dans Google appengine magasin de données

Question

J'ai besoin de stocker un grand et dynamique dans google graphe non orienté AppEngine, quelle est la meilleure façon de le faire? La représentation graphique doit être en mesure de soutenir tirant rapidement un ensemble de sommets (pour le rendu sur une page) et tous les liens d'un sommet spécifique, et pathfinding sur le graphique (bien que le chemin optimal est pas vraiment nécessaire, juste assez bon)

Mes réflexions sur le sujet: La façon la plus évidente est d'avoir un modèle de sommet, et un modèle de bord qui fait référence à deux sommets, mais qui sonne comme ça va finir par l'utilisation d'un très grand nombre de requêtes pour chaque opération, je me demande s'il y a une meilleure façon ( peut-être construire les informations de lien dans chaque sommet en quelque sorte)

Answer 1

Voici la façon la plus simple:

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

Maintenant, vous pouvez explorer le graphique sans requêtes du tout - il suffit d'appeler db.get sur 1 ou plusieurs clés pour récupérer les sommets concernés:

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

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

Answer 2

En fonction du nombre de sommets / liens que vous pourriez vouloir utiliser simplement des listes au lieu de créer un tas de nouvelles entités. http:: Vérifiez les problèmes de graphes d'amis décrits dans la seconde moitié de cette vidéo de Google IO 2009 // www.youtube.com/watch?v=AgaL6NGpkB8

Si vous pensez que le nombre de sommets est suffisamment élevé, vous pouvez simplement créer un modèle Vertex avec une liste qui représente les connexions.

Answer 3

Étant donné que vous utilisez le moteur Google App il serait préférable si vous l'enregistrez les informations dans des tableaux distincts:

L'un des sommets, l'un pour les liens d'un sommet (comme vous l'avez dit déjà) et un supplémentaire où les chemins sont déjà précalculées.

GAE fonctionne mieux si les informations que vous stockez est dénormaliser de sorte que vous ne devez pas faire des calculs sur elle.