Przechowywanie skierowanego wykresu w google appengine datastore

Question

Potrzebuję przechowywać duży i dynamiczny nieukierunkowany wykres w Google Appengine, jaki jest najlepszy sposób na zrobienie tego? Reprezentacja wykresu musi być w stanie obsługiwać szybkie wyciąganie zestawu wierzchołków (dla renderowania na stronie) i wszystkich linków z określonego wierzchołka oraz ścieżek na całym wykresie (chociaż optymalna ścieżka nie jest tak naprawdę potrzebna, wystarczy dość dobry)

Moje przemyślenia na ten temat: Najbardziej oczywistym sposobem jest posiadanie modelu wierzchołków i modelu krawędziowego, który odwołuje się do dwóch wierzchołków, jednak brzmi to tak, jakby skończył się przy użyciu ogromnej ilości zapytań. dla każdej operacji zastanawiam się, czy istnieje lepszy sposób (może jakoś budować informacje o każdym wierzchołku)

Answer 1

Oto najprostszy sposób:

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

Teraz można zbadać wykres bez żadnych zapytań w ogóle - po prostu zadzwoń db.get na 1 lub więcej kluczy do pobierania odpowiednich wierzchołków:

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

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

Answer 2

Biorąc pod uwagę, że korzystasz z wyszukiwarki Google, najlepiej byłoby przechowywać informacje w oddzielnych tabelach :

Jeden dla wierzchołków, drugi dla linków z wierzchołka (jak już wspomniano) i dodatkowy, gdzie ścieżki są już wstępnie obliczone.

GAE działa najlepiej, jeśli przechowywane informacje są denormalizowane, więc nie trzeba wykonywać żadnych obliczeń.

Answer 3

W zależności od liczby wierzchołków/linków, możesz chcieć użyć list, zamiast tworzyć kilka nowych elementów. Sprawdź problemy z wykresem znajomych opisane w drugiej części tego filmu z Google IO 2009: http://www.youtube.com/watch?v=AgaL6NGpkB8

Jeśli uważasz, że liczba wierzchołków jest wystarczająco wysoka, możesz po prostu utworzyć model wierzchołków z listą reprezentującą połączenia.