グラフ書き換え系の例

項の代わりにグラフを使うと、グラフ書き換え系になる。

Grrrシステム

以下の内容については、資料"Graph Drawing by Graph Rewriting"（/home/hattori/visual-prog/graph-rewriting-{1,2}.ps）を参照。

• 書き換え規則の左辺には、「あるサブグラフが存在しない」という条件が描ける。赤で描かれた部分と対象グラフがマッチすれば、その規則は適用できない。
• 書き換えの順序を制御するためにトリガー（他のノードと区別するために四角のノードで表す）を使う。
  • 書き換え規則の左辺には必ず一つのトリガーが含まれる。したがって、対象グラフの中のトリガーを含む部分が常に書き換えられる。
  • 同じトリガーを含む規則の間には優先順序があり、対象グラフと左辺のパターンがマッチする最初の規則が適用される。
  • 書き換え規則の右辺にはトリガーが何個あっても良い。したがって、対象グラフの中のトリガーは増えたり減ったりする。
  • 対象グラフの中に複数のトリガーがある場合は、後にできたトリガーが優先して書き換えの対象になる。したがって、新しくトリガーを作ることは、サブルーチンと同じような効果がある。
• 書き換え規則の左辺には、同じノードには一度しかマッチしないOnce Onlyノードを含めることができる。
  • 通常のグラフ書き換え系では、同じ規則が同じノードに何回も適用されないよう、適用済みであることを覚える補助ノードを付加しなければならないが、Once Onlyノードを使えばその必要がない。
  • 同じトリガーに関する規則に含まれるOnce Onlyノードには、各ノードが一度しかマッチしない。別のトリガーに関する規則には、もう一度マッチできる。

使用例

ウェブページに載っている例は、二分木を「見やすく」書き直すプログラムであり、基本的なアルゴリズムは次のようになっている。なお、論文に載っている例はもう少し複雑なものである。

1. 矢印をたどり、それぞれのノードが上から何階層目になっているかを付加する（元のノードと区別するために楕円形のノードを使う）。
2. 階層ごとにY座標を決定する。
3. 最下層のノードのX座標を順に決める。
4. 階層を上がりながら、子ノードの中央に来るように親ノードを動かす。
5. 作業用に付加したノードを消す。

図5.1[LayoutTreeに関する書き換え規則]は、全体の動きを決める書き換え規則である。

1. 最初に、書き換え対象となるグラフに、LayoutTreeというトリガーを付け加える。
2. doneYというノードは存在しないので、最初の規則が適用され、doneYというノードとLayoutYというトリガーが新しく出来る。
3. LayoutYに書き換え規則を適用し、Y座標を決定する。その処理が完了すると、LayoutYは消える。
4. doneYは存在するので、最初の規則は適用されない。doneXは存在しないので、二番目の規則が適用され、doneXというノードとLayoutXというトリガーが新しく出来る。
5. LayoutXに書き換え規則を適用し、X座標を決定する。その処理が完了すると、LayoutXは消える。
6. doneXもdoneYも存在するので、三番目の規則が適用され、LayoutTree, doneY, doneXはすべて消えて、DeleteLevelsというノードが新しくできる。
7. DeleteLevelsに書き換え規則を適用し、作業用に付加したノードを消す。その処理が完了するとDeleteLevelsも消える。