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

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

ソフトウェア設計を議論するとき、レイヤー、責務、結合度、状態遷移、依存関係のような言葉がよく出てくる。これらの多くは、実際にはグラフとして表現すると整理しやすい。

グラフ理論を使うと、設計の見た目をきれいにするだけではなく、循環依存の検出、変更影響範囲の見積もり、到達不能状態の発見、処理順序の決定のような実務上の判断を機械的に支えやすくなる。

この記事では、ソフトウェア設計をグラフとして捉えると何がうれしいかを整理し、依存関係の検証を図と擬似コードで追える最小例までまとめる。

結論

モジュール依存、呼び出し関係、状態遷移、データフローは、グラフとして扱える
設計レビューで重要なのは「きれいな図」より、頂点と辺の意味を明確に定義すること
循環依存の検出には強連結成分やトポロジカルソートが実用的に効く
変更影響の見積もりでは到達可能性が役立つ。ボトルネック分析では中心性やカットの考え方を使える場合がある
ただし、リフレクション、動的 import、設定駆動の分岐が多い実装では、静的グラフだけで全体像を断定しないほうが安全だ

前提

この記事は特定の言語や実行環境を前提にしない。コード片は考え方を伝えるための擬似コードであり、実際には任意の言語やツールへ読み替えられる。

対象読者: 設計レビューやアーキテクチャ整理をするときに、グラフ理論を実務へどう結びつけるか知りたい人
想定する題材: モジュール依存、状態遷移、データ処理順序の整理
ねらい: 実装テクニックではなく、設計上の見方をつかむこと

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

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

たとえば、次のような対応関係がある。

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

設計の現場では、グラフに落とした時点で見えてくる問題が多い。たとえば「下位レイヤーのはずのモジュールが上位 UI を参照している」「状態遷移図に戻れない状態がある」といったものだ。

小さな依存グラフの例

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

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

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

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

1. 循環依存を見つける

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

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

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

トポロジカルソートについて

トポロジカルソートは、依存関係を壊さないように頂点を並べる方法だ。A が B に依存するなら、並び順では B が A より先に現れる。つまり、「何を先に用意しないと次へ進めないか」を機械的に並べる操作だ。そう考えるとわかりやすい。

実務では、モジュールの build 順序、バッチ処理の実行順、テーブル作成順、画面初期化の順序確認などにそのまま応用できる。ポイントは、トポロジカルソートが使えるのは閉路がないときだけ、という点だ。もし app -> auth -> infra -> app のように循環していると、「どれを先に始めても別の何かが先に必要」という状態になり、順序を一意に定められない。

たとえば、社内システムを UI -> Application -> Domain -> Infrastructure の 4 層で分けることを考える。UI は Application を使い、Application は Domain を使い、Domain は Infrastructure を使う。このときトポロジカルソートの結果が Infrastructure, Domain, Application, UI のようになれば、「下位層を先に組み立てて、その上に上位層を載せる」という設計意図と一致していると読める。

逆に、ある日 Infrastructure から Application を参照し始めると、両者の間に循環ができる。この変化は import が 1 本増えただけでも、設計上は「下位層が上位層の都合を知ってしまった」という崩れのサインになりやすい。トポロジカルソートは、その崩れを build エラーや CI の失敗として早めに表面化しやすい。

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

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

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

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

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

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

設計書で状態図を描いて終わりにせず、どの状態からどこへ遷移できるかをコードやテストと突き合わせると、運用事故を減らしやすい。

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

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

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

ここでは、モジュール依存を簡単な有向グラフとして表現し、循環依存の有無と実行順序を確認する。実装言語には依存しないので、図を見ながら擬似コードとして読むだけでよい。

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

まず、依存関係を Mermaid で描くと次のようになる。

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]

考え方を擬似コードで書くと次の通りだ。

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
Martin, R. C. の依存関係の議論やレイヤー化の話は、グラフとして見ると整理しやすい。ただし実装時は言語仕様やビルドツールの制約も併せて確認したほうがよい