すごいグラフ処理ライブラリNetworkXの使い方 - 檜山正幸のキマイラ飼育記 (はてなBlog)

NetworkX（http://networkx.lanl.gov/ 、https://networkx.lanl.gov/trac/wiki）*1は、なかなかにすごいPythonライブラリです。ここで言っているNetworkは、実際の通信ネットワーク（のモデル）に限らず、グラフの辺に重さ（weight）と呼ばれる値を割り当てた構造です。重さを考えないときは、全ての辺に同じ重さが付いているとすればいいので、普通のグラフも扱えます。つまり、NetworkXを使ってグラフに対するさまざまな処理ができるのです。

内容：

例題：コールグラフ

関数のコールグラフを扱ってみたいと思います。例えば、次のJavaScript関数を考えます。

function foo(x) {
 if (x < 0) {
    return bar(x);
 } else {
    return baz(x)
 }
}

関数fooは、関数barとbazを呼び出しています。これを次のように書いてみましょう。

foo
  bar
  baz

同じように、他にもいくつかの関数があって、その呼び出し関係が次のようだとします。

foo
  bar
  baz

bar
  baz

baz
  zot
  foo
  baz

zot

「呼び側 → 呼ばれ側」という方向の有向グラフで表すと次のようになります（描画はGraphvizを使ってます）。

~~Graphvizでは~~今使っているGraphvizフロントエンドに問題があって、自己ループ辺を簡単には描けないので、baz→baz というループを描く代わりにノードbazを二重丸で描いて識別しています。

有向グラフの表現方法

NetworkXを使う前に、有向グラフを表現するデータを決めておきましょう。JSON形式を使うことにします。

例題のコールグラフのノード（関数を表すマル）fooに注目してください。fooから出る辺は2本で、それぞれの先にbar, bazというノードがあります。この部分だけを図示すると：

この図のように、ひとつのノード（foo）を中心として隣接するノード（bar, baz）とそこに至る辺の集まりをスターと呼びます。この場合、スターの中心はfooなので、fooを中心とするスターといいます。

グラフを構成するノードごとに、そのノードを中心とするスターを列挙すればグラフは完全に記述できるので、次のJSONオブジェクトデータをグラフの記述に使いましょう。1つのプロパティが1つのスターに対応します。

