Memorizzazione di un grafo orientato in google appengine datastore

Question

ho bisogno di memorizzare una grande e dinamica grafo non orientato in google AppEngine, qual è il modo migliore per farlo? La rappresentazione grafica deve essere in grado di supportare rapidamente tirando fuori una serie di vertici (per il rendering in una pagina) e tutti i collegamenti da un vertice specifico, e pathfinding attraverso il grafico (anche se il percorso ottimale non è realmente necessario, solo abbastanza buona)

I miei pensieri sul tema: Il modo più ovvio è quello di avere un modello di vertice, e un modello di bordo che fa riferimento a due vertici, tuttavia, che suona come sta andando a finire con un sacco di domande per ogni operazione, mi chiedo se c'è un modo migliore ( forse costruire le informazioni di collegamento in ciascun vertice in qualche modo)

Answer 1

Ecco il modo più semplice:

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

Ora è possibile esplorare il grafico senza alcuna query a tutti - basta chiamare db.get su 1 o più tasti per richiamare i vertici rilevanti:

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

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

Answer 2

A seconda del numero di vertex / link che si potrebbe desiderare di utilizzare solo liste invece di creare un gruppo di nuove entità. Controllare i problemi amici grafico descritti nella seconda metà di questo video da Google IO 2009: http: // www.youtube.com/watch?v=AgaL6NGpkB8

Se si pensa che il numero di vertice è abbastanza alto si può semplicemente creare un modello Vertex con una lista che rappresenta i collegamenti.

Answer 3

Considerando che si sta utilizzando il motore di applicazione Google che sarebbe stato meglio se si è memorizzato le informazioni in tabelle separate:

Uno per i vertici, uno per i collegamenti da un vertice (come già detto) e un ulteriore uno in cui i percorsi sono già pre-calcolate.

GAE funziona meglio se le informazioni che negozio è denormalizzato in modo da non avere a che fare calcoli su di esso.