Storing a directed graph in google appengine datastore

Question

I need to store a large and dynamic undirected graph in google appengine, what's the best way to do this? The graph representation must be able to support rapidly pulling out a set of vertices (for rendering on a page) and all the links from a specific vertex, and pathfinding across the graph (although the optimal path isn't really needed, just a fairly good one)

My thoughts on the subject: The most obvious way is to have a vertex model, and an edge model which references two vertices, however that sounds like it's going to end up using an awful lot of queries for every operation, I'm wondering if there is a better way (maybe build the link information into each vertex somehow)

Answer 1

Considering you're using the google app engine it would be best if you stored the information in separate tables:

One for the vertices, one for the links from a vertex (as you already said) and an additional one where the paths are already precomputed.

GAE works best if the information you store is denormalized so you don't have to do any calculations on it.

Answer 2

Here's the simplest way:

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

Now you can explore the graph without any queries at all - just call db.get on 1 or more keys to retrieve the relevant vertices:

# Get the first referenced vertex
vertex2 = db.get(vertex1.outedges[0])

# Get all referenced vertices
vertices = db.get(vertex1.outedges)

Answer 3

Depending on the number of vertex/links you might want to just use lists instead of creating a bunch of new entities. Check the friends graph problems described in the second half of this video from Google IO 2009: http://www.youtube.com/watch?v=AgaL6NGpkB8

If you think the number of vertex is high enough you can just create a Vertex model with a list that represents the connections.