Last week (November 11) over dinner in Amsterdam, I talked with a colleague about Git as a tool for creating graphs. For some reason I started to think about a Sierpirński triangle, and we started trying to create such graphs with Git.
The basic shape is a triangle (in the UTF-8 drawing below, the arrows represent the parent → child relationship):
⋅
↓ ↘
⋅ → ⋅
It is quite easy to create by hand. I did it using git commit-tree,
using always the same tree object (the empty tree), as we only care
about the graph that represents commit lineage, not about the content.
The next step basically repeats the same shape, attached to the low-level nodes / commits of the previous graph:
⋅
↓ ↘
⋅ → ⋅
↓ ↘ ↓ ↘
⋅ → ⋅ → ⋅
I could create it in a couple of minutes, with a few more
git commit-tree commands.
After that, it stops being interesting to do by hand, and one wants to program it. My goal has been to create the following shape, and larger ones, using a Perl program.
A
⋅
↓ ↘
⋅ → ⋅
↓ ↘ ↓ ↘
B ⋅ → Ãâ → ⋅ C
↓ ↘ ↓ ↘
⋅ → ⋅ ⋅ → ⋅
↓ ↘ ↓ ↘ ↓ ↘ ↓ ↘
⋅ → Ãâ → Ãâ → Ãâ → ⋅
Until now, I've been trying several recursive approaches, and failed miserably each time. The big issue is the merge points, showed in the graph above using Ãâ.
In my recursive approaches, I usually first created the triangle (ABC), usually and then started again from B and then C. But the last merge of B (the Ãâ in the middle of the bottom line) can only be created once the vertical line starting from C has been started. I should probably keep state in some way, but haven't had much time to spend on this.
I also thought about using the mapping from Pascal's triangle (odd numbers as dots and even numbers as empty space, see both Wikipedia pages for details), but haven't actually tried it yet.
In other news, I've started to take care of my personal web site again.
It
hadn't been touched since 2002, so I gave
it a facelift.
Surprisingly enough, the only section yet is about
Git fractals.
;-)
Links to Git repositories, GraphViz images and more successful attempts
with other fractals are also available there.
...someone picked up the idea and beat me to it.
More details on:
two words...
rjbs on 2009-12-05T02:44:42
Git Triforce