グラフやネットワークを扱うClojureライブラリ「Jungerer」
はじめに
Jungererは私が開発したグラフ/ネットワークを扱うClojureライブラリです。JavaのライブラリであるJUNG (Java Universal Network/Graph Framework)をラップして、Clojureから簡単に扱えるようにしています。
Clojureでグラフ/ネットワークを扱うライブラリとしては、他に純Clojureで実装されたLoomがあります。Loomの解説記事も書いていますので、興味ある方はご覧ください。
Loomはとてもよくできたライブラリですが、ページランクなどの中心性を計算するアルゴリズムが不足しています。また、グラフの可視化に外部ツールであるGraphVizが必要となります。
Jungererでは、JUNGのもつ多くのアルゴリズムを利用することができます。それらはJavaで書かれているため高速に動作します。また、可視化にSwingを使っているため、外部への依存なしでClojureから即座に可視化することができます。
使い方
インストール
Clojarsで配布されているため、LeiningenやBootの依存設定に以下を追加するだけです。
[jungerer "0.4.1"]
グラフの生成・変更
jungerer.graphはグラフの作成やノードの追加など、グラフ自体のデータを取り扱います。
まずグラフを作成するには、
(require '[jungerer.graph :as g])
(def graph (g/directed-graph [[1 2] [2 3] [4 2]]))
のようにします。[1 2]はエッジをあらわし、その中の1や2がノードです。directed-graphは有向グラフを作成するので、この場合、
- 1 → 2
- 2 → 3
- 4 → 2
という3つのつながりのあるグラフができます。無向グラフを作りたければ、undirected-graphを使います。上の例ではノードに数値を入れていますが、文字列でもオブジェクトでも構わないです。
作成したグラフにエッジを追加したいときは、add-edge!を使います。
(g/add-edge! graph [4 5])
Jungererが作成するグラフはミュータブルなため、add-edge!やadd-node!は元のデータを変更してしまうことに注意してください。これはJavaライブラリであるJUNGが元々イミュータブルには作られていないためであり、Loomのデータ構造と比べるとClojureらしくはない点だといえます。
グラフのノードやエッジを取得するには以下のようにします。
(g/nodes graph)
;;=> #{1 4 3 2 5}
(g/edges graph)
;;=> ([1 2] [2 3] [4 5] [4 2])
他にも多くのグラフ操作関数が用意されているので、詳しくはドキュメントを参照してください。
様々なアルゴリズム
jungerer.algoにはノード間の最短経路や中心性などを計算するアルゴリズムが用意されています。
次のコードは、ダイクストラ法を用いてノード4からノード3への最短経路を計算します。
(require '[jungerer.algo :as a])
(a/dijkstra-path graph 4 3)
;;=> [4 2 3]
中心性を計算するアルゴリズムとして、たとえばページランクを計算したければ、
(def scorer (a/page-rank graph))
(a/score scorer 2)
;;=> 0.26350079629361517
のようにします。page-rankによってページランクのScorerを作り、score関数にScorerとノードを渡すことで、そのノードの中心性スコアを取得できます。上の例ではノード2のスコアを求めています。
betweenness-centralityやcloseness-centralityなどの様々なScorerを生成する関数が用意されているので、求めたい中心性によって利用するScorerを切り替えてください。他の経路探索アルゴリズムやScorer生成関数はドキュメントを参照ください。
可視化
jungerer.visはグラフの可視化を担当しています。JavaのGUIツールキットであるSwingを用いて簡単にグラフを描画することができます。
view関数にグラフを渡すだけで、すぐに可視化することができます。
(require '[jungerer.vis :as v])
(v/view graph)
グラフのレイアウトアルゴリズムを変更したいときは、グラフを***-layoutでラップしてから渡します。デフォルトではcircle-layoutが使われます。また、第2引数にはウィンドウに対するオプションをマップで渡すことができます。
(v/view (v/kk-layout graph) {:title "My Graph"
:frame-size [640 520]
:node-label-fn (fn [node]
(str "node" node))
:edge-label-fn (fn [[node1 node2]]
(str node1 " -> " node2))})
インポートとエクスポート
jungerer.ioを用いると、グラフを外部ファイルに書き出したり、読み込んだりできます。他のグラフソフトウェアと組み合わせて解析する際に利用します。
load-pairs!を使うと、1行ごとに半角スペースをはさんでエッジ（ノードのペア）が記述されたファイル（e.g. sample.pairs）を読み込みます。
(require '[jungerer.io :as i])
(def graph (g/directed-graph))
(i/load-pairs! "dev-resources/sample.pairs" graph)
逆に、save-as-pairsでグラフをファイルに書き出すことができます。先ほど読み込んだグラフにエッジをひとつ足して書き出してみると、元のファイルからエッジが増えて保存されているはずです。
(g/add-edge! graph ["AAA" "LLL"])
(i/save-as-pairs "/tmp/sample-edited.pairs" graph)
おわりに
Clojureのグラフ/ネットワークライブラリであるJungererを紹介しました。基本的なネットワーク分析機能で十分なときはLoom、より高度な分析やパフォーマンスが必要なときはJungererと、使い分けるのがよいかと思います。