Disclaimer: This page is so poorly written it may eat your computer. I do not apologize, and instead choose to find this explicitly acceptable. We should never have taught sand to think.
When we were doing cyber analysis using graphs, we ran into a lot of metrics that were kinda... bogus. It's easy to do maths on graphs, they're a math thing. But that doesn't always mean the number you get out of a formula is meaningful.
I've always defined graph theory as "a way to describe how things are related to each other." I feel like this isn't a frightfully novel definition, but that's probably good. The neat thing about mazes is that the cells of a maze have relationships: which cells you can move to. A maze is just an undirected graph.
This is handy, because since it's super easy to measure stuff about graphs, I'll bet we can figure out the difference between those maze generation algorithms using their graphs.
Let's see what maze generation looks like as a graph:
Looks like a filo virus to me, long strands, few forks. Let's see that other algorithm, the nucleation one:
Looks a lot more bunchy, with little branches, less clear long hallways. To extend the previous example, this feels more like streptococcus to my wife, the microbiologist. I don't think there's a science-y parallel conclusion about microbiology here, just talkin' vibes.
... but, as much as "data science by vibes" is popular, maybe we can measure something about this difference?
There are a ton of graph metrics people have invented. In my not-so-humble opinion, they are almost all nonsense unless you are using them in the extremely narrow circumstance they were invented for. For example, let's look at how connected the typical node is.
If we had a perfect circle, there'd be one edge per node. The graph would go in a loop like: edge, node, edge, node, etc. So we might imagine different shaped graphs would have different edge to node ratios. Let's see!
That's totally useless! But, why?
This is what I was getting at: you need to think about what metrics actually measure. The simplest maze is one long hallway, which give us just under a 1.0 edge to node ratio: it's the circle with one of the edges missing. If we cut the hallway and reattach it somewhere in the middle, we don't need to add or remove any nodes or edges. A maze where there is only one route between any two points will always have one less edge than nodes. Look, see, nodes - edges = 1:
The only time one of them isn't one is when there's a disjoint subgraph: the new worm isn't connected, so there's effectively a missing edge that would otherwise connect it.
This example feels dumb, because it is. The reason I bring it up is because it came up constantly during the Trace work. Everyone had their favorite graph theory metric about how this or that thing you could compute would tell you how secure the network was. They were all nonsense exactly like this, based on vibes, not data. Once we started applying real data to them, it was pretty obvious they had a hammer and this problem wasn't a nail.
So what's something real? We can tell "by vibes" that these mazes are different. How do we show it?
When we were first working on Trace, we were in a meeting with some Navy cyber warfare guys. We had this silly picture of a deeply connected network, with a little hand-drawn plot based entirely on vibes of how long it would take to figure out a way to get n nodes deep in, kinda like this:
I said "we don't really know what to measure" and their CO said "it sure looks like you do." So, we found a way to measure that, and it created an actually meaningful metric.
The vibes I get on these mazes are that the crystal maze has more hallways that are shorter. Well, that's hard to measure, but it also means it has more intersections, right? Even if the number of edges is constant, the number of nodes with extra edges (or fewer edges) should be different if there's a different number of intersections. Intersections means more neighbors you can go to, means more edges, means more dead ends at the end of those hallways.
Let's look at that, charting a histogram of number of nodes with n connections, from 0 neighbors to 4:
Oh snap! We can quantify the difference in these mazes.
To understand these charts, each number represents the number of nodes with that many neighbors, from zero to four. Zero neighbors means a node all by its lonesome off in space. One is a dead end, two is a hallway. Three or four means an intersection.
The crystal algorithm has way more dead ends and intersections, and those intersections often have far more options. Which, for the same number of total nodes in the maze, means we've gotta trade hallway length for'em. The worm mazes, in contrast, are often almost all hallway.
Vibes worked.
It's always been my contention that this is the trick to science. We all talk a good game about hypothesis testing, but you can't have a good hypothesis to test without vibes first.
We look at a cannonball falling off a tower and say "it looks like it doesn't matter how much it weighs, takes the same time." That's a vibe that we can turn into a hypothesis.
So I guess this is a post in defense of vibes. You can't just run with vibes, or you end up with nonsense metrics. But if you run data against your vibes to test'em out, you can get real useful metrics. Maybe that's obvious, but sometimes, it feels like it's not.
© 2025 Frank Lynam. All Rights Reserved.