ライフゲーム #2

Graphviz

現世代のグラフを入力とし次世代のグラフを出力とするフィルタをgvprプログラムで書いてみる。

next_gen.g
BEGIN {
  int count_alive(node_t n) {
    int count = 0;
    edge_t e;
    for (e = fstedge(n); e != NULL; e = nxtedge(e, n)) {
      if ((e.tail == n && e.head.alive) || (e.head == n && e.tail.alive)) {
        count++;
      }
    }
    return count;
  }
}

N [alive] {
  int c = count_alive($);
  if (c == 2 || c == 3) {
    $.next_alive = 1;
  } else {
    $.next_alive = "";
  }
}

N [! alive] {
  if (count_alive($) == 3) {
    $.next_alive = 1;
  } else {
    $.next_alive = "";
  }
}

END_G {
  node_t n;
  for (n = fstnode($); n != NULL; n = nxtnode(n)) {
    if (n.next_alive == 1) {
      n.alive = 1;
      n.next_alive = "";
    } else {
      n.alive = "";
    }
  }
}

ノードの真偽値属性の名前をaliveとする無向グラフで一つの世代を表す。
非零の値が設定されたalive属性を持つノードを真値ノード、
alive属性を持たないノードを偽値ノードとする。
状態遷移の規則はオリジナルの規則に基づく。
各ノードの次世代の属性は一時的な属性next_aliveとしてマークしておき、
最後にまとめてnext_alive属性付きのノードにalive属性を付け、
next_alive属性の付いていないノードのalive属性は消去する。
また、next_alive属性は一時的なものなので、付いている場合は消す。
次のようなテストグラフを用意して、これが機能するかテストしてみる。

test.gv
graph g00 {
  nw -- c -- se;
  n  -- c -- s;
  ne -- c -- sw;
  e  -- c -- w;
}
graph g01 {
  nw [alive=1];
  nw -- c -- se;
  n  -- c -- s;
  ne -- c -- sw;
  e  -- c -- w;
}
graph g02 {
  nw [alive=1];
  n  [alive=1];
  nw -- c -- se;
  n  -- c -- s;
  ne -- c -- sw;
  e  -- c -- w;
}
...snip
graph g08 {
  nw [alive=1];
  n  [alive=1];
  ne [alive=1];
  w  [alive=1];
  e  [alive=1];
  sw [alive=1];
  s  [alive=1];
  se [alive=1];
  nw -- c -- se;
  n  -- c -- s;
  ne -- c -- sw;
  e  -- c -- w;
}
graph g10 {
  c  [alive=1];
  nw -- c -- se;
  n  -- c -- s;
  ne -- c -- sw;
  e  -- c -- w;
}
graph g11 {
  c  [alive=1];
  nw [alive=1];
  nw -- c -- se;
  n  -- c -- s;
  ne -- c -- sw;
  e  -- c -- w;
}
...snip
graph g18 {
  c  [alive=1];
  nw [alive=1];
  n  [alive=1];
  ne [alive=1];
  w  [alive=1];
  e  [alive=1];
  sw [alive=1];
  s  [alive=1];
  se [alive=1];
  nw -- c -- se;
  n  -- c -- s;
  ne -- c -- sw;
  e  -- c -- w;
}

各グラフはノードcに8個の隣接ノードが接続している。

グラフg0mはm個のalive属性付きノードがalive属性の付いていないノードcに隣接している。
グラフg1mはm個のalive属性付きノードがalive属性の付いているノードcに隣接している。
これをnext_gen.gでフィルタし、その出力のうち、ノードcにalive属性が付いているグラフ名を表示する。
bash上で実行する*1なら、

$ gvpr -cq -f next_gen.g test.gv | gvpr -q "N[name=='c' && alive]{print(\$G);}"
g03
g12
g13

となり、ノードcは規則通りに次世代の状態へ遷移しているようだ。

g03 : aliveでないノードの隣接ノード3個がaliveならfalseからtrueへ遷移する
g12 : aliveであるノードの隣接ノードのうちaliveが2個でも3個でもなければtrueからfalseへ遷移する
g13 : 同上

本当は相互に影響しあうようなテストデータでもってテストしないといけないが、
もっと実戦的なグラフで使用していっても駄目駄目かどうかは分かるだろう。
gvprの-qオプションはalive属性を持つノードが全くないグラフを与えられても警告しないようにするため。
next_gen.gを使用するに当たっては、フィルタ操作した入力グラフを出力するため-cオプションを付ける。

*1:コマンドプロンプトなら\$Gの\は不要