Sierpiński triangle ✔

After giving up on the recursive approach, I still wanted to produce the Git graphs I had in mind when I started blogging about Git fractals. I thought that maybe a linear approach would work, given how hard it was to recursively create the triangles but stop one step before a triangle was finished to propagate nodes that needed to be merged with nodes from another recursively created triangle. Just like Pascal's triangle, the Sierpiński triangle is built line by line, using a simple condition to decide if a node will be created at the given position and with which parent nodes.

Given the following setup, trying to create node N, it only has at most three possible parent nodes:

 B → C    # row n-1 (fully built at the previous step)
 ↓ ↘ ↓
 A → N    # row n   (being built)

If N is not on the first column and B exists and has less that 3 parents, then A and B are potiential parents. If C exists and has less than 3 parents, it is also a potential parent.

Non-existing parents are removed from the list of potential parents, and a new node is created if it has at least one parent. Then we move on to the next node, until we have tried to create one more node than on the previous row.

This is repeated until the number of needed lines has been created. We must create 2^depth-1+1 rows, because the last node of the last line will be a descendant of all the nodes created before. Therefore a simple branch will point to it.

Presented below are the graphs (generated using GraphViz) of the various sierpinski-* branches of my fractals.git Git repository.

Step 0: 1 node

Step 1: 3 nodes

Step 2: 6 nodes

Step 3: 15 nodes

Step 4: 42 nodes

Step 5: 123 nodes

Step 6: 366 nodes

The graphs above were generated using git-dot on the branches. The Git graphs where created with a one second delay between commits, so that --date-order gives the nodes in the proper order to git-dot and GraphViz.