Gráficos sin dirección y recorrido en Google App Engine

Question

Me preguntaba cuál sería la mejor manera de implementar gráficos no dirigidos (y, por lo tanto, atravesar gráficos) en Google App Engine. Actualmente estoy almacenando bordes en la base de datos como una lista, es decir,

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

pero esto es notoriamente ineficiente.

Soy consciente de la pregunta del gráfico dirigido como se plantea here, pero me parece que no sería tan adecuado para un gráfico no dirigido.

Answer 1

Me gustaría almacenar el gráfico como un gráfico dirigido, lo que le permite utilizar las consultas de manera más efectiva. Obviamente, debe tener la restricción de que todos los bordes dirigidos deben tener un borde asociado en la dirección opuesta.

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

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

A continuación, puede sacar todas las aristas relacionadas con un vértice específico con una simple consulta:

#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 

bonito y sencillo, aprovechando el hecho de que está utilizando para que pueda appengine dejar que la indexación hacer una gran parte del trabajo para usted;)

Si desea asegurarse de que la restricción dirigida sigue siendo cierto, obviamente, utilizar un método para crear bordes de esta manera:

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() 

Dirigiéndose roffles preocupaciones acerca del almacenamiento de todos los bordes dos veces, usted podría intentar algo como esto:

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. 

Este enfoque básicamente ahorra espacio de almacenamiento (todas las aristas se almacena sólo una vez) a costa de consulta ligeramente más alto veces y mucho código messier. En mi opinión, esa no es una solución muy buena, ya que te estás ahorrando unos 64 bytes de almacenamiento por borde.

Answer 2

Puede almacenar los extremos de los vértices como una lista de teclas, pero deberá actualizar dos vértices para crear una nueva conexión.

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

Si no está preocupado por el tiempo de escritura, esta puede ser una buena solución.

Answer 3

Perdóneme si esto falla algo sobre el problema, pero ¿por qué no puede tener una clase edge que tenga un máximo de dos refs de vértice en una lista? Esto le permitiría usar una consulta de igualdad para buscar todos los bordes de un vértice dado y no requiere duplicación.

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

... 

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