ソフトウェア設計とグラフ理論

この記事は LLM と連携して作成しました

ソフトウェア設計を議論するとき、モジュール間のつながり、状態遷移、依存関係がよく出てくる。これらの多くは、実際にはグラフとして表現できる。

この記事では、ソフトウェア設計をグラフとして捉えるとどう理解できるかをまとめる。

ソフトウェア設計をグラフとして見る

グラフは頂点と辺からなる抽象表現だ。ソフトウェア設計に当てはめると、頂点をモジュール、クラス、サービス、状態、ジョブなどに見立て、辺を依存、遷移、通信、参照、配送のような関係として表現できる。

設計対象	頂点	辺	よく使う見方
モジュール間の依存	パッケージ、ライブラリ、サービス	import、参照、利用	DAG、強連結成分、トポロジカルソート
呼び出し関係	関数、メソッド、エンドポイント	call、invoke	到達可能性、支配関係、影響範囲
状態遷移	状態	遷移条件	到達不能状態、閉路、終端状態、オートマトン
データパイプライン	ジョブ、トピック、テーブル	入出力、依存	実行順序、再計算範囲、ボトルネック
システム構成	サービス、ノード、サブネット	通信経路	カット、経路長、単一障害点

グラフ理論を知っているち抽象の理解を深めることができ、構造的な理解を助ける。

グラフ理論が効く代表的な場面

1. 循環依存を見つける

依存関係を DAG として保ちたい層構造では、閉路の有無が設計健全性の近似指標になる。

build 順序を決めたい
レイヤー違反を検出したい
package の責務分割が崩れていないか見たい

この場合は、トポロジカルソートで順序を作れるか、強連結成分を計算したときに複数頂点の塊が出るかを見るとよい。

トポロジカルソートは、依存関係を壊さないように頂点を並べる方法だ。A が B に依存するなら、並び順では B が A より先に現れる。実務では、モジュールの build 順序、バッチ処理の実行順、テーブル作成順の確認などにそのまま応用できる。

ポイントは、トポロジカルソートが使えるのは閉路がないときだけという点だ。app -> auth -> infra -> app のように循環していると順序を一意に定められない。この崩れを CI の失敗として早めに表面化しやすくなる。

2. 変更影響範囲を見積もる

あるモジュールを変更したとき、どのコンポーネントへ影響が伝播するかは、逆向きの辺をたどると整理しやすい。呼び出し関係や依存関係を逆グラフにして到達可能な頂点を列挙すれば、レビュー対象やテスト候補を絞りやすい。

ただし、設定ファイル、プラグイン、動的ロードへの依存が強い実装では、静的解析だけで全体を捉えにくい。欠落が出ることもある。

3. 状態機械の欠陥を見つける

ワークフローやジョブ制御では、状態遷移図をグラフとして見ると次の欠陥を見つけやすい。

到達不能状態
失敗時に戻れない遷移
終了できない閉路
本来は排他的であるべき遷移の混在

4. ボトルネックや単一障害点を考える

分散システムでは、すべての通信が 1 つのサービスやキューに集中していないかをグラフで見ると、単一障害点や過剰なハブを発見しやすい。ここでは厳密な数理最適化まで行かなくても、入次数・出次数の偏りを見るだけで役に立つことが多い。

グラフの表現方法

依存グラフの例

依存関係を有向グラフとして書くと、設計上の前提がかなり明確になる。

flowchart LR
  ui[UI] --> app[Application]
  app --> domain[Domain]
  app --> auth[Auth]
  auth --> infra[Infrastructure]
  domain --> infra

この図で重要なのは見た目ではなく、「辺の向きが何を意味するか」だ。ここでは A --> B を「A が B に依存する」と定義している。向きの定義を曖昧にすると、解析結果も議論もぶれやすい。

隣接行列による表現

上の依存グラフは図として見るだけでなく、隣接行列として数値化できる。頂点の並びを UI, Application, Domain, Auth, Infrastructure とし、 $A_{ij} = 1$ を「頂点 $$i$$ から頂点 $$j$$ へ辺がある（ $$i$$ が $$j$$ に依存する）」と定める。

