I'm wondering an amount be the easiest method to implement undirected graphs (and therefore graph traversal) on the internet Application Engine. I am presently storing edges within the database as a listing, i.e.
class Relation(db.Model): connect = db.ListProperty(str, required=True)
but this really is infamously inefficient.
I am conscious of the directed graph question as posed here, however i discover that it wouldn't be so appropriate to have an undirected graph.
I'd keep graph like a directed graph, which enables you to employ queries better. Clearly you must have the constraint that directed edges should have a joining up edge pointed in the other direction.
Class Vertex(db.Model): #Vertex specific stuff Class Edge(db.Model): Start = db.ReferenceProperty(Vertex) End = db.ReferenceProperty(Vertex)
After that you can take out all the edges relevant to some specific vertex having a simple 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
Nice simple, benefiting from the very fact you are using appengine so that you can let indexing perform a large amount of the meet your needs )
If you wish to make certain that directed constraint remains true, clearly use a means to create edges like so:
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()
Addressing roffles concerns about storing all of the edges two times, you could attempt something similar to this:
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.
This method essentially helps you save space for storage (every edge is just saved once) at the expense of slightly greater query occasions and far messier code. For me that isn't an excellent tradeoff, since you are saving yourself about 64 bytes storage per edge.
Forgive me if the misses something concerning the problem, why can't you possess an edge class that holds max two vertex refs in a listing? This could allow you to make use of an equality query to fetch all edges for any given vertex also it does not require duplication.
Class Edge(db.Model): Vertices = db.ListProperty(db.ReferenceProperty(Vertex)) ... edges = Edge.all() edges.filter("Vertices = ", foo)
You can keep vertex' finishes as a listing of secrets, but you should update two vertex to produce a new connection.
class Vertex(db.Model): ends= db.ListProperty(db.Key) # Other information about the vertex here
If you're not concerned about the writing time, this might be a great choice.