networkxによるグラフアルゴリズム実装

グラフとして考えると解ける問題

グラフは、点(ノード)と線(エッジ)だけでできた構造です。素朴に見えて、実務の多くの問題がこの形に落ちます。

• リソースの依存関係 — どのリソースがどれに依存し、どの順で作るべきか
• モジュールの参照関係 — 循環参照が起きていないか
• タスクの前後関係 — 並列に実行できるものはどれか

networkx は、[[Python]] でこれらを扱うライブラリです。自前でノードとエッジを管理する代わりに、既存のアルゴリズムをそのまま呼べるのが価値です。

import networkx as nx

g = nx.DiGraph()                          # 有向グラフ
g.add_edge('vpc', 'subnet')               # vpc -> subnet(subnetがvpcに依存)
g.add_edge('subnet', 'instance')
g.add_edge('vpc', 'security_group')

print(list(nx.topological_sort(g)))
# ['vpc', 'subnet', 'security_group', 'instance']

有向か無向かを最初に決める

この選択を間違えると、以降のアルゴリズムがすべて意味を失います。

依存関係を Graph(無向)で作ると、トポロジカルソートも循環検出も使えません。逆に「単に関連している」だけの関係を DiGraph にすると、向きの意味を後から説明できなくなります。

よく使うアルゴリズム

nx.is_directed_acyclic_graph(g)     # 循環が無いか(依存関係の健全性)
nx.topological_sort(g)              # 依存を満たす実行順
nx.descendants(g, 'vpc')            # vpc を消すと影響が及ぶ範囲
nx.shortest_path(g, 'a', 'b')       # 2点間の最短経路
nx.weakly_connected_components(g)   # 孤立した塊の検出
list(nx.simple_cycles(g))           # 循環している経路そのもの

循環検出は「エラーを出す」だけでなく「どこが循環しているか」まで返せるのが実用上の差です。is_directed_acyclic_graph が False を返したときに simple_cycles を呼べば、直すべき箇所が特定できます。

描画位置の計算

依存関係を図にするとき、ノードをどこへ置くかも networkx が計算できます。

pos = nx.spring_layout(g, seed=42)     # 力学モデル
pos = nx.multipartite_layout(g, subset_key='layer')  # 階層ごとに並べる

spring_layout は [[力学モデルによるグラフレイアウト]] の実装で、エッジをばね・ノード同士を反発する電荷とみなして安定位置を求めます。seed を固定しないと実行のたびに配置が変わります — 図を再生成するたびに全く違う絵になり、差分が読めなくなるため、再現性が要る用途では必ず固定します。

依存関係のように層が明確な構造では、力学モデルより階層レイアウトのほうが読めます。図の目的で選び分けます。

実務での注意点

• 規模で性能が変わる — 数千ノードまでは素直に動きますが、最短経路や中心性の計算は組み合わせ爆発します。全ペアを求める関数は件数を先に見積もります
• ノードIDは文字列で統一する — 数値と文字列が混ざると同じ名前に見えるノードが別物になります
• 属性はノード・エッジに持たせられる — g.add_node('vpc', kind='network') のように付けておくと、フィルタや色分けで使えます
• 可視化は別の道具に任せてよい — 位置計算だけ networkx で行い、描画はフロントエンドへ渡す構成が扱いやすくなります

関連技術とのつながり

• [[Python]] — 実装言語。データ処理の流れにそのまま組み込める
• [[グラフデータベース]] — 同じ構造を永続化して問い合わせる側。networkx は計算用の一時表現
• [[力学モデルによるグラフレイアウト]] — spring_layout が実装しているアルゴリズム
• [[IaC]] — リソース依存関係の解析はこのライブラリの典型的な用途
• [[Terraformのstate解析とimportブロック応用]] — state から取り出した依存関係をグラフとして扱う

Q: 依存関係を表すのに適したnetworkxの型はどれ?
- [ ] `Graph`(無向グラフ)
- [x] `DiGraph`(有向グラフ)
- [ ] どちらでもよい
解説: 無向で作るとトポロジカルソートも循環検出も使えません。向きに意味があるかで最初に決めます。

Q: 循環検出で `is_directed_acyclic_graph` が False を返したあとに使うと有効なのはどれ?
- [x] `simple_cycles`(循環している経路そのものを返す)
- [ ] `shortest_path`
- [ ] `spring_layout`
解説: 「循環がある」だけでなく「どこが循環しているか」まで分かると、直すべき箇所が特定できます。

Q: `spring_layout` で `seed` を固定する理由はどれ?
- [ ] 計算が速くなるから
- [x] 固定しないと実行のたびに配置が変わり、図の差分が読めなくなるから
- [ ] ノードの重なりを防ぐため
解説: 力学モデルは初期配置に依存します。再現性が要る用途では必ず固定します。