久々の投稿です。
次こそはSML#ネタを投稿したかったのですが、今回もOCamlです。
前に投稿したプログラミング勉強会（笑）の巡回セールスマン問題のために、OCamlでグラフを扱いたかったのでライブラリを探してみたところ、容易にocamlgraphというものを見つけました。
これが中々使うのが大変で、骨の折れる作業でございました。
ファンクターをこのライブラリでは多用しておりまして、非常に把握しづらいといいますか。
で、結局挫折しました（白目）
自分が観測した範囲でできること
- 手続き的・immutableなグラフの両方を扱える
- 代表的なグラフアルゴリズムを扱える。
- dot言語を出力できる。外部ツールと組み合わせてグラフ描画できる。
- グラフの頂点・辺に対して基本的な演算やfold,iterなどで繰り返し処理を書ける
見たところ、
- ダイキストラ法
- フォード・ファルカーソンのアルゴリズム（フローネットワークの最大フローを求める
- ゴールドバーグの最小フローアルゴリズム
- ベルマンフォードの負の閉路を見つけるアルゴリズム
- クルスカルの最小全域木を求めるアルゴリズム
は実装されているようです。
最初に公式サイトを貼っておきます。http://ocamlgraph.lri.fr/
まぁまずはdemo.mlを実行してみますよね。OPAMからもこのライブラリはインストールできるのでちゃちゃっとインストールしてインタラクティブモードか何かで実行してしまえばいいと思います。
あ、ちゃんと動かすにはdotとgvが必要です。
このライブラリの問題はまともなチュートリアルがないことなんですよね。
一応TFP2007のライブラリ開発に関する論文が公式に貼ってあるのですが、それくらい。
チュートリアルはサンプルを見ろということなのでしょうか。
まぁ往々にして研究レベルのツールにはあることですね。
あとは公式のAPIドキュメント嫁という話なのですが、一つ注意点。
最小全域木を作りたいからって早速Graph.Kruskalとかのページを見ないこと。
僕のお薦めは、Graph.PackにあるMutableもしくはImmutableなモジュールをいじることです。
Graph.Packに入っている2つのモジュールは、書いてあるとおりすぐに使用できるものになっておりまして、Edge,VertexにIntのラベルを用います。
このライブラリはラベルにどの型を使うか、それを表示させるときにどのように表示させるかなど非常に細かな設定をmoduleに書いて、それをファンクターに渡して生成することになるのでなんか最初からちゃんとしたグラフモジュールを作るぞーとなるとチュートリアルもないので挫折します。
まずはGraph.Pack.Graphあたりをいじって、
次にhttp://stackoverflow.com/questions/8999557/how-to-visualize-draw-automata-in-ocaml/9011334#9011334
あたりを読んで（唯一わかりやすい使用例、どのように使うのか何となくわかる気がする）
使うのが良いのではないでしょうか。
僕は上のをよんで、やっとどのグラフを作るにも要求されるシグニチャGは、グラフで
そこの中に含まれているシグニチャEはEdge、VはVertexだということに気づきました（白目）
ついでにE.tやV.ｔはEdge,Vertexのラベルの型を指しているのだと思います。
ダイキストラ法ではEdgeのラベルを重みとして使っているのだったかな？
うーん、ドヤ顔で難しいとか言ってるけどほんとなのかなぁ。
自分がファンクターに慣れてないだけでは。まぁいいか。
詳しい方いらっしゃいましたら僕にご教授いただければ幸いです。
