NetworkX 利用ノート

本稿では Python のグラフライブラリーである NetworkX のインストール方法、動作確認、簡単なグラフアルゴリズムの利用例、グラフのイメージ化方法について記す。余裕があれば、高級なグラフアルゴリズムの応用例をいくつか示したい。

本稿でのグラフとは、計算機科学の教科書に書いてあるような、ノードとエッジの集合うんぬんのグラフである。変数と関数のとる値を座標平面にプロットした曲線ではない。そちらについては Matplotlib のほうが相応しい。

• セットアップ
  • NetworkX をインストールする
  • インストールの成功を確認する
• NetworkX を利用する
  • 基本的なコードの書き方を習得する
    • Dijkstra 法による最短経路
    • グラフィックを描画する
• 連結成分
  • 強連結成分
  • その他の連結成分
• トポロジカルソート
  • 基本事項
  • 辞書式トポロジカルソート
• 最小全域木
  • 問題の背景
  • 関数 nx.minimum_spanning_tree の実行およびデータの取得
• 最短経路
  • 共通ルール
  • Dijkstra 法による最短経路探索関数
  • 負のエッジの重みを許す最短経路探索関数
  • A* アルゴリズムによる最短経路探索関数
• マッチング
  • 極大マッチング
  • 最小極大マッチング
  • 最大マッチング
• オイラー閉路
  • ドラクエ 7 最適基本職習得キャリアパスを計算する
    • 関数 nx.is_eulerian
    • 関数 nx.eulerian_circuit
• 連結度
  • 辺連結度と点連結度
  • 最小カットセット
• ネットワークフロー
  • 最大フロー
    • お手軽な手法
    • 残余ネットワーク計算アルゴリズムを指定する手法
  • 最大フロー最小カット
  • 最小コストフロー
    • 最大フロー最小コスト
    • 関数 nx.network_simplex
• グラフを描画する
  • Matplotlib との連携
  • PyGraphviz との連携
  • pydot との連携
    • Python3 動作版 pydot のセットアップ
    • パッケージ nxpydot のセットアップ
    • モジュール networkx.nx_pydot の関数の動作確認
  • 形状別描画手引
    • 完全グラフを正多角形の頂点に描画したい
    • 木を描画したい
• グラフ用語と実装要素の対応早見表

Note

• OS

  • Windows 7 Home Premium x64 SP1

  • Windows 10 Home x64

• 本稿において、利用した各パッケージのバージョンは次のとおり。

  • Python: 3.4.1, 3.5.0, 3.5.2, 3.6.4, 3.6.5.

  • NetworkX: 1.9.1, 2.0.dev20151014034116, 1.11, 2.1.

  • Nose: 1.3.4, 1.3.7

  • Numpy: 1.9.1, 1.10.0, 1.11.1

  • Matplotlib: 1.4.2, 1.4.3, 1.5.1, 2.2.2.

関連リンク

NetworkX

公式サイト。インストール方法から基本的な利用方法、応用等が文書化されている。

関連ノート

• Nose 利用ノート [obsolete]

• Matplotlib 利用ノート