Storing a directed graph in google appengine datastore

database-design, directed-graph, google-app-engine, path-finding

Solution

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)

Problem

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)

Original source