Grafici e traiettoria indiretti su Google App Engine

Question

Mi chiedevo quale sarebbe il modo migliore per implementare grafici non orientati (e quindi attraversare graficamente) su Google App Engine. Sto attualmente memorizzando bordi nel database come un elenco, cioè

class Relation(db.Model): 
    connect = db.ListProperty(str, required=True) 

ma questo è notoriamente inefficiente.

Sono a conoscenza della domanda di grafico diretto come posata here, ma trovo che non sarebbe così adatto per un grafico non orientato.

Answer 1

Vorrei archiviare il grafico come grafico diretto, che consente di utilizzare le query in modo più efficace. Ovviamente è necessario avere il vincolo che tutti i bordi diretti devono avere un vantaggio di partenariato andando nella direzione opposta.

Class Vertex(db.Model): 
    #Vertex specific stuff 

Class Edge(db.Model): 
    Start = db.ReferenceProperty(Vertex) 
    End = db.ReferenceProperty(Vertex) 

È quindi possibile tirare fuori tutti i bordi relativi a un vertice specifico con una semplice query:

#getting all neighbours of a vertex called "foo" 
Neighbours = Edge.all() 
Neighbours.filter("Start = ", foo) 
#neighbours now contains a set of all edges leading from foo 

Nizza e semplice, approfittando del fatto che si sta utilizzando in modo da poter AppEngine lasciare che l'indicizzazione fare un sacco di lavoro per voi;)

Se si vuole fare in modo che il vincolo diretto resta vero, ovviamente, utilizzare un metodo per creare bordi in questo modo:

LinkVertices(A, B) #A and B are vertices 
    edgeOne = Edge() 
    edgeOne.Start = A 
    edgeOne.End = B 
    edgeOne.put() 

    edgeTwo = Edge() 
    edgeTwo.Start = B 
    edgeTwo.End = A 
    edgeTwo.put() 

Affrontare roffles preoccupazioni per la memorizzazione di tutti i bordi per due volte, si potrebbe provare qualcosa di simile:

Class Edge(db.Model): 
    A = db.ReferenceProperty(Vertex) 
    B = db.ReferenceProperty(Vertex) 

#getting all neighbours of a vertex called "foo" 
Neighbours = Edge.all() 
Neighbours.filter("A = ", foo) 
OtherNeighbours = Edge.all() 
OtherNeighbours.filter("B = ", foo) 
#these two queries now contains all edges leading from foo. 

Questo approccio consente di risparmiare in pratica si spazio di archiviazione (ogni bordo è memorizzata solo una volta) al costo di interrogazione leggermente superiore tempi e un gran numero di messer. Secondo me non è un compromesso molto buono, dal momento che ti stai risparmiando circa 64 byte di storage per edge.

Answer 2

È possibile memorizzare le estremità del vertice come un elenco di chiavi, ma è necessario aggiornare due vertici per creare una nuova connessione.

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

Se non sei preoccupato per il tempo di scrittura, questa potrebbe essere una buona soluzione.

Answer 3

Perdonami se questo manca qualcosa del problema, ma perché non puoi avere una classe edge che contiene un massimo di due ref di vertice in una lista? Ciò consentirebbe di utilizzare una query di uguaglianza per recuperare tutti i bordi per un dato vertice e non richiede la duplicazione.

Class Edge(db.Model): 
    Vertices = db.ListProperty(db.ReferenceProperty(Vertex)) 

... 

edges = Edge.all() 
edges.filter("Vertices = ", foo)