友だちPython ep9. networkx vol.2
はじめに
友だちPython シリーズのご紹介
友だちPython シリーズは、Python の小ネタを短文でお届けします。
小さなエピソードを重ねてPythonと仲良しになれたら、と願ってシリーズ名を付けました。
話題
Pythonによる実務で役立つ最適化問題100+ (1)
書籍「Pythonによる実務で役立つ最適化問題100+ (1)」（朝倉書店）をご紹介いたします。
この書籍シリーズは、いわゆる「最適化問題」について、コードを写経しつつ、基礎から学べる良書です。
数式とPythonコード中心の硬派な一冊です。
対象の書籍は３巻構成の第１巻（初版第１刷）です。
この記事は networkx と 私の戯れの記録です。
記事中のイラストは「いらすとや」さんからお借りしました。
ありがとうございます！
今回の友だち
■ networkx （ねっとわーくえっくす）
「グラフ理論」をビジュアル面と最適化面でサポートする精鋭です。
NetworkX 公式サイトの Gallery ページをご覧ください。
話題の概要
第４章「最小木問題」の「4.4 networkXの利用」で 無向グラフの最小木を「スパイ仕立てのストーリー」で学びました。
実行環境
・networkx ver. 2.8.8
遊んだ内容
networkx を用いて、貪欲解法とPrim法による「すべてのスパイ（頂点）と交信して、かつ、交信コストを最小化する司令伝達経路（辺）」を算出し、グラフ図を描画します。
■ 遊び方
書籍の67ページのストーリーおよびコードをお借りして、拡張版コードを作りました。
### インポート
import networkx as nx
import randomスパイを配置してグラフを作成します。
初期値設定の交信コスト範囲 cost_lower, cost_upper の数値を変更すると、最小木の形状が変わります！
### スパイグラフの作成
## 初期値設定
random.seed(1)
cost_lower, cost_upper = 1, 3 # 交信コストの下限と上限
com_cost = [random.randint(cost_lower, cost_upper) for _ in range(7)]
## グラフの作成
# グラフの初期化
G = nx.Graph()
# グラフに辺と重みを設定
G.add_edge('Arigator', 'WhiteBear', weight=com_cost[0])
G.add_edge('Arigator', 'Bull', weight=com_cost[1])
G.add_edge('Bull', 'WhiteBear', weight=com_cost[2])
G.add_edge('Bull', 'Shark', weight=com_cost[3])
G.add_edge('WhiteBear', 'Condor', weight=com_cost[4])
G.add_edge('WhiteBear', 'Shark', weight=com_cost[5])
G.add_edge('Shark', 'Condor', weight=com_cost[6])
# グラフの仮描画
# positionの作成
pos = nx.spring_layout(G, seed=123)
# 辺のラベル＝重みの取得
edge_labels = {(i, j): w['weight'] for i, j, w in G.edges(data=True)}
# 頂点と辺の描画
nx.draw(G, pos=pos, with_labels=True, node_color='lightblue')
# 辺のラベル＝重みの描画
nx.draw_networkx_edge_labels(G, pos=pos, edge_labels=edge_labels);【実行結果】
５人のスパイ（頂点）・交信経路（辺）・交信コスト（辺の重み）が明らかになりました。
コスト最小経路の行く末はいかに・・・！？
スパイグラフの描画関数を定義します。
もちろん暗号化しています（そんな訳はない）。
### スパイグラフの描画関数の定義
def draw_spygraph(G, edge_list, title):
# minimum_spanning_treeで取得した経路情報の表示
print(f'最小木：{title}の司令交信ルート\n', edge_list)
# 辺のラベル＝重みの取得
edge_labels = {(i, j): w['weight'] for i, j, w in G.edges(data=True)}
# positionの作成
pos = nx.spring_layout(G, seed=123) # バネ的レイアウト seed付与で形状固定可能
# pos = nx.circular_layout(G) # 参考：円状レイアウト
## 描画処理
# 最小木の辺の描画
nx.draw(G, pos=pos, with_labels=False, edgelist=edge_list,
edge_color='tomato', width=8, alpha=0.5)
# 頂点と辺の描画
nx.draw(G, pos=pos, with_labels=True, node_color='lightblue')
# 辺のラベル＝重みの描画
nx.draw_networkx_edge_labels(G, pos=pos, edge_labels=edge_labels)
plt.show()【実行結果】なし
貪欲解法で交信コスト最小の伝達経路を探ります。
ここで networkx のアルゴリズムの登場です！
minimum_spanning_tree() が最小木のグラフを算出する関数です。
アルゴリズム引数になにも与えないと、デフォルトアルゴリズムの貪欲解法が選択されます。
### スパイグラフの描画 貪欲解法
# 最小木の経路（辺）情報の取得：アルゴリズムKruskal法（貪欲解法）
edge_list = list(nx.minimum_spanning_tree(G).edges())
# 描画
draw_spygraph(G, edge_list, '貪欲解法')【実行結果】
「nx.minimum_spanning_tree(G).edges()」で取得したグラフGの最小木経路です。
赤い経路の集まりが最小木です。
赤い辺上の数＝コストの合計は$${5}$$です。
続いてPrim法で交信コスト最小の伝達経路を探ります。
minimum_spanning_tree() の引数 algorithm='prim' を指定します。
### スパイグラフの描画
# 最小木の経路（辺）情報の取得：アルゴリズムPrim法
edge_list = list(nx.minimum_spanning_tree(G, algorithm='prim').edges())
# 描画
draw_spygraph(G, edge_list, 'Prim法')【実行結果】
「nx.minimum_spanning_tree(G, algorithm='prim').edges()」で取得したグラフGの最小木経路です。
貪欲解法と違うようですね！
図を見てみましょう。
赤い辺上の数＝コストの合計は$${5}$$です。
最小コストに複数の解があり、アルゴリズムによって選択する解が変わるようです。
いずれのアルゴリズムも高いコスト$${2, 3}$$の経路を避けています！
実はアルゴリズムにもう１つ、 Boruvka法（algorithm='boruvka'）があります。試してみてね✨
【Pythonの公式】
数学的要素＋グラフィカル要素＝楽しさ無限大
計算＆可視化を簡単なコードで実践できて、とても楽しいです！
みなさんも最適化問題を存分に堪能してください！
幸運を祈る🍀
おわり
ブログの紹介
noteで５つのシリーズ記事を書いています。
ぜひ覗いていってくださいね！
１．のんびり統計
統計検定２級の問題集を手がかりにして、確率・統計をざっくり掘り下げるブログです。
雑談感覚で大丈夫です。ぜひ覗いていってくださいね。
統計検定２級公式問題集CBT対応版に対応しています。
２．実験！たのしいベイズモデリングをPyMC Ver.5で
書籍「たのしいベイズモデリング」の心理学研究に用いられたベイズモデルを PyMC Ver.5で描いて分析します。
この書籍をはじめ、多くのベイズモデルは Ｒ言語＋Stanで書かれています。
PyMCの可能性を探り出し、手軽にベイズモデリングを実践できるように努めます。
身近なテーマ、イメージしやすいテーマですので、ぜひぜひPyMCで動かして、一緒に楽しみましょう！
３．RとStanではじめる心理学のための時系列分析入門 を PythonとPyMC Ver.5 で
書籍「RとStanではじめる心理学のための時系列分析入門」の時系列分析トピックを PythonとPyMC Ver.5で取り組みます。
豊富なテーマ（お題）を実践することによって、PythonとPyMCの基礎体力づくりにつながる、そう信じています。
日々、Web検索に勤しみ、時系列モデルの理解、Pythonパッケージの把握、R・Stanコードの翻訳に励んでいます！
このシリーズがPython時系列分析の入門者の参考になれば幸いです🍀
４．Python機械学習プログラミング実践記
書籍「Python機械学習プログラミング PyTorch & scikit-learn編」を学んだときのさまざまな思いを記事にしました。
この書籍は、scikit-learn と PyTorch の教科書です。
よかったらぜひ、お試しくださいませ。
５．データサイエンスっぽいことを綴る
統計、データ分析、AI、機械学習、Python のコラムを不定期に綴っています。
「統計」「Python」「数学とPython」「R」のシリーズが生まれています。
最後までお読みいただきまして、ありがとうございました。