Stockage d'un graphe orienté dans google appengine datastore

Question

Je dois stocker un graphe non orienté volumineux et dynamique dans google appengine, quelle est la meilleure façon de procéder? La représentation graphique doit pouvoir prendre en charge rapidement un ensemble de sommets (pour le rendu sur une page) et tous les liens d'un sommet spécifique, ainsi que la recherche de chemin à travers le graphe (bien que le chemin optimal ne soit pas vraiment nécessaire). 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 ça sonne comme si ça allait finir par utiliser énormément de requêtes Pour chaque opération, je me demande s'il existe un meilleur moyen (peut-être construire les informations de lien dans chaque sommet d'une manière ou d'une autre)

Answer 1

est ici 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

Étant donné que vous utilisez le moteur d'application google, il est préférable de stocker les informations dans des tableaux séparés :

Un pour les sommets, un pour les liens d'un sommet (comme vous l'avez déjà dit) et un autre où les chemins sont déjà précalculés.

GAE fonctionne mieux si les informations que vous stockez sont dénormalisées afin que vous n'ayez aucun calcul à effectuer.

Answer 3

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

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