先ほどの依存グラフをこの定義で隣接行列にすると、次のようになる。

From \ To	Application	Domain	Auth	Infrastructure
UI	1	0	0	0
Application	0	1	1	0
Domain	0	0	0	1
Auth	0	0	0	1
Infrastructure	0	0	0	0

A = \begin{pmatrix} 0 & 1 & 0 & 0 & 0 \\\\ 0 & 0 & 1 & 1 & 0 \\\\ 0 & 0 & 0 & 0 & 1 \\\\ 0 & 0 & 0 & 0 & 1 \\\\ 0 & 0 & 0 & 0 & 0 \end{pmatrix}

隣接行列の利点は、計算に乗せやすいことだ。たとえば $$A^2$$ を見ると長さ 2 の経路数を数えられるし、到達可能性の判定や推移閉包の計算にもつなげやすい。一方で、実際のソフトウェアの依存グラフは疎であることが多いので、大規模な解析では隣接リストのほうがメモリ効率はよい。

状態遷移図と隣接行列

状態遷移図でも、隣接行列はそのまま使える。違いは、頂点をモジュールではなく状態として読むことだ。たとえば、ジョブの状態が Ready, Running, Succeeded, Failed の 4 つあるとする。

flowchart LR
  ready[Ready] --> running[Running]
  running --> succeeded[Succeeded]
  running --> failed[Failed]
  failed --> ready

頂点の順番を Ready, Running, Succeeded, Failed とすると、隣接行列 $$A$$ は次のようになる。

A = \begin{pmatrix} 0 & 1 & 0 & 0 \\\\ 0 & 0 & 1 & 1 \\\\ 0 & 0 & 0 & 0 \\\\ 1 & 0 & 0 & 0 \end{pmatrix}

$A_{ij} = 1$ は「状態 $$i$$ から状態 $$j$$ へ 1 回の遷移で進める」ことを意味する。 $$A^2$$ の $$(i,j)$$ 成分は「2 回の遷移で到達する経路数」を表す。たとえば $$A^2$$ を計算すると 1 行 3 列（Ready → Succeeded）の値が 1 になる。これは Ready -> Running -> Succeeded という経路が 1 本あることを示す。同様に 1 行 4 列（Ready → Failed）も 1 なので Ready -> Running -> Failed も 2 ステップで到達できる。この計算で、Failed -> Ready -> Running のような再試行ループの存在も機械的に検出できる。

状態数が増えると図だけでは追いにくくなるが、行列にすると到達性や閉路の有無を計算で扱いやすくなる。

固有値が示すもの

隣接行列を数値として扱えるようになると、固有値がグラフの構造を要約した指標として使えるようになる。ここでは設計の議論に結びつきやすいものを挙げる。

1. 固有値がすべて 0 なら閉路がない

有向グラフが DAG であることと、隣接行列が冪零（ある $$k$$ で $$A^k = O$$ ）であることは同値で、このとき固有値はすべて 0 になる。「長さ $$k$$ の経路数」を表す $$A^k$$ が最終的にゼロ行列になる、と読むと直感的だ。閉路があれば経路をいくらでも伸ばせるので、ゼロ行列にはならない。

先ほどの依存グラフの $$A$$ を実際に累乗すると、 $$A^3$$ では UI から Infrastructure への長さ 3 の経路が 2 本（Domain 経由と Auth 経由）残り、 $$A^4 = O$$ になる。つまり最長経路の長さは 3 で、循環依存はない。

冪零になるまでの回数（冪零指数）は「最長の依存チェーンの長さ + 1」に対応するので、レイヤーの深さの目安としても読める。

2. スペクトル半径は経路数の増え方を表す

固有値の絶対値の最大値をスペクトル半径 $\rho(A)$ と呼ぶ。これは経路数が増えていく速さの指標で、長さ $$k$$ の経路の総数はおおよそ $\rho(A)^k$ のオーダーで増える。

