Cabling the Butterfly Network

The work described in this blog post follows from Bernasconi, Bodei, and Pagli's paper, "On formal descriptions for knitting recursive patterns" which can be found here on CiteSeer.

I've spent the past few days learning to knit an architecture known as the butterfly network. To construct a butterfly of dimension d, draw d rows of 2^d-1 nodes. Label each node with the pair (i, w) where i and w are binary numbers representing respectively the row and column of each node. Connect two nodes (i_a, w_a) and (i_b, w_b) if one of the following hold:

1. i_b = i_a + 1, and w_a differs from w_b in the i_ath bit. (cross edge)
2. i_b = i_a + 1, and w_a = w_b. (straight edge)

Bernasconi et al describe an algorithm to recursively generate a knitting grid for a butterfly of some given dimension. They ignore straight edges for "aesthetic" reasons; since I couldn't find a nice way of working vertical stripes alongside cables, I did the same.

My first effort was a butterfly of dimension three (the simplest non-trivial butterfly) to familiarize myself with the cabling; for my second attempt I worked a 4-butterfly, adding colours to distinguish the graph from the background. The yarn I used in this piece was rough, but with a better yarn I think this would look really nice.

The grid that I mentioned being recursively generated is actually a "meta chart"--a grid made up of dark and light circles which gives only an outline of the pattern. The point is to then replace these circles with specific stitches to create a pattern with a chosen look, texture, etc. For example, for a flat pattern, dark circles could become knit stitches and light circles, become purls, or each could be replaced by stitches worked in different colours. But for cabled patterns, because the direction of the twist of a cable is important, the meta chart for the butterfly cannot be converted into an actual pattern so easily; a human knitter could look at the chart and reason without difficulty about which way to twist the stitches represented by dark circles, but any automatic conversion procedure would need to be somewhat more complex.

The authors refer to such a procedure as (part of) a "knitting compiler". Unfortunately, I couldn't find the paper that they cite in reference to this, and searching online for knitting compilers turned up nothing useful. But the concept is pretty neat: an algorithm (code) to generate a pattern is specified; the code is then "compiled" into a human- (or even knitting-machine-) readable format (executable); and this "executable" is then "run" to produce a piece of fabric. I'm not yet sure how far this analogy goes towards being useful, but it's interesting to think about nonetheless.