有向グラフを表現するデータ形式について

今年の4月に、「すごいグラフ処理ライブラリNetworkXの使い方」という記事を書きました。メモ編にもいくつかNetworkX関係のメモが残っています。

• https://m-hiyama-memo.hatenablog.jp/search?q=networkX

NetworkXとGraphVizの組み合わせは、グラフの操作・解析・描画に便利なんですが、グラフを表現するデータ形式が色々あって頭がこんがらかる時があります。実装に依存しない一般論を一回整理しておいたほうがいいようです。ライブラリ固有のネイティブ形式ではなくて、JSONで表現できるデータ形式の話をします。

例題は次のようなグラフだとします。

1. 頂点（ノード）は、a, b, c, d, e の5つがある。
2. 辺は次の4本：
   1. a → b
   2. b → c
   3. c → a
   4. c → d

内容：

単純な有向グラフ

以下、有向グラフだけを考えます。まずは多重辺を持たない単純な有向グラフから。

グラフは「頂点の集合と辺の集合」からなります。辺は、2つの頂点の順序対です。頂点は文字列のIDで表現するとして、グラフの定義を素直にJSONデータにすれば次のようでしょう。

{
 "nodes": ["a", "b", "c", "d", "e"],
 "edges": [["a", "b"], ["b", "c"], ["c", "a"], ["c", "d"]]
}

どの辺とも接してない頂点を孤立点と呼ぶことにします。もし、孤立点がないなら、辺のリスト（配列）だけでも完全にグラフを表現できます。しかし孤立点があると、辺のリストを見ただけでは孤立点の存在が分からないので、やはり頂点集合も必要となります。

["a", "a"] のように、自分自身に戻る辺を自己ループ辺と呼びます。すべての頂点が自己ループ辺を持つグラフは反射的グラフといいます。反射的グラフには孤立点がありません； 自己ループ辺といえども辺だからです。例題のグラフを反射的グラフに直すと、次のようになります。

{
 "nodes": ["a", "b", "c", "d", "e"],
 "edges": [["a", "a"], ["b", "b"], ["c", "c"], ["d", "d"], ["e", "e"],
           ["a", "b"], ["b", "c"], ["c", "a"], ["c", "d"]
          ]
}

この場合は、頂点が自己ループ辺として辺集合に埋め込まれているので、辺のリストだけでグラフを完全に表現できます。

dict-of-lists形式

NetworkXでdict-of-lists形式と呼んでいるデータ形式では、1つの頂点から出る辺のターゲット達をリストとして並べます。実例を出したほうが話が早いでしょう。

{
 "a": ["b"],
 "b": ["c"],
 "c": ["a", "d"],
 "d": [],
 "e": []
}

最初に出した形式より、dict-of-lists形式のほうがコンパクトですね。自己ループ辺を加えた反射的グラフなら次のようです。

{
 "a": ["a", "b"],
 "b": ["b", "c"],
 "c": ["c", "a", "d"],
 "d": ["d"],
 "e": ["e"]
}

頂点／辺に値が付いたグラフ

頂点と辺（どちらか片方のときもある）になんらかの値が付いたグラフを考えます。この値は、ラベル、重さ、色などと呼ばれることがあります。現実のモデルだと電圧だったり、輸送量だったりもします。

例題のグラフの頂点 a, b, c, d, e に、それぞれ 10, 20, 30, 40, 50 の数値を割り当て、辺には「ターゲットの値 - ソースの値」と引き算した値を割り当てることにします。まずは素朴に、値をリスト要素（むしろタプル要素）として付け加えてみます。

{
 "nodes": [["a", 10], ["b", 20], ["c", 30], ["d", 40], ["e", 50]],
 "edges": [["a", "b", 10], ["b", "c", 10], ["c", "a", -20], ["c", "d", 10]]
}

あんまり見やすくないですね。リスト（配列）より辞書（マップ、JSONオブジェクト）形式のほうが少しスッキリします。値付きの頂点は次のように表現できます。

{
 "a": 10,
 "b": 20,
 "c": 30,
 "d": 40,
 "e": 50
}

値付きの辺は入れ子の辞書で表現します。NetworkXでは、dict-of-dicts形式と呼んでいます。

{
 "a": {"b": 10},
 "b": {"c": 10},
 "c": {"a": -20, "d": 10},
 "d": {},
 "e": {}
}

ちょっと分かりにくいですが、このデータをJavaScriptの変数edgesに入れたとすると、edges.a.b、あるいは edges["a"]["b"] として、辺 a→b の値を取ることができます。

>>> var edges = { "a": {"b": 10}, "b": {"c": 10}, "c": {"a": -20, "d": 10}, "d": {}, "e": {}}
undefined

>>> edges.a.b
10

>>> edges["a"]["b"]
10

その他

例題では、頂点／辺に付ける値が単なる数値でしたが、複雑な値を割り当てることもできます。例えば、GraphVizでは、{"color": "green", "shape": "circle"} のような値により描画時のスタイリングをしています。

多重辺を扱いたいときは、辺のIDを値として割り当て、両端が同じでもIDが違えば異なる辺と解釈すればいいでしょう。実際には、NetworkXもGraphVizも多重辺のサポートは弱いので、苦労させられることはあります。

隣接行列や接続行列としてグラフを表現することもできます。NetworkXは、NumPy、SciPyの行列によるグラフ表現もサポートしています。

とにかく、いろんな表現方法があります。どれかひとつで済ませることも出来ないので、全体の関連性をつかんだ上で適宜使い分けるしかないようです。