# NetworkX と python-igraph のローカル最短経路・グラフ構築実測

依頼: req-20261022-065 / 題材ID: networkx-igraph-local-hikaku
測定日: 2026-11-16（Asia/Tokyo）。実行時刻のUTC生値は raw.json の started_at_utc / finished_at_utc。

## 判断と範囲

このMacの砂場で両方をCPU実行でき、最短経路の結果と処理時間の比較軸が成立した。
NetworkX 3.6.1（このMacに導入済み）と python-igraph 1.0.0（C コア 1.0.0）を実際に呼び出した。外部の速度表の転載は使っていない。
鍵、ログイン、有料API、買い物は不要。igraph はこのMacに入っていなかったため、`pip install --target` で一時ディレクトリに取得して測り、測定後に削除した（取得にPyPIへの通信を使った）。
公開・X投稿・git commitは行っていない。GPU・Metal・音声・Bluetoothは使っていない（どちらもCPUのみ）。

測定環境は macOS 27.2.1 / arm64 / CPython 3.14.10 / Apple M4 Pro / 論理CPU数 12。
NetworkX は純Python実装、igraph はCで書かれたコア。実装言語の違いを含む比較であり、アルゴリズムだけの比較ではない。

## 入力と方法

入力は再実行コードの make_graph() が作る人工グラフ（無向・重み付き・20000頂点・99983辺）。
リング（i と i+1）で連結を保ち、整数演算のLCGで80000本のランダム辺を足した（重複・自己ループは除外）。重みは 1〜100 の整数。
乱数モジュール・外部ファイル・日付は使わない。辺リストのSHA256は raw.json の input.edge_list_sha256。
グラフは計時の外で作り、NetworkX と igraph に同じ辺リスト・同じ重みを渡した。

比較した操作は4つ（1バッチの回数 loops を含む）。

| 操作 | NetworkX | igraph | 1バッチ |
|---|---|---|---|
| bfs-distances | single_source_shortest_path_length | Graph.distances(source) | 10頂点から全頂点への距離 ×1 |
| dijkstra-distances | single_source_dijkstra_path_length(weight) | Graph.distances(source, weights) | 10頂点から全頂点への重み付き距離 ×1 |
| dijkstra-pair-path | dijkstra_path(s, t, weight) | get_shortest_paths(s, to=t, weights) | 10組の経路 ×5回 |
| build-graph | Graph + add_weighted_edges_from | Graph(n, edges) + es['weight'] | 辺リストから構築 ×3回 |

始点・終点は固定のLCG（種777）で決めた10組（raw.json の conditions.sources / targets）。
1バッチのウォームアップ後に5バッチを計時した（計40バッチ・ウォームアップ8バッチ）。
試行ごとにNetworkX・igraphの実行順を交互に切り替えた。perf_counter_ns で整数ナノ秒を取得し、計時中のみ循環GCを止めた。
グラフ生成・import・検証・ハッシュは計時に含まない（build-graph は構築そのものを計時）。結果は呼び出しごとに捨てた。

## 結果の一致確認（計時の外）

- bfs-distances: 10始点×20000頂点の距離が2ライブラリで完全一致した。
- dijkstra-distances: 同じく完全一致した（整数重みなので浮動小数の誤差の影響を受けない）。
- dijkstra-pair-path: 10組すべてで経路の総重みが一致し、始点・終点も正しかった。頂点列も10組すべて同一だった（同点の経路がある場合は別になりうるが、この入力ではそうならなかった）。
- build-graph: 頂点数・辺数・重みの合計が一致した。

## 結果

生値は trials[].elapsed_ns と loops。台帳の全40 assertion はこの整数生値を直接指し、identity / rounding=0 / tolerance=0 を使う。
summaries[] の中央値は参考の派生値で、台帳の根拠には使っていない。
この環境では、4操作すべてで igraph の処理時間が NetworkX より短かった。バッチ中央値の比は、bfs-distances で約6.8倍、dijkstra-distances で約12.2倍、dijkstra-pair-path で約12.8倍、build-graph で約7.1倍（raw の trials から再計算できる）。
倍率・順位は、このCPU・この人工グラフ・この版に限る。揺れもあり、たとえば dijkstra-pair-path の NetworkX は最小約26.9億ns・最大約37.4億ns（5試行、原因は調べていない）。

## 範囲と限界

- 測ったのは、このMacのCPUで、人工グラフ1つ（20000頂点・約10万辺）の単一始点距離・経路探索とグラフ構築の処理時間と、結果の一致だけ。
- 他のグラフ規模・疎密・有向グラフ・全点対最短経路・中心性やコミュニティ検出など他のアルゴリズム、メモリ使用量、起動・import時間、実データ、他OS・他CPUは測っていない。
- NetworkX を他のバックエンド（nx-cugraph など GPU 系や並列系）に切り替えた構成は測っていない。igraph も既定の単スレッド呼び出しのみ。
- 外部推論や機械学習は使っていない。APIの使いやすさ・機能の広さ・品質は測っていない。
- パッケージのバージョンは dependencies.json に保存した。ホイールのハッシュは固定していない。
- 同じ秒数でも別の環境で再現するとは限らない。再実行: networkx-igraph-local-2026-11-16-req065-a1-replay.txt（macOS arm64・CPython 3.14・NetworkX が入っていること。igraph が無ければPyPIへ通信して一時取得する）。
- 公式ページの記述は転記していない。公式リポジトリ: https://github.com/networkx/networkx / https://github.com/igraph/python-igraph
