Speichern eines gerichteten Graphen in Google appengine Datenspeicher

Question

Ich brauche eine große und dynamische ungerichteten Graphen in google appengine zu speichern, was ist der beste Weg, dies zu tun? Die Diagrammdarstellung muss in der Lage sein, schnell zu unterstützen eine Reihe von Eckpunkten herausziehen (für auf einer Seite dargestellt) und alle Links von einem bestimmten Vertex und Wegfindung in der Grafik (obwohl der optimale Weg nicht wirklich benötigt wird, nur ein ziemlich guter)

Meine Gedanken zum Thema: Der offensichtlichste Weg ist, ein Vertex-Modell zu haben, und ein Kantenmodell jedoch der Verweise zwei Ecken, das klingt wie es geht um eine Menge von Anfragen für jeden Betrieb, um am Ende mit, ich frage mich, ob es eine bessere Art und Weise ist ( vielleicht bauen die Link-Informationen in jedem Eckpunkt irgendwie)

Answer 1

Hier ist die einfachste Art und Weise:

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

Jetzt können Sie die Grafik ohne Abfragen überhaupt erforschen - einfach anrufen db.get auf 1 oder mehr Tasten die entsprechenden Eckpunkte abzurufen:

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

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

Answer 2

In Abhängigkeit von der Anzahl der Vertex / Links, die Sie nur verwenden Listen wollen könnten stattdessen eine Reihe von neuen Einheiten zu schaffen. Überprüfen Sie die Freunde Probleme in der zweiten Hälfte dieses Video von Google IO 2009 beschrieben Grafik: http: // www.youtube.com/watch?v=AgaL6NGpkB8

Wenn Sie die Anzahl der Vertex denken ist hoch genug, kann man einfach ein Vertex-Modell mit einer Liste erstellen, die die Verbindungen darstellen.

Answer 3

In Anbetracht Sie den Google App Engine verwenden wäre es am besten, wenn Sie die Informationen in separaten Tabellen gespeichert:

Eine für die Eckpunkte, eine für die Verbindungen von einem Scheitelpunkt (wie Sie bereits gesagt) und eine weitere ein, wo sich die Wege sind bereits vorberechnet.

GAE funktioniert am besten, wenn die Informationen, die Sie speichern ist denormalized, so dass Sie auf sie keine Berechnungen nicht zu tun haben.