$\rho(A) = 0$ : DAG（経路は有限）
$\rho(A) = 1$ : 閉路はあるが、経路数は増減しない
$\rho(A) > 1$ : 経路数が指数的に増える

先ほどのジョブ状態機械の $$A$$ は Ready -> Running -> Failed -> Ready という長さ 3 の閉路を 1 本持ち、特性多項式は $\lambda^4 - \lambda = \lambda(\lambda^3 - 1)$ 、固有値は 0 と 1 の 3 乗根になる。したがって $\rho(A) = 1$ で、実際に $$A^4 = A$$ と周期 3 で循環する。再試行ループが 1 本だけの素直な状態機械であることが、値としても表れている。

ここに別の再試行経路やタイムアウト遷移が加わって閉路同士が絡み合うと $\rho(A) > 1$ になり、たどるべき経路が状態数の割に爆発していることを意味する。網羅的なテストケース設計が現実的かどうかの判断材料になる。

3. 固有ベクトルは「重要な頂点」を示す

隣接行列の主固有ベクトル（最大固有値に対応する固有ベクトル）の各成分は、固有ベクトル中心性と呼ばれる重要度指標になる。「重要な頂点から参照されている頂点は重要」という再帰的な定義を、固有値問題として解いたものだ。PageRank も同じ発想の変種で、依存グラフに当てはめれば「壊すと影響が大きい共通基盤」を定量化できる。

ただし DAG の場合、固有値がすべて 0 になるため、この指標は退化して使えなくなる。PageRank が減衰係数（ランダムジャンプ）を入れているのは、この種の退化を避けるためだ。依存グラフで重要度を測りたいなら、PageRank を使うか、素直に逆グラフ上の到達可能頂点数を数えるほうが実務的なケースは多い。

4. ラプラシアンの固有値はモジュール分割に効く

辺の向きを落として無向グラフとして見ると、ラプラシアン行列 $$L = D - A$$ （ $$D$$ は次数の対角行列）の固有値が使える。

固有値 0 の重複度は連結成分の数と一致する
2 番目に小さい固有値（代数的連結度、Fiedler 値）は、グラフがどれだけ分割しにくいかを表す

Fiedler 値が小さいということは、少ない辺を切るだけでグラフを 2 つに分けられるということだ。対応する固有ベクトル（Fiedler ベクトル）の符号で頂点を分けると、実際の分割候補が得られる。これがスペクトラルクラスタリングで、モノリスを分割するときに「どこで切ると依存の断面が細いか」を機械的に探す用途に使える。

もちろん、出てきた分割がドメイン上意味のある境界とは限らない。あくまで人間が引く bounded context の候補を出す補助として扱うのがよい。

固有値を見るときの注意

固有値はグラフ全体を数個の数に圧縮した指標なので、「何かがおかしい」ことは示せても「どこを直すべきか」までは示さない。 $\rho(A) > 1$ だと分かったら、結局は強連結成分を計算して具体的な閉路を特定することになる。全体の傾向を継続的に観測する指標として使い、個別の修正は従来のグラフアルゴリズムに任せる、という分担が現実的だ。

図と擬似コードで見る最小例

ここでは、モジュール依存を簡単な有向グラフとして表現し、循環依存の有無と実行順序を確認する。

1. 正常な依存関係で順序を確認する

flowchart LR
  ui[UI] --> app[Application]
  app --> domain[Domain]
  app --> auth[Auth]
  auth --> infra[Infrastructure]
  domain --> infra

このグラフに対してトポロジカルソートをかける擬似コードは次の通りだ。

dependencies = {
  UI: [Application],
  Application: [Domain, Auth],
  Auth: [Infrastructure],
  Domain: [Infrastructure],
  Infrastructure: []
}

order = topological_sort(dependencies)
print(order)

結果は Infrastructure, Auth, Domain, Application, UI のようになる。Auth と Domain の前後は入れ替わることがあるが、どちらも Infrastructure より後、Application より前でなければならない。この結果は、「下位層を先に用意し、その上に上位層を積み上げる」という設計意図と整合している。

2. 循環依存を入れて失敗を確認する

Infrastructure -> Application の依存を追加して、閉路をわざと作る。

flowchart LR
  ui[UI] --> app[Application]
  app --> domain[Domain]
  app --> auth[Auth]
  auth --> infra[Infrastructure]
  domain --> infra
  infra --> app

擬似コードでは、単に依存を 1 本追加するだけでよい。

dependencies = {
  UI: [Application],
  Application: [Domain, Auth],
  Auth: [Infrastructure],
  Domain: [Infrastructure],
  Infrastructure: [Application]
}

order = topological_sort(dependencies)
if order cannot be built:
  print("cycle detected")

Application -> Auth -> Infrastructure -> Application という閉路があるため、順序を最後まで確定できない。実務では、こうした検査を CI に入れておくと、設計の崩れをレビュー前に検出しやすい。

3. 変更影響を逆グラフで見る

Infrastructure から逆向きにたどると、影響候補は次のように広がる。

flowchart RL
  infra[Infrastructure] --> auth[Auth]
  infra --> domain[Domain]
  auth --> app[Application]
  domain --> app
  app --> ui[UI]

1
2
3

reverse_graph = reverse_edges(dependencies)
affected = reachable_nodes(from = Infrastructure, graph = reverse_graph)
print(affected)

結果は Infrastructure, Auth, Domain, Application, UI のようになる。これは Infrastructure の変更が、最終的には上位層全体の確認につながる可能性を示している。もちろん実際の影響は公開 API の互換性や実行時の経路に依存するが、設計レビューでの初期見積もりとしては十分役に立つ。

実務へ持ち込むときの見方

グラフ理論を設計へ持ち込むときは、難しいアルゴリズムを覚えることより、次の順序で考えるほうが実務的だ。

何を頂点にするか決める
辺の意味を 1 種類ずつ定義する
期待する性質を決める
その性質を壊すパターンを検査する

たとえば、「レイヤードアーキテクチャを守りたい」なら、期待する性質は「循環依存がない」「下位層から上位層へ参照しない」になる。ここで必要なのは、巨大な図よりも、依存関係の抽出規則と違反判定のほうだ。

逆に、「処理遅延の原因を知りたい」なら、重み付きグラフや待ち行列のモデルが必要になる場合がある。つまり、グラフ化は万能ではなく、知りたい性質に合わせてモデルを選ぶ必要がある。

注意点

静的依存グラフは、リフレクション、動的 import、設定駆動の経路を取りこぼす場合がある
1 本の辺に複数の意味を混ぜると、解析結果の解釈が曖昧になる
巨大グラフをそのまま可視化しても、人間には読みにくい。責務単位で集約した粗いグラフから始めるほうがよい
グラフ上で近いことと変更リスクの高さを同一視しないほうがよい。公開 API の安定性や運用上の重要度についても別途見る必要がある

トラブルシュート

トポロジカルソートが失敗したら、閉路の一部だけでなく「なぜその依存が必要になったか」まで追う
可視化した図が複雑すぎるなら、package 単位から bounded context 単位へ粒度を上げる
変更影響が広すぎるなら、共通基盤に責務が集まりすぎていないかを見る
静的解析の結果と実行時挙動が違うなら、設定ファイル、プラグイン、生成コードの経路を別グラフとして扱う
CI へ入れるとノイズが多い場合は、まずは特定ディレクトリだけを対象にして検査規則を安定させる

参考

Dijkstra, E. W. “A note on two problems in connexion with graphs”. Numerische Mathematik, 1959
Kahn, A. B. “Topological sorting of large networks”. Communications of the ACM, 1962
Tarjan, R. E. “Depth-first search and linear graph algorithms”. SIAM Journal on Computing, 1972
Fiedler, M. “Algebraic connectivity of graphs”. Czechoslovak Mathematical Journal, 1973
Page, L., Brin, S., Motwani, R., Winograd, T. “The PageRank Citation Ranking: Bringing Order to the Web”. Stanford InfoLab, 1999
Chung, F. R. K. “Spectral Graph Theory”. American Mathematical Society, 1997