Memorizzazione di un grafo orientato in google appengine datastore
-
19-09-2019 - |
Domanda
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)
Soluzione
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)
Altri suggerimenti
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.
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.