Memorizzazione di un grafico diretto in google appengine datastore

Question

Ho bisogno di memorizzare un grafico grande e dinamico non orientato in google appengine, qual è il modo migliore per farlo? La rappresentazione grafica deve essere in grado di supportare rapidamente l'estrazione di un insieme di vertici (per il rendering su una pagina) e tutti i collegamenti da un vertice specifico e il path-finding attraverso il grafico (sebbene il percorso ottimale non sia realmente necessario, solo un abbastanza buono)

I miei pensieri sull'argomento: Il modo più ovvio è quello di avere un modello di vertice, e un modello di bordo che fa riferimento a due vertici, tuttavia sembra che finirà per usare un sacco di domande per ogni operazione, mi chiedo se c'è un modo migliore (magari costruire le informazioni di collegamento in ogni 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 domande 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

Considerando che stai usando il motore di app di google, sarebbe meglio se tu salvassi le informazioni in tabelle separate :

Uno per i vertici, uno per i collegamenti da un vertice (come già detto) e uno aggiuntivo dove i percorsi sono già precalcolati.

GAE funziona in modo ottimale se le informazioni archiviate vengono denormalizzate in modo da non dover eseguire calcoli.

Answer 3

A seconda del numero di vertici/collegamenti, è possibile utilizzare solo elenchi anziché creare un gruppo di nuove entità. Controlla i problemi del grafico degli amici descritti nella seconda metà di questo video da Google IO 2009: http://www.youtube.com/watch?v=AgaL6NGpkB8

Se pensi che il numero di vertici sia sufficientemente alto, puoi semplicemente creare un modello Vertex con un elenco che rappresenti le connessioni.