Pascalの三角形 #10

Pasacalの三角形を介することなくSierpinskiの三角形を直接生成するなら、
二項係数そのものの値は不要であり、前段が偶数か奇数かさえ記録しておけば済む。

sierpinski_g.g

BEGIN {
  if (ARGC != 1) {
    print("usage: gvpr -fsierpinski_g.g -a <step>");
    exit(0);
  }

  int step = ARGV[0];
  graph_t g = graph("sierpinski_gasket", "U");
  node_t p[], q[];
  edge_t e;
  int i, j;

# user-defined function for creating new node
  node_t create(int k) {
    node_t n = node(g, sprintf("%d_%d", i, k));
    n.v = i == k || k == 0 ? 1 : (0 + p[k - 1].v) ^ p[k].v;
    if (n.v == 0) {
      n.style = "invis";
    } else {
      n.style = "filled";
      n.fillcolor = "black";
    }
    n.label = " ";
    return n;
  }

  for (i = 0; i <= step; i++) {
# create nodes in i-th step
    for (j = 0; j <= i; j++) q[j] = create(j);
# create edges from (i-1)-th step to i-th step
    for (j = 0; j < i; j++) {
      e = edge_sg(g, p[j], q[j], "");
      e.style = "invis";
      e = edge_sg(g, p[j], q[j + 1], "");
      e.style = "invis";
    }
# prepare for next step
    for (j = 0; j <= i; j++) p[j] = q[j];
  }
  write(g);
}

ノードにユーザ定義のv属性を付加する。
v属性は奇数なら1、偶数なら0を設定する。
次段のv属性は前段のv属性の排他的論理和で計算できる。
sierpinski_g.gはフィルタではないので-cオプションは不要である。

$ gvpr -fsierpinski_g.g -a100 | dot -Gsize=5 -Tpng -osierpinski_g.png

はオーバーフローを起こしたPascalの三角形に基づいたものと同じものになった。
このグラフの画像化も重い処理だが、
これまでのグラフの生成やフィルタリングと同様、DOTの生成自体は軽いものであり、
dotコマンドによる画像化のレイアウト処理がその重さのかなりの比重を占めている。