init.
init:-cost(!A,!A,0), cost(!A,!B,100), cost(!A,!C,100), cost(!A,!D,100), e(!A,!B,2), e(!A,!C,1), e(!C,!B,3), e(!B,!D,1), e(!C,!D,3),
e(!B,!A,2), e(!C,!A,1), e(!B,!A,3), e(!D,!B,1), e(!D,!C,3).
cost(!S,!P,$c1), e(!P,!T,$c0), cost(!S,!T,$c2)
:-$c=$c0+$c1, $c<$c2 |
cost(!S,!P,$c1), e(!P,!T,$c0), cost(!S,!T,$c).
図5.7 HyperLMNtalで記述した最短経路問題
cost w1
cost w
e
w2
!T
!P
!S
図5.8 HyperLMNtalでエンコードした際のルールの適用条件
フで一意にエンコードすることができない. 図5.9の左のグラフもLMNtalでは2通りの グラフに変換してしまう可能性がある. 一意にLMNtalグラフへエンコードできないなら ば,複数のグラフに対応したルールを記述しなければならなくなり,必然的にルールの本数 が増加してしまう. よってこのエンコード方法ではLMNtalの特徴である簡潔な表現性が 生かされなくなる. 様々なグラフ問題に対応するためにも,本論文ではハイパーリンクを 使用したグラフのエンコード方法を提案する. エンコード方法のポイントとして, ノード とエッジをどちらもハイパーリンクを使用して表現することである.
a b
c
a b
c
a c
b
図5.9 単純なエンコード法
ノード専用のハイパーリンクはエッジの接続だけではなく, ノードの属性などをハイ パーリンクでまとめることができる. 本手法においてノードの情報は2引数のアトム n を使用して管理されており,第一引数にはノードに接続されているエッジをまとめたハイ パーリンク, 第二引数にはノードの属性をまとめたハイパーリンクに接続されている. ア トムnの第二引数の接続において,属性情報が1つしかない場合は直接リンクでその情報 に接続することができる. 今回の例題は各ノードに1つのフラグの情報のみを所持してい るグラフを扱うので,属性をまとめるハイパーリンクは使用していない.
同様にエッジ専用のハイパーリンクもノードの接続だけではなく,エッジの属性や重み などをまとめて表現することができる. ノードの情報がアトムnで管理されているのに対 して,エッジの情報はアトムeで管理されている.
アトムを表現するハイパーリンクとエッジを表現するハイパーリンクそれぞれの表現範 囲を区別するため,今回のエンコード方法ではポートアトム（2引数のアトムp）とよばれ るアトムが挿入されている. ポートアトムの第一引数にはアトム専用のハイパーリンクに, 第二引数にはリンク専用のハイパーリンクに接続される.
具体 的な 例 と し て 図 5.10 のグ ラ フ を LMNtal で エン コ ー ド した コ ー ド を図 5.11,
LMNtalグラフを図5.12に示す. 点線で書かれている曲線がハイパーリンクである. その
点線の曲線のうち,粗い点線はアトム専用のハイパーリンクであり,細かい点線はエッジ専 用のハイパーリンクである. このエンコード方法によって, 一般的なグラフをLMNtalグ ラフで一意に表現することができる.
1
0 2
3
図5.10 エンコードするグラフ
n(!H0,0),p(!H0,!H02),e(!H02),p(!H2,!H02), n(!H2,2),p(!H2,!H21),e(!H21),p(!H1,!H21), n(!H1,1),p(!H1,!H13),e(!H13),p(!H3,!H13), n(!H3,3),p(!H3,!H30),e(!H30),p(!H0,!H30).
図5.11 図5.10をLMNtalでエンコードしたときのプログラム
n 1 p
p n
0
e p
p e
n 2
n 3
p p e
p e
p
図5.12 図5.11のLMNtalグラフ
ここでエッジのエンコード方法をさらにシンプルに行うことを考える. その理由として,
ハイパーリンクによるエンコードはエッジがシンプルな構造をしていても複雑な構造とし
てLMNtalグラフにエンコードされてしまうからである. 例えば2つのグラフ「a(X), b(X)
」と「a(!H), b(!H)」は一見同じ型のグラフとして扱われそうだが, SLIM内では別のグラ
フとして処理される. このとき後者は前者より必要とする記憶領域が多くなってしまうの で, なるべくシンプルにエンコードする方法が大規模なグラフを扱う際に求められる. 図 5.10のグラフにおいてエッジに付随する情報は無いことから, エッジをハイパーリンクで 表現することはあまり好ましくない. したがって,このようなエッジはそのままLMNtalの リンクに置き換えることで,使用するメモリ量を最小限に抑えることができる. 他のメリッ トとして,ハイパーリンクをたどるマッチングよりもリンクをたどるマッチングの方が高 速に行える点が挙げられる. 図5.11 を改良したコードを図5.13, LMNtal グラフを図5.14 に示す. 以降特に記述しなければエッジのエンコードはリンクで行っているものとする.
n(!H0,0),p(!H0,L02),p(!H2,L02), n(!H2,2),p(!H2,L21),p(!H1,L21), n(!H1,1),p(!H1,L13),p(!H3,L13), n(!H3,3),p(!H3,L30),p(!H0,L30).
図5.13 エッジのエンコードをリンクにしたときのプログラム
n 1 p
p n
0
p
p
n 2
n 3
p p
p p
図5.14 図5.13のLMNtalグラフ
このエンコード手法は単純グラフの他に多重エッジや自己ループを含むグラフもエン コードすることが可能である.
5.2.2 グラフ構造探索問題概要
次にグラフ構造探索問題に関して説明する. この例題は扱うグラフにおいて, ある特徴 的な構造をした部分グラフを探索し,部分グラフに関わるノードのフラグを立てるのみの グラフ書換え操作を行う例題であり, 画像処理などの技術に応用することが可能である. ノードのフラグを立てる動作はLMNtalにおいて1本のルールによるグラフ書換えによっ て実現されている. 例えば,指定した数のエッジが接続されているノード,指定した属性を 所持するノード,ノードとエッジによって多角形を形成している部分グラフ構造,指定した ２点ノード間の部分グラフ構造などを探索することができる. (詳しくは付録A参照)
本論文ではグラフ中から三角形を形成しているノードとエッジを探索するルールを使 用して評価実験を行っている(第8章). 探索するグラフ構造を図5.15,書換えルールを図 5.16に示す. 今回エンコードしたLMNtalグラフではアトムnの第二引数にフラグを意味
するint型のunaryアトムを接続している. 初期段階はアトム0を代入しておき,ルールに
よってアトム1に変わる. フラグが立つという意味はnの第二引数をアトム1に書き換え ることと同義である.
図5.15 今回探索するグラフ構造
n(!H1,$x),p(!H1,B),p(!H2,B), n(!H2,$y),p(!H2,C),p(!H3,C),
n(!H3,$z),p(!H3,D),p(!H1,D):-$x\=1,$y\=1,$z\=1|
n(!H1,1),p(!H1,B),p(!H2,B), n(!H2,1),p(!H2,C),p(!H3,C), n(!H3,1),p(!H3,D),p(!H1,D).
図5.16 グラフ中の三角形を探索するルール
第 6 章
アトムの動的操作
本章ではSLIM内のアトムの配置を動的に操作する手法に関して述べる.