Press "Enter" to skip to content

NetworkX におけるグラフの実装を覗いてみた

NetworkX の使い方がいまいちピンと来ず、そもそも NetworkX がグラフという抽象概念をどうやってコードに落とし込んでいるのか気になってしまったのでソースを読んで見ました。

NetworkX ソース : https://github.com/networkx/networkx

グラフの概念を定義するグラフクラス

まず NetworkX は

  • グラフは Graph クラスや DiGraph クラスのインスタンスとして実体が定義される
  • ノード・エッジはそのインスタンス変数として保持される

となっています。これは実際に NetworkX を使ったことがあるならなんとなく気がついていると思います。

グラフのクラスとして使えるもの

NetworkX では「グラフ」に対応するクラスが複数用意されており

  • Graph()
  • DiGraph()
  • MultiGraph()
  • MultiDiGraph()
  • OrderedGraph()

があります。

Graph() と DiGraph() はそれぞれ 無向グラフ有向グラフ になります。

MultiGraph() と MultiDiGraph() は 多重無向グラフ多重有向グラフ になります。多重グラフとは 2つのノード間にエッジが並列に2本以上あるようなグラフです。実は最初の Graph() と DiGraph() は単純グラフであることが前提です。

最後の OrderedGraph() は Wikipedia の記事(英語) に説明があるように、ノードに順序(親・子の関係)が定義されているグラフになります。

ノードの実体

Graph クラスについて見ていったところ、ノードは”_node” というインスタンス変数(dictionary形式) における「キー」として、その存在が定義されている ようです。そのキーに対する値は、ノードのに対する属性情報(dictionary形式)となっています。

エッジの実体

同じく Graph クラスについて見ていきました。エッジは”_adj” というインスタンス変数が隣接行列のようなものとして機能することで、その存在が定義されている ようです。adj は adjacent (隣接)の略です。

この _adj は厳密には隣接行列(多重配列)ではなく、まず多重 dictionary となっています。さらに隣接行列ではそれぞれの要素は 0 か 1 の値を取りますが、 _adj はエッジが存在する部分のみそのエッジの属性情報となる dictionary が格納されており、エッジが存在しない部分についてはそもそもキーが存在しません。

ノードを追加するという操作

上で説明したことがわかれば明らかなことかもしれませんが、ノードを追加する操作は

  • _node に新たにノードキーを追加し、それに対する値として空の dictionary を割り当てる(もしもユーザがノードの定義と一緒に属性情報も渡せば、それが割り当てられる)
  • _adj に新たにノードのキーを追加し、それに対する値として空の dictionary を割り当てる(つまり隣接するノードが無いということ)。

となります。

エッジを追加するという操作

エッジを追加する操作は

  • もしも _node のキーに無いノードが含まれていたら、 先程のノードの追加操作を行う
  • _adj に追加するエッジとなるキーの組み合わせを追加し、それに対する値として空の dictionary を割り当てる(ユーザがエッジの定義と一緒に属性情報も渡せば、それが割り当てられる)

となります。

とまぁここまで書きましたが、実は今一番気になっているのは NetworkX におけるグラフの描画なので次は描画について調べようかなと思います。

Be First to Comment

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です