I asked a question in twitter about graph theory the other day. Unsurprisingly, it was tricky to convey what I wanted to know in such a short span. So this explains what i was wondering in more depth.

I’ve got a problem involving graph layouts (think dot and graphviz) I want to write a GUI program that lets the user draw directed graphs interactively. That is, they start with a single node. Then, to modify that graph, there are five basic operations:

– add a node above: that is, a node _A_ becomes the graph _B_ -> _A_
– add a graph below: _A_ -> _B_
– add an edge between two nodes
– delete an edge
– delete a node, and all connecting edges

And what I’d like to know is; to keep the UI responsive, can I precalculate the positions of every possible graph ahead of time? When the user makes a change, I can refer to the precalculated positions and keep the UI experience really fast.

This depends on how many possible nodes there are. If I am only ever going to see, say, 500,000 possible layouts, it is possible to just spend a couple of days chugging through all the possible configurations and saving them in a database.

Without any more limits, this is impossible — there are an infinite number of graphs. But I think I can make reasonable guesses about the types of graph I’m likely to see in my app. For instance;

– the graph is always connected
– no two nodes have a duplicate edge
– the graph has no cycles
– Nodes generally won’t have more than about five incoming nodes and five outgoing nodes
– A graph probably won’t have more than about 100 nodes in it

So here’s how I formulated the problem;

Given a directed acyclic graph with _N_ nodes, where no node has more than _E_ total incoming and outgoing nodes, how many possible graphs are there?