Python
データ分析
Python3
networkx
python2.7

pythonでグラフ構造が必要な時はnetworkxを使おう


networkxの使い道

グラフ構造やツリー構造が必要な時に、自分で実装していませんか?

pythonの標準ライブラリにはグラフ構造が実装されていないため、

必要になるたびに簡単なグラフ構造のAPIを自作している方が多いと思います。

networkxは最短経路の導出等、ネットワークを解析するためのパッケージですが、

hashableなオブジェクトならなんでもノードにすることができ、

エッジの抽出や幅優先探索等の一般的なAPIも実装されています。

さらに、簡単にグラフを可視化できるため、効率的にデバッグできます。

これらの機能からnetworkxはネットワーク解析だけでなく、

グラフ構造APIの実装として十分活用できます。

本ブログではnetworkxをグラフ構造APIの実装として活用する際に必要となる

最低限な機能以下3点を説明します。


  1. グラフの作成

  2. グラフからのデータ抽出、

  3. グラフの可視化


グラフの作成

networkxではまずグラフオブジェクトを作成し、

グラフオブジェクトのメソッドを使ってノードやエッジを追加します。1


グラフオブジェクトの作成

グラフの種類によってインスタンスを作成するクラスが違います。2

import networkx as nx

simple_graph = nx.Graph() #無向グラフを作成
directed_graph = nx.Digraph() #有向グラフを作成


ノード、エッジの追加

グラフの作成後、グラフオブジェクト(下表では "graph")のメソッドから

ノードとエッジを追加します。

ノードとエッジは同時に複数追加することもできます。

ノードはhashableなら良いので

基本的なオブジェクトはなんでもノードにできますし、

自前実装のオブジェクトもノードにできます。

エッジを追加する際はノードが存在しない場合、自動的にノードが作成されます。

graph.add_node(node)

graph.add_nodes_from([node1, node2])
graph.add_edge(node1, node2, attr_name = attr_val)
graph.add_edges_from([(node1,node2,{"attr_name": attr_val})
,(node2, node3,{"attr_name": attr_val})])


グラフからのデータ抽出

グラフからデータを取得する方法は様々なAPIが存在しますが、

最も基本的な取得方法は以下の2種類です。


  • ノードやエッジの一覧を取得

  • ノードを引数として近傍やエッジを取得


一覧の取得

ノードとエッジの一覧は下記のapiからイテレータを取得できます。

リストにするにはリスト関数を実行する必要があります。

graph.nodes

list(graph.nodes)
graph.edges
list(graph.edges)


近傍やエッジの抽出

グラフからデータを抽出するにはグラフオブジェクトがどのようにデータを保存しているか

知る必要があります。

正確ではありませんがグラフオブジェクトはノードをキー、

近傍からエッジへの辞書をバリューとしたオブジェクトを持っているイメージです。

graph = nx.Graph()

graph.add_edge(1,2,attr="edge1")
graph.add_edge(2,3,attr="edge2")
# 以下のようなデータ構造が作成されます。
{
node1: {node2: {"attr": "edge1"}},
node2: {node1: {"attr": "edge1"},
node3: {"attr": "edge2"}
},
node3: {node2,{"attr": "edge2"}}
}

したがって以下のようにノードから近傍の取得、エッジ取得ができます。

なお、エッジは属性名をkey、属性値をvalueとした辞書になっています。

neighbor = graph[node1] # neighborはノードのイテレータ

edge = graph[node1][node2]


グラフの可視化

netowrokxはMatplotlibを使ってグラフを可視化します。3

グラフの描画ではノードの配置を決めるのが面倒くさいですが、

networkxはよく使われるレイアウト決定方法を実装してくれており、

簡単に可視化できます。

以下の例では、レイアウト決定方法としてspringレイアウト(デフォルト)を使用しています。

import matplotlib.pyplot as plt

nx.draw(graph)
plt.show()

他のレイアウト決定方法を使いたい場合や、ノードのid, エッジのアトリビュートを表示したい場合等、

詳細な可視化制御が必要な場合は nx.draw_networkxを使用してください。

各パラメータの意味は公式ページを参考にしてください。

p.s. 意見や感想をコメントに書いていただけると嬉しいです。

もしコメントがあれば今後も記事を書こうという気になるので、、

ちなみに、今後はnetworkxのメインの機能であるグラフの解析APIや、

グラフを可視化する際のレイアウト決定アルゴリズムを説明する予定です。





  1. もちろん、グラフとノード、エッジを同時に作成する方法もありますが、基本はグラフ作成後にノード追加です。 



  2. 単純グラフではないグラフを作成したい場合、MultiGraphを使用する必要があります。 



  3. Graphvizも利用できます。