• Home

The full title was "Generating graphs uniformly using a context-free hypergraph grammar"

The aim was to find some way of generating graph networks uniformly. This has applications in testability, for example could you could generate graphs that represent a syntax tree for a programming language. Another fun application is for game development, where a designer creates the rules for a graph that represent a procedurally generated dungeon.

The naive approach of generating graph networks would be to define some grammar and randomly pick substitutions, but this wouldn't be uniform and you'd get some productions of the grammar that would almost never occur.

A grammar is a series of replacement rules where you can start with a simple edge/vertex and keep applying replacement rules to build a larger network.

A context-free grammar is a grammar where the replacement rule applies to a individual elements like vertices or edges without regard for their position relative to other elements. This constraint gives you invariance that can be used prove things about the grammar later.

"Uniformly" here means that every possible terminal graph had the exact same chance of being produced. This is useful because if you are generating graphs randomly then you wouldn't want some graphs being produced most of the time, and other being produced almost never.

My insight was two things:

1. I found a paper that described a way to uniformly generate strings from a context-free string grammar. I would need to apply this to graph grammars. But context-free graph grammars are not that useful since you can't use them to generate much variety of graphs.
2. A hypergraph is a graph where edges can connect to any number of vertices. I could raise the regular graph grammar into a hypergraph grammar since all regular graphs are hypergraphs. Hypergraph context-free grammars are more useful and can generate far more variety of graphs. You can also ensure that the edges in the final graph always had two vertices, so the output graph was a regular graph. Therefore the hypergraph was only used during the rule generation.

Combining these two things I had a system where you could generate a large variety of graphs, and it was uniform so every graph had the exact same chance of being produced.

I also made a GUI editor for the hypergraph rule editor since there wasn't existing software to edit+visualise hypergraphs or grammars. It used a force-directed graph network algorithm to layout the nodes in real time. I ended up learning Scala for this project since a lot of the math was very functional in nature.