Je me demandais quelle serait la meilleure façon de mettre en œuvre des graphiques non dirigés (et donc une traversée graphique) sur Google App Moteur. Je stocke actuellement des arêtes dans la base de données comme liste, c'est-à-dire mais ceci est notoirement inefficace. Je suis au courant de la question de graphique dirigée comme posée < un href = "https://stackoverflow.com/questions/1187414/storing-a-directed-graph-in-google-appengine-DaTaTore"> ici , mais je trouve que ce ne serait pas aussi apte à un graphique non dirigé.
3 Réponses :
Vous pouvez stocker le sommet 'se termine comme une liste des touches, mais vous devez mettre à jour deux sommets pour créer une nouvelle connexion.
class Vertex(db.Model):
ends= db.ListProperty(db.Key)
# Other information about the vertex here
Je stockerais le graphique en tant que graphique dirigé, ce qui vous permettrait d'utiliser plus efficacement les requêtes. Évidemment, vous devez avoir la contrainte que tous les bords dirigés doivent avoir un avantage de partenariat dans la direction opposée. Vous pouvez ensuite retirer tous les bords relatives à un sommet spécifique avec un simple Query: p> Class Edge(db.Model):
A = db.ReferenceProperty(Vertex)
B = db.ReferenceProperty(Vertex)
#getting all neighbours of a vertex called "foo"
Neighbours = Edge.all()
Neighbours.filter("A = ", foo)
OtherNeighbours = Edge.all()
OtherNeighbours.filter("B = ", foo)
#these two queries now contains all edges leading from foo.
Oh j'aime ça, même si j'aimerais vraiment une implémentation indemne de graphique :)
Vous pouvez supprimer des commentaires lorsque vous avez une légère explosion du cerveau;) Cela répond-il à vos exigences alors?
Je suis préoccupé par le fait que je vais avoir besoin de deux bords par lien, bien que 500 bords non dirigés soient transformés en 1000 dirigés. Cela ne peut pas être bon pour le moteur App.
Les bords sont assez légers en termes d'espace de stockage. Je ne m'inquiéterais pas pour ça - c'est le temps de processeur que vous devriez être plus inquiet à mon avis.
Merci pour cela. Qu'en est-il des ancêtres - suppose que les bords devraient avoir des parents. Soit un edgeded edges_root ou que le nœud est parent à son bord? bordeone.start = A; bordone.parent = a; edgetwo.start = b; edgetwo = b; Ou ai-je tort? Je suppose que vous n'avez pas vraiment besoin du noeud de démarrage car il est pareil que le parent et n'est jamais changé
Par ancêtres, je suppose que vous voulez dire le sommet d'origine d'un bord? Si tel est le cas, je pense que vous avez répondu à votre propre question - utilisez simplement le noeud de démarrage.
Pardonnez-moi si cela manque quelque chose sur le problème, mais pourquoi ne pouvez-vous pas avoir une classe de bord qui contient deux Refs de Vertex Max dans une liste? Cela vous permettrait d'utiliser une requête d'égalité pour aller chercher tous les bords pour un sommet donné et ne nécessite pas de duplication.
Class Edge(db.Model):
Vertices = db.ListProperty(db.ReferenceProperty(Vertex))
...
edges = Edge.all()
edges.filter("Vertices = ", foo)
S'il vous plaît expliquer pourquoi vous pensez qu'il est inefficace. Aussi s'il vous plaît éclairer - fait g.a. Soutien des procédures stockées?
Je dois effectuer beaucoup de questions pour obtenir tous les liens avec le nœud - aussi je suis à peu près sûr que l'apps d'applications ne prend pas en charge les procédures stockées.
Pourquoi ne pas stocker votre AG comme une seule chaîne XML et faire tout le déballage et la traversée dans un python régulier?
Le problème est que je m'attends à ce que ce graphique soit énorme et il dépasserait probablement la limite de mémoire.
Je dois admettre que je ne suis pas un utilisateur de Google App. Voici un exemple: en.wikipedia.org/wiki/graphml Maintenant, pourriez-vous élaborer plus : Quelle est la taille du graphique global de GB et quelles données y est-elle et pourquoi avez-vous été réglé sur le moteur d'application Google? Il est possible que vous souhaitiez utiliser autre chose. En outre, quel est le nombre typique / maximum d'arêtes sortant d'un sommet unique? Et ... qu'est-ce que le travertisseur graphique accomplit pour vous? Essayez-vous de mettre Google hors de l'entreprise à l'aide du moteur d'application Google?
Je pense que Google App Moteur est fiable et évolutif qui convient à mon objectif.
Je pense que GAE fonctionnerait bien pour cela, et vous pourriez probablement trouver une solution de graphique non dirigée. Pourriez-vous nous donner une liste de quelles fonctions vous effectueriez probablement le plus?