Git fractals
Background
On Tuesday November 10, 2009, I was at Café Mankind in Amsterdam with my colleague Fernando Vezzosi, talking about Git. I don't remember exactly how it started, but soon enough we were trying to create Sierpiński triangles using Git.
Since then, I've tried to create different kinds of graphs using Git. The repository that is the result of my attempts is here: fractals.git.
Tools
These fractal graphs look really ugly in gitk, even with the --date-order option (which requires 1 second sleeps between commit creation to ensure we can find out the proper chronological order), so I decided to use GraphViz to try and show something better.
I quickly whiped up a small script (nicknamed git-dot) as part of my test script:
#!/bin/sh
# create a good looking graph with dot
echo "digraph G {"
git log --pretty=format:"%h %p" $* \
| perl -lane 'print qq("$F[0]";), map {qq("$_"->"$F[0]";)} @F[1..$#F]'
echo "}"
It takes the same options as git log (a rev-list) and turns the list of commits into a nice .dot graph source. I used the output of this script (or slight modifications of it) to produce the graphs shown in these pages.
Fractals created with Git
Sierpiński triangles ✘
Still sitting at our table, waiting for the dinner to arrive, I quickly managed to create a level 2 triangle by hand (6 connected commits). We spent the rest of the evening doodling on paper to try and find out a way to do this automatically.
Back at my hotel room, I continued to try, and began to write a program to create such triangles recursively. I didn't succeed that night, and have since then miserably failed at writing a program that would create a triangle of arbitrary depth.
The really hard part is creating the merge points. Check the page dedicated to the Siepiński triangle for more details about what I'm trying to achieve.
Cayley graph of F2 ✔
Disappointed with my failures at creating fractal triangles, I remembered another fractal that can be constructed in an iterative* way the Cayley graph of the free group on two generators (also called F2).
It took me less than an hour, during the night of Friday November 13 to correctly write the recursive function producing the expected commit graphs. That was a relief, compared to the pains I suffered trying to produce a Sierpiński triangle!
The result is the branches cayley-0, cayley-1, cayley-2, cayley-3, cayley-4, cayley-5, cayley-6, in the fractals.git repository. Check the page dedicated to the Cayley graph of F2 for the Graphviz graphs of various iterations and source code.
Sierpiński triangles ✔
As I expected when I started blogging about Git fractals, someone picked up the idea and beat me to it.
On November 20, Jan Krüger uploaded the script and a rendered graph of the history to http://gg.jk.gs/git/sierp/.
While this proves one shouldn't talk about a sekrit project
before it is completed, I am not disappointed at all. After all, Jan told me
You're right, it takes a bit of weird thinking to get it working
,
confirming that it was not just because of my stupidity that I haven't been
able to do it yet.
Here's a reduced version of Jan's graph, by the way:
Jan Krüger's Git Sierpiński graph
However, I'm relieved that the graph he came up with is completely different from the one I'm trying to produce. :-) This means there's room for several solutions, and I hope to update this page with my own, some time in the future.
Sierpiński triangles ✔
It seems Amsterdam is good for my brain (or motivation). On December 1st, again in the same hotel room, I decided to try again, this time using a linear technique.
The page dedicated to the Sierpiński triangles has all the details.