LoginSignup
22
9

More than 5 years have passed since last update.

Haskell (その2)Advent Calendar 2018Day 16
@maton(maton)

[論文/ライブラリ紹介] Algebraic graphs with class (functional pearl)

Posted at

本記事は Haskell (その2) Advent Calendar 2018 16日目の記事です。

本記事では、Haskell Symposium 2017 で発表された Algebraic graphs with class (functional pearl)1 という論文および、その実装である algebraic-graphs パッケージを紹介していきます。

提案されている Algebraic graphs （本記事では代数グラフと呼ぶことにします）は、これまでのグラフ表現に代わり、グラフの接続関係を加法や乗法（に似た表現）で表すことで、不正な形式のグラフの構築を型レベルで抑止し、グラフに対する様々な操作をエレガントに表現しています。

これまでのグラフ表現

ここで言うグラフとは、棒グラフや曲線グラフのようなものでなく2、有向グラフのような点とか矢印からなるものを指します。
グラフ理論的には頂点集合 $V$ と辺集合 $E$ からなる組 $\ G=(V,E)\ $ と表現されます。
プログラミングにおいては隣接リストや隣接行列など、様々なグラフデータ構造で表現されます。
最も単純な表現方法は、頂点集合と辺集合をそのまま組として扱うことです（ここからしばらく有向グラフを前提に話します）。

data Graph a = ([a], [(a,a)])
data Graph a = Graph { vertices :: [a], edges :: [(a,a)] } -- ラベルをつけるとこんな感じ

これは、頂点のラベルの型を a としたとき、

  • 頂点集合を a のリスト [a] で
  • 辺を始点と終点の組 (a,a) として、辺集合をそのリスト [(a,a)] で

表現した形になります。
集合をそのまま表すならばSetデータ構造が適していますが、ここでは簡単のためにリストで表現することにします。

これまでのグラフ表現が抱える問題

先述のグラフ表現には実は問題があり、不正な形式のグラフ（malformed/inconsistent graph）を表現することができてしまいます。
例えば以下のようなグラフが不正な形式のグラフになります。

Graph [1] [(1,2)]

このグラフは、存在しない頂点 2 に向かって辺を作ってしまっています。
このような小規模なグラフであれば、目視で不正な形式のグラフであると判断できそうです。
しかし、様々な計算を経て作られた巨大なグラフであれば、実際にグラフを利用するまで不正な形式のグラフであることに気づかない恐れがあります。
また、グラフが不正であることに気づかずに種々の計算を行ってしまうかもしれません3。

この問題には、正常なグラフと不正な形式のグラフの境界が値レベルに存在し、型レベルでは判断できないという側面があります。
つまり、グラフを構成する頂点集合や辺集合に含まれる値を調べてみないと不正であることを判断できないのです4。

代数グラフによる解決

本論文で提案されている代数グラフは、以下のような代数データ構造で表現されます。

data Graph a = Empty
             | Vertex a
             | Overlay (Graph a) (Graph a)
             | Connect (Graph a) (Graph a)
  • Empty: 空グラフを表現します
  • Vertex: 単一の頂点を表現します
  • Overlay: グラフの重ね合わせを表現します
  • Connect: グラフの接続を表現します

EmptyとVertexはまあ良いと思いますので、OverlayやConnectに注目しましょう。
これらはどちらもグラフをつなぎ合わせることを表現するのですが、つなぎ方が異なります。

Overlayは、2つのグラフの頂点集合と辺集合の和集合をとったグラフを表現します。
数式では " $+$ " という記号で表し、以下のように定義できます。
$\ (V_1, E_1) + (V_2, E_2) \overset{\mathrm{def}}{=} (V_1 \cup V_2, E_1 \cup E_2) \ $

一方でConnectは、2つのグラフの頂点集合と辺集合の和集合をとり、さらに片方の頂点集合のすべての頂点をもう片方の頂点のすべての頂点への辺を加えます（これは直積集合として表現できます）。
数式では " $\rightarrow$ " という記号で表し、以下のように定義できます。
$\ (V_1, E_1) \rightarrow (V_2, E_2) \overset{\mathrm{def}}{=} (V_1 \cup V_2, E_1 \cup E_2 \cup V_1 \times V_2)\quad $

この辺は例を見るのが手っ取り早いのですが、えっと…その…転載するのもナンなので、具体例はスライドの方を見てください。
（この記事の存在意義…）

さて、この表現方法なのですが、それぞれの型コンストラクタを関数と見なすと、それは全域関数になっています。
すなわち、この方法で構築されたグラフが不正な形式のグラフであるとき、型検査でエラーとなります。

例えば、先ほどの不正な形式のグラフ Graph [1] [(1,2)] を代数グラフで表現しようとしてみても、
Connect (Vertex 1) 2 では Connect の2番目の引数で型エラー（Graph Int にすべきところに Int が入っている5）が発生します。
Connect の引数にするためには、Graph 型の型コンストラクタで要素を包んであげなければならないのです。

もっとすごいぞ代数グラフ

さて、このグラフ構造を更に応用させるために、論文中では様々な応用が紹介されています。
ここではいくつかのケースをピックアップして紹介します。

例：クリークの構築

上記のプリミティブだけでは使い勝手がよろしくないので、論文では様々な補助関数が挙げられています。
それらの補助関数も、プリミティブの組み合わせでシンプルに表現することができます。
具体例として、与えられた頂点リストのクリーク（全頂点間に辺があるグラフ）を作る関数 clique を考えてみましょう6。
関数のシグネチャは以下のようになります。

clique :: Graph g => [Vertex g] -> g

クリーク構築の部分問題として、あるクリークであるグラフ $G = (V, E)$ に新たに頂点 $v$ を加え、クリークにすることを考えます。
頂点 $v$ とクリーク $G$ を接続し、再びクリークになるためには、$v$ と $V$ のすべての頂点との間に辺が必要です。
単一の頂点 $v$ からなる頂点集合を $V'$ とすると、頂点集合間のすべての辺の組み合わせは $V'\times V$ と表現できます。
そして、これを実現する関数が connect になります。
すなわち、頂点 v をクリークなグラフ g に加えてクリークにする処理は、 connect (vertex v) g と表現できます。
（ここで、ある頂点から単一頂点のグラフを構築する関数として vertex を用いています。）

あとは、リストのすべての頂点を連続して connect していけばよいのですが、connect をグラフにおける二項演算とみなしたとき、その単位要素は何になるのでしょうか。
実は、代数グラフは、connect （つまり $\rightarrow$ ）を二項演算、空グラフ empty （つまり $\epsilon$ ）を単位元とするモノイドを成すことが論文中で示されています。
つまり、空グラフ empty にリスト中の頂点を次々に connect していけば頂点集合からクリークを構成できます。

一連の処理は、空グラフ empty への頂点の連続接続を foldr を用いて foldr connect empty と表現すれば実装できます。
ただし、 connect は Graph g 間の二項演算なので、頂点集合（リスト） [Vertex g] を単一頂点グラフ集合 [Graph g] に持ち上げることが必要です。
そのため、頂点集合に対して map vertex します。
全体としては以下のような実装になります。

clique :: Graph g => [Vertex g] -> g
clique = foldr connect empty . map vertex

この関数は Algebra.Graph.clique としてライブラリに含まれています7。
他にもパスや閉路グラフ、ツリーを構築する関数などが実装されています。

例：交換則を用いた無向グラフ

データ構造に対応する型クラスを作ることで、様々な性質を持つグラフを表現することが可能です。
ここでは、具体例として交換的閉包を代数グラフに加えて、無向グラフを作ってみます。
手順としては以下のような感じです。
- 型クラス化する
- 集合上の2項関係をグラフで表現する
- 交換則を与え、交換的閉包を作る

まずは、型クラス化です。
ノードの型を Vertex g として扱います。以下の記法には TypeFamilies GHC拡張が必要です。

class Graph g where
  type Vertex g
  empty :: g
  vertex :: Vertex g -> g
  overlay :: g -> g -> g
  connect :: g -> g -> g

さて、これによって様々なものを代数グラフで表現できるようになりました。
次は2項関係を考えてみます。
集合上の2項関係は、要素の集合 domain と、2項関係が存在する要素の組の集合 relation から表現されます。

import Data.Set (Set)

data Relation a = R 
  { domain :: Set a
  , relation :: Set (a, a) 
  } deriving Eq

集合の表現には containers パッケージの Set を使用することとします。
さて、これを Graph g のインスタンスにしてみます。
overlay や connect はそれぞれ、上記で示した " $+$ " や " $\rightarrow$ " で表せることを思い出しましょう。
すなわち、以下のような計算になります。
$\ (V_1, E_1) + (V_2, E_2) \overset{\mathrm{def}}{=} (V_1 \cup V_2, E_1 \cup E_2) \ $
$\ (V_1, E_1) \rightarrow (V_2, E_2) \overset{\mathrm{def}}{=} (V_1 \cup V_2, E_1 \cup E_2 \cup V_1 \times V_2)\quad $

これらの計算を Haskell コード上でも表現していきます。

import Data.Set (Set, singleton, union, elems, fromAscList)
import qualified Data.Set as Set (empty)

data Relation a = R { domain :: Set a, relation :: Set (a, a) } deriving Eq

instance Ord a => Graph (Relation a) where
  type Vertex (Relation a) = a
  empty = R Set.empty Set.empty
  vertex x = R (singleton x) Set.empty
  overlay x y = R (domain x `union` domain y) (relation x `union` relation y)
  connect x y = R (domain x `union` domain y) (relation x `union` relation y `union`
    fromAscList [ (a, b) | a <- elems (domain x), b <- elems (domain y) ])

union はその名の通り、集合の和をとる演算です。
直積集合$\ V_1 \times V_2\ $は、リスト内包表記を用いて、
fromAscList [ (a, b) | a <- elems (domain x), b <- elems (domain y) ]
と表現できます。

さて、これで集合上の2項関係を代数グラフ上で扱うことができるようになりました。
次はこれに対称律を導入しましょう。
Algebra.Graph.Relation.InternalDerived では、対象律は以下のように定義されています。

newtype SymmetricRelation a = SymmetricRelation { fromSymmetric :: Relation a }
    deriving (Num, NFData)

instance Ord a => Eq (SymmetricRelation a) where
    x == y = symmetricClosure (fromSymmetric x) == symmetricClosure (fromSymmetric y)

ここで、symmetricClosure は、対称的閉包を構築する関数です。
やることは単純で、すでに存在する2項関係の始点と終点をひっくり返したものを2項関係に加えてあげればよいです。

symmetricClosure :: Ord a => Relation a -> Relation a
symmetricClosure (Relation d r) = Relation d $ r `Set.union` Set.map swap r

そして、SymmetricRelation を Graph のインスタンスにしてあげます。
fromSymmetric で包んであげることで、Relation の overlay や connect のインスタンスを使うことができ、シンプルにかけます。

instance Ord a => Graph (SymmetricRelation a) where
    type Vertex (SymmetricRelation a) = a
    empty       = SymmetricRelation empty
    vertex      = SymmetricRelation . vertex
    overlay x y = SymmetricRelation $ fromSymmetric x `overlay` fromSymmetric y
    connect x y = SymmetricRelation $ fromSymmetric x `connect` fromSymmetric y

このインスタンスはどうやら GHC 8.2 で追加された GeneralizedNewtypeDeriving によって自動導出できそうだと言われており、今後置き換わるかもしれません。（GeneralizedNewtypeDeriving についてはこちらで解説されていらっしゃいます。）

さて、以上で対象律を導入することができました。
このグラフは無向グラフになります。
例えば、以下のような初期化方法の異なる2つのクリークがちゃんと等価になります。

> clique "abcd" == (clique "dcba" :: Symmetric Char)
True

上記の他にも、反射性や対称性を導入することで、同値関係を扱えるようになったりします。

残りのトピック

本記事は論文からいくつかつまみ食いした程度なので、まだまだ紹介できていない内容があります。
今回紹介できなかったトピックを列挙します。
気になったら読んでみてください（投げっぱなし）。

  • 3章：代数的構造
    • 半順序関係
    • 等式推論
  • 4章：アラカルト（型クラスを使って様々なインスタンスを紹介）
    • 標準形（異なる表現をもつグラフも、標準形に変形することで、等しいグラフかどうかを判定できるようになる）
    • Deep Embeddings（データ型で表すとDeep, 型クラスで表すとShallowになる。Deepな表現を標準形にするにはFoldなどを用いた変換が必要になる）
    • 反射的グラフ（各ノードが自己ループを持つ（反射的閉包））
    • 推移的グラフ（接続関係に関する推移的閉包）
    • 前順序と同値関係（反射的グラフと推移的グラフを組み合わせて前順序ができる、これは強連結成分の検出に使える。そして無向の場合は同値関係になる）
    • ハイパーグラフ
  • 5章：グラフ変換ライブラリの実装
    • 特定の形状（パス、サイクル、スター、木、森）をつくる関数
    • newtypeを用いた逆向きグラフ
    • グラフファンクタ、グラフモナド
    • 頂点、辺の削除
    • De bruijn グラフ
  • 6章：関連研究（他のライブラリとの比較）
  • 7章：今後の展望

参考文献

  • Algebraic graphs with class (functional pearl) | GitHub
    • 投稿論文、スライドがリリースされており、発表ビデオへのリンクも公開されています。
    • 正直、スライドを読めばこの記事を読まなくても要旨がわかります :upside_down:
  • Algebraic graphs | GitHub
    • algebraic-graphs ライブラリのリポジトリです。
    • Hackage でも公開されています。
  • グラフ代数 | POSTD
    • 論文およびライブラリの作者である Andrey Mokhov 氏のブログポストの翻訳記事です。
  • A. Mokhov, V. Khomenko. ”Algebra of Parameterised Graphs“, ACM Transactions on Embedded Computing Systems, 2014

余談ですが、著者の Andrey Mokhov 先生は翌年の ICFP 2018 で Build Systems à la Carte という論文を投稿され、ベストペーパー賞を取られています。そちらの論文についても読んでみたいですね（誰か解説記事を書いてくれないかな…なんちゃって）。

  1. functional pearl は、Haskell Symposium においてとりわけ解法のエレガントさを重視している投稿区分であり、タイトルには (functional pearl) と付記されます。 ↩

  2. Algebraic graphs で画像検索すると、多項式曲線のグラフがたくさん出てくるようです :sweat_smile:  ↩

  3. 今回の問題のように、データ構造の正当性が型レベルで表現できない場合には、篩型（Refinement Type）、依存型（Dependent Type）を導入し、型検査で正当性を検証するというアプローチがしばしば取られるようです。しかし、私自身そこまで詳しくないのでこれ以上の説明は控えさせていただきます…。 ↩

  4. 論文中では他にも、containers ライブラリの隣接行列表現が配列外参照をコンパイル時には検出できないことや、fgl ライブラリの帰納的グラフ表現に対するグラフ操作関数が部分関数であり、実行時例外を起こしうることが指摘されています。 ↩

  5. 実際のところは Num a => Graph a と Num a => a とのミスマッチになると思いますが、簡単のため。 ↩

  6. 本当は無向グラフで議論すべきですが…（無向グラフを作る方法は後述します） ↩

  7. 実際のところは、connects = foldr connect empty という補助関数を経由して実装されています。 ↩

22
9
1

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
22
9