圏論番外：有向グラフのパスの圏（実装付き） - 檜山正幸のキマイラ飼育記 (はてなBlog)

一般的に、有向グラフがあったとき、そのグラフの「パスの圏」とか「自由生成された圏」と呼ばれる圏が作れます。
グラフから自由生成された圏はいろんな場面で使う重要な概念です。

と書いたので、有向グラフから作られるパスの圏を紹介しておきます。よく使いますし、面白いし。

有向グラフ

まずは有向グラフを定義しておきます。頂点（vertex, node）の集合Vと、辺（edge, arc, arrow）の集合Eがあって、2つの写像 src:E→V、trg:E→Vがあると、これらの組み合わせ (V, E, src, trg) を有向グラフと呼びます。srcはsourceのことで、矢印（有向な辺）の根本を意味し、trgはtarget、矢印の先端を意味します。圏の場合と同様に、「頂点や辺がなんであるか？」なんてのは一切気にしません。なんだっていいのです。

src、trgは、圏のdom, codと同じものです。別な言い方をすると、圏は有向グラフに、恒等と結合（合成）の概念を付け加えたものです。有向グラフの場合も、dom, codという記号を使ってもいいのですが、混乱を招かないように一応区別しておきました。

以下で単に「グラフ」と言ったら、それは有向グラフのことです。

パスの圏

さて、グラフ(V, E, src, trg)があると、それから圏が作れます。これから作る圏をCとして、圏Cの“対象の集合”を|C|、圏Cの“射の集合”をC（圏全体と同じ記号）で表します。

まず、|C| = V 、つまり、圏Cの対象とは与えられたグラフの頂点のことです。次にCの射を定義しましょう。Cの射とは、長さが2以上のリスト（シーケンス、ベクトル、配列、なんとでも好きに呼んでください）なんですが、次の形のものを考えます。

長さが2のときは、A, B∈V に対して [A, B] の形をしている。
長さが3のときは、A, B∈V と e∈E に対して [A, e, B] の形をしている。
長さが4のときは、A, B∈V と e, f∈E に対して [A, e, f, B] の形をしている。
長さが(2 + n)のときは、A, B∈V と e₁, ..., e_n∈E に対して [A, e₁, ..., e_n, B] の形をしている。

ようするに、リストの最初と最後はグラフの頂点、中間にはグラフの辺が並んでいるってことです。

いま定義した形のリストに、さらに次の条件を課します。

長さが2のときは、A = B 。
長さが3のときは、src(f) = A, trg(f) = B 。
長さが4のときは、src(f) = A, trg(f) = src(g), trg(g) = B 。
長さが(2 + n)のときは、src(e₁) = A, trg(e₁) = src(e₂), ..., trg(e_n) = B

図形的に考えると、[A, e₁, ..., e_n, B] は、AからBに至るパス（経路）です。中間に並んでいる e₁, ..., e_n は途中で通るn本の辺を順番に並べたものです。[A, A] は「まったく移動しないパス」を表します。[A, f, B] は辺fだけを通るパスですね*1。

C = 圏Cの射の集合 = パスの全体

としてCを定義します。

圏を構成する残りの部分を定義するのは簡単：

dom([A, e₁, ..., e_n, B]) = A
cod([A, e₁, ..., e_n, B]) = B
id(A) = [A, A]
[A, e₁, ..., e_n, B];[B, f₁, ..., f_m, C] = [A, e₁, ..., e_n, f₁, ..., f_m, C]

n = 0 の特殊ケースも容易に想像できるでしょ。これらが圏の法則を満たすことを確認してください。圏の定義を復習するちょうどいい練習問題です。

実装例

JavaScriptによる実装も作りました。ソースコードはこちら→http://d.hatena.ne.jp/m-hiyama-memo/20090525/1243206277

今回のパスの圏は、なにか特定の圏をひとつ実装するわけではありません。与えられたグラフから圏を構成する、その“構成法”をプログラミングするわけです。そこで、グラフは次のインターフェースを持つオブジェクトだと約束します。JavaScriptは、言語機能としてインターフェースを持たないのでコンベンションとしてのインターフェースです。

/*
 * グラフ（有向グラフ）のインターフェース
 *
 * isVertex(x) -- xはグラフの頂点である
 * isEdge(x) -- xはグラフの辺である
 * eqVertex(a, b) -- 頂点aと頂点bは等しい
 * eqEdge(e, f) -- 辺eと辺fは等しい
 * src(e) -- 辺eの根本の頂点
 * trg(e) -- 辺eの行き先の頂点
 * vertex(...) -- 頂点のコンストラクタ
 * edge(...) -- 辺のコンストラクタ // 今回、PathCat側では使わない
 */

これらのインターフェースを備えたオブジェクトGraphが与えられれば、次のようにして圏を表すオブジェクトCatを構成できます。

 var Cat = new PathCat(Graph);

ちなみに、圏は次のインターフェースを持つオブジェクトで表しています。

/*
 * 圏のインターフェース
 *
 * isObjct(x) -- xは圏の対象である
 * isMorphism(x) -- xは圏の射である
 * eqObj(a, b) -- 対象aと対象bは等しい
 * eqMor(f, g) -- 射fと射gは等しい
 * dom(f) -- 射fの域
 * cod(f) -- 射fの余域
 * id(a) -- 対象aの恒等射
 * composable(f, g) -- 射fと射gは結合（合成）可能である
 * compose(f, g) -- 射fと射gの結合
 * obj(...) -- 対象のコンストラクタ
 * mor(...) -- 射のコンストラクタ
 */

具体例

PathCatは、グラフから自動的に圏を作るメカニズムなので、グラフの具体例を与えれば、圏の具体例が得られます。

まず、次のようなグラフを考えてみましょう。

/* Graph1.js */

var Graph1 = {
};

Graph1.isVertex = function(x) {
  return (x === 0 || x === 1 || x === 2);
};

Graph1.isEdge = function(x) {
  return false;
};

Graph1.eqVertex = function(a, b) {
  if (!Graph1.isVertex(a) || !Graph1.isVertex(b))
    throw "not a vertex";
  return a === b;
};

Graph1.eqEdge = function(e, f) {
  throw "not an edge";
};

Graph1.src = function(e) {
  throw "not an edge";
};

Graph1.trg = function(e) {
  throw "not an edge";
};

Graph1.vertex = function(n) {
  if (!Graph1.isVertex(n)) throw "invalid argument";
  return n;
};

Graph1.edge = function() {
  throw "cannot create";
};

isEdgeがいつでもfalseを返すので、これは頂点だけで辺をまったく持たないグラフです。離散グラフと呼ぶことがあります。この離散グラフからでも圏を作れます。

js> var Cat1 = new PathCat(Graph1)
js> Cat1.isObject(1)
true
js> var id_1 = Cat1.id(1)
js> id_1
1,1
js> Cat1.composable(id_1, id_1)
true
js> Cat1.compose(id_1, id_1) // id_1;id_1
1,1
js> Cat1.eqMor(id_1, Cat1.compose(id_1, id_1)) // id_1 = id_1;id_1
true
js>

圏の対象の集合は {0, 1, 2} で、id_0, id_1, id_2 という射だけがあります。JavaScriptデータのレベルでは、恒等射は、[0, 0], [1, 1], [2, 2] という形になりますが、具体的な表現はどうでもよくて、構造としては確かに離散圏（恒等射以外の射を持たない圏）です。

他の具体的なグラフの例としてGraph2, Graph3も作っておきました（ソースコードはこちら→http://d.hatena.ne.jp/m-hiyama-memo/20090525/1243206472）、これらのグラフからどんな圏が作られるかは、ご自分の目と手で確認してみてください。もっと別なグラフの例を追加するのもいいと思います。

*1:リストの最後の頂点は省略できます。最後の頂点も明示的に書くようにしたのは、そのほうが檜山が気分がいいからです。それ以上の理由はありません。