{
  "foo": ["bar", "baz"],
  "bar": ["baz"],
  "baz": ["zot", "foo", baz"],
  "zot": []
}

NetworkXでJSONが使えるのか？というと、実はPythonの辞書型／リスト型データがJSONと同じ構文なので、JSONを使っているように見えるのです。NetworkXでは、この形式のデータをdict_of_lists形式と呼んでいます。それとは別に、JSONファイル／JSON文字列を読み書きする関数もちゃんと備えています。NetworkXでは、dict_of_lists形式以外にも多様なデータ構造からグラフ構築ができます。

NetworXを使ってみる

NetworXのインストールは、easy_install networkx で行えます。他に、matplotlib、pylab、numpy もインストールされているとします。以下、次のようにimportしていると仮定します。

import networkx as nx
import matplotlib.pylab as p

対話的インタプリタだと次のようです。

$ python
Python 2.6.5 (r265:79096, Mar 19 2010, 21:48:26) [MSC v.1500 32 bit (Intel)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> import networkx as nx
>>> import matplotlib.pylab as p
>>>

有向グラフのコンストラクタは nx.DiGraph です。

>>> g = nx.DiGraph(
... {
...   "foo": ["bar", "baz"],
...   "bar": ["baz"],
...   "baz": ["zot", "foo", "baz"],
...   "zot": []
... }
... )
>>>

gはDiGraphクラスのオブジェクトです。nx.to_dict_of_lists関数で dict_of_lists形式に変換できます。

>>> g
<networkx.classes.digraph.DiGraph object at 0x02E1A710>
>>> nx.to_dict_of_lists(g)
{'baz': ['baz', 'foo', 'zot'], 'foo': ['baz', 'bar'], 'zot': [], 'bar': ['baz']}
>>>

DiGraphは多重辺を許しませんが、自己ループ辺は許します。selfloop_edgesメソッドで自己ループ辺を調べられます。サイクルの検出も簡単で、simple_cycles関数で単純サイクルを列挙できます。

>>> g.selfloop_edges()
[('baz', 'baz')]
>>> nx.simple_cycles(g)
&#91;['baz', 'baz'], ['foo', 'bar', 'baz', 'foo'], ['foo', 'baz', 'foo']&#93;
>>>

baz→baz が自己ループ辺で、それ以外の単純サイクルは、foo→bar→baz→foo と foo→baz→foo です（先の図で確認してください）。

有向グラフの辺の向きをすべて逆にするにはreverseメソッドです。

>>> gr = g.reverse()
>>> nx.to_dict_of_lists(gr)
{'zot': ['baz'], 'foo': ['baz'], 'baz': ['bar', 'foo', 'baz'], 'bar': ['foo']}
>>>

グラフを表示するには、nx.drawとp.show関数を使います（次の図）。

デフォルトの描画はこんな感じでGraphvizに比べるとちょっとショボイですが、対話的にすぐに確認できます。

推移的閉包を求める

例題のグラフは、「呼び側→呼ばれ側」の関係でした。reverseで逆転したグラフは「呼ばれ側→呼び側」です。さらに、間接的にでも呼ばれていれば辺で結んだグラフを作ってみましょう。このグラフを見れば、ある関数を直接間接に呼び出している関数が即座に分かります。

この目的には、グラフの推移的閉包を求めればいいのですが、NetworkXのグラフアルゴリズム一覧（http://networkx.lanl.gov/reference/algorithms.html）に推移的閉包が載ってません。が、最短経路アルゴリズムで同等のことができます。

>>> nx.shortest_path(gr)
{'zot': {'baz': ['zot', 'baz'], 'foo': ['zot', 'baz', 'foo'], 'zot': ['zot'], 'b
ar': ['zot', 'baz', 'bar']}, 'foo': {'bar': ['foo', 'baz', 'bar'], 'foo': ['foo'
], 'baz': ['foo', 'baz']}, 'baz': {'bar': ['baz', 'bar'], 'foo': ['baz', 'foo'],
 'baz': ['baz']}, 'bar': {'baz': ['bar', 'foo', 'baz'], 'foo': ['bar', 'foo'], '
bar': ['bar']}}
>>>

見にくいですが、最短経路をすべて列挙してます。経路自体は不要で、経路があるかないかだけを知りたいので、次の短いプログラムを書きます。

def star_closure(g):
  sp = nx.shortest_path(g)
  r = {}
  for x in sp.keys():
    r[x] = []
    for y in sp.get(x).keys():
      r[x].append(y)
  return r

最短経路情報を見て、経路が存在する頂点のあいだを辺で結んだデータを作っています。star_closureの"star"は「グラフノードのスター」のことではなくて、正規表現などで使う星印の意味です。Gの推移的閉包をG^*と書くことがあるのです。star_closure(gr) とすると次のデータが得られます。

{
  'foo': ['bar', 'foo', 'baz'],
  'bar': ['baz', 'foo', 'bar'],
  'baz': ['bar', 'foo', 'baz'],
  'zot': ['baz', 'foo', 'zot', 'bar']
}

このグラフデータ（dict_of_lists形式）を見ると、すべての頂点に自己ループ辺があります。自分から自分には長さ0の経路があるからです。しかし、自明な経路は除いて、再帰呼び出しがあるときだけ自己ループ辺を作るようにしたほうが便利でしょう。かなり手抜きですが、次のようにしてそれを実現できます。

def _flatten(lislis):
  l = []
  for lis in lislis:
    l[len(l):] = lis
  return l

def plus_closure(g):
  cn = _flatten(nx.simple_cycles(g)) # サイクルに含まれるノード達
  sp = nx.shortest_path(g)
  r = {}
  for x in sp.keys():
    r[x] = []
    for y in sp.get(x).keys():
      if x == y: # 自己ループが現れたとき
        if x in cn:
          r[x].append(y)
      else:
        r[x].append(y)
  return r

plus_closure関数は、自明な自己ループ辺は除いた推移的閉包（G⁺と書くことがあります）を求めます。plus_closure(gr) は次のデータになります。

{
  'foo': ['bar', 'foo', 'baz'],
  'baz': ['bar', 'foo', 'baz'],
  'bar': ['baz', 'foo', 'bar']
  'zot': ['baz', 'foo', 'bar'],
}

ここでは、simple_cyclesとshortest_pathを呼んでますが、これらはグラフ全体をスキャンするので二度手間になっています。オーバーヘッドが気になるなら、既存のソースコードを参考にしてplus_closureを直接実装してもいいかもしれません。

この例題くらいのグラフのサイズだと目視手作業でもどうってことないですが、関数が100個あると人手でコールグラフの分析は辛くなります。1000個あると事実上不可能でしょう -- NetwrokXを使ってコンピュータにやらせましょう。その他、グラフを調べたり加工したりして出来る作業は色々ありますから、NetworkXの出番は多いと思います。

*1:lanl.govはロスアラモス国立研究所。原爆を作った研究所なので、良い印象を持たない人もいるでしょうが、軍事以外の研究もしていて、NetworkXもなんらかの研究に関連しているのでしょう。