Stories
Slash Boxes
Comments
NOTE: use Perl; is on undef hiatus. You can read content, but you can't post it. More info will be forthcoming forthcomingly.

All the Perl that's Practical to Extract and Report

use Perl Log In

Log In

[ Create a new account ]

BooK (2612)

BooK
  {book} {at} {cpan.org}
http://paris.mongueurs.net/
Yahoo! ID: philippe_bruhat (Add User, Send Message)

Obfuscation [plover.com]. Pink [axis-of-aevil.net]. HTTP::Proxy [cpan.org]. YEF [yapceurope.org]. Fishnet [perl.org]. Kapow [cpan.org]. Cog's [perl.org] bitch [cpan.org]. Invitation [perl.org]. White [perl.org] Camel [perl.org]. Nuff' said.

Journal of BooK (2612)

Thursday November 19, 2009
07:43 PM

Git fractals

[ #39919 ]

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.

The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
 Full
 Abbreviated
 Hidden
More | Login | Reply
Loading... please wait.