Ich habe mich gefragt, wie die ungerichteten Graphen (und damit die Traversierung von Graphen) in Google App Engine am besten implementiert werden könnten. Ich speichere gerade Kanten in der Datenbank als Liste, d. H.
%Vor%aber das ist notorisch ineffizient.
Ich kenne die gerichtete Grafikfrage als hier , aber ich finde, dass es für eine ungerichtete Graphik nicht so geeignet wäre.
Ich würde den Graphen als gerichteten Graphen speichern, wodurch Sie Abfragen effektiver nutzen können. Offensichtlich müssen Sie die Einschränkung haben, dass alle gerichteten Kanten eine Partner-Kante haben müssen, die in die entgegengesetzte Richtung geht.
%Vor%Sie können dann alle Kanten, die sich auf einen bestimmten Eckpunkt beziehen, mit einer einfachen Abfrage herausziehen:
%Vor%Schön und einfach, die Tatsache ausnutzend, dass Sie appengine verwenden, so dass Sie Indizierung viel Arbeit für Sie machen lassen können;)
Wenn Sie sicherstellen möchten, dass die gerichtete Abhängigkeit wahr bleibt, verwenden Sie offensichtlich eine Methode, um Kanten wie folgt zu erstellen:
%Vor%Bei der Adressierung von roffles geht es darum, alle Kanten zweimal zu speichern. Sie könnten so etwas wie folgt ausprobieren:
%Vor%Dieser Ansatz spart grundsätzlich Speicherplatz (jede Kante wird nur einmal gespeichert) auf Kosten von etwas höheren Abfragezeiten und viel schlechterem Code. Meiner Meinung nach ist das kein sehr guter Kompromiss, da Sie sich etwa 64 Byte pro Kante sparen.
Verzeiht mir, wenn dies etwas an dem Problem vermissen lässt, aber warum können Sie keine Kantenklasse haben, die maximal zwei Vertex-Referenzen in einer Liste enthält? Auf diese Weise können Sie eine Gleichheitsabfrage verwenden, um alle Kanten für einen bestimmten Eckpunkt abzurufen, und es ist keine Duplizierung erforderlich.
%Vor%Tags und Links database google-app-engine graph