明瞭オートマトンと近傍とイプシロンパス

ダイクストラ波動を走らせるためには、グラフにサイクルがあってはダメ。正確に言えばあってもいいのだけど（つうか、ないと使い物にならない）、サイクルの原因が一箇所に集中しているようなグラフ。背景は、トレース付き圏の正規形だが、明瞭性とマッチするかどうかが今の問題。

それはともかく、明瞭オートマトンにおけるスター近傍は次の概念にしようかな。まずはout側の近傍の定義

• コスト1以下で中心から到達できるノードの集合と、中心から各ノードに至るパスを構成する辺からなる部分グラフ

in側の近傍は

• コスト1以下で中心へと到達できるノードの集合と、ノードから中心に至るパスを構成する辺からなる部分グラフ

「コストが1」じゃなくて、コスト1以下が非常に重要。これにより、有用なイプシロン辺を排除せずに済む。

pをノードだとして、Out(p)とIn(p)を次のように定義できる。

• out側の近傍の辺ラブベルを合併した集合 = Out(p)
• in側の近傍の辺ラブベルを合併した集合 = In(p)

Out(p) = 空 と out(p) = 0 が違うところがミソ。境界で止まるイプシロンパスや、境界から出るイプシロンパスは、Out, In に関係しない。

サイクルの入り口にはイプシロンパスが入っても大丈夫みたい。同じく、サイクル出口からイプシロンパスが複数出てもいいのかな？ イプシロンパスが分岐してツリーになるのは許せるけど、イプシロンサイクルはやっぱりダメだな。「イプシロンサイクルを持たない」は死守。

まてよ、イプシロンチェーンとイプシロンツリーの中間に、境界でないない到達点がたかだか1個って条件があるな。これなら、事実上はチェーンのように扱える。境界はスタートノード、サイクル入り口、サイクル出口、ゴールノード。