【上級者向け】依存関係の「循環参照」をグラフ理論で解く：再帰的探索によるデッドロックの完全検出
Microsoft Project（以下、MS Project）を用いた大規模プロジェクト管理において、WBS（Work Breakdown Structure）の自動生成や、外部システム（ERPやPLMなど）からタスク・依存関係をインポートする処理は、業務自動化の華である。
しかし、この自動化の裏には、極めて凶悪なトラップが潜んでいる。「循環参照（Circular Dependency）」である。
タスクAがタスクBに依存し、タスクBがタスクCに依存し、タスクCがタスクAに依存する――。このような依存関係の閉路（Loop）が1つでも混入すると、MS Projectの強力なスケジューリングエンジン（PERT/CPM計算エンジン）は、内部計算の無限ループに陥るか、最悪の場合、致命的な例外を投げてプロセスごとクラッシュする。
本稿では、MS ProjectのCOMオブジェクトが抱えるメモリ管理の限界を突破し、グラフ理論（DFS：深さ優先探索および3色着色アルゴリズム）を用いて、数千タスク規模のWBSから循環参照（デッドロック）を瞬時に、かつ100%安全に検出する「極限のVBAデバッグエンジン」を構築する。
—
1. MS ProjectのスケジューリングエンジンとCOMの限界
MS Projectにおけるタスク間のリンクは、`Task.Predecessors`（先行タスク）や`Task.Successors`（後続タスク）というCOMコレクションを介して表現される。
これをVBAから直接、逐次的に走査（Traverse）していく設計は、中堅エンジニアが最も陥りやすい過ちである。理由は2つある。
① COM境界往復による著しいパフォーマンス劣化
VBAからMS ProjectのCOMオブジェクト（`MSProject.Task`や`MSProject.TaskDependency`）にアクセスするたび、背後では「COMプロキシ/スタブ」を経由したプロセス間・コンテキスト間通信が発生する。
数千タスク、数万リンクの規模でこれを行うと、オーバーヘッドは指数関数的に増大し、処理完了までに数分から数十分を要する。
② メモリリークとオブジェクトの生存期間（ライフサイクル）
MS ProjectのCOM参照は極めてデリケートである。ループ処理の中で一時オブジェクトを適切に解放（`Set … = Nothing`）しなければ、参照カウンタがクリアされず、ExcelやProjectのプロセスがゾンビのようにバックグラウンドに残り続ける。
解決策：メモリ上へのグラフの転写（Projection）
この問題を解決するため、本アーキテクチャでは、MS ProjectのCOM空間から「タスクID」と「依存関係の接続情報」のみを高速に一括抽出し、メモリ上の`Scripting.Dictionary`および配列構造に転写（プロジェクション）する。
実探索は純粋なメモリ空間でのみ実行し、COMオブジェクトへのアクセスを最小限（$O(N)$）に抑える。
—
2. グラフ理論によるアプローチ：3色着色DFSアルゴリズム
循環参照を検出する上で、単純な「訪問済み（Visited）」フラグだけを用いた深さ優先探索（DFS）では不十分である。無向グラフとは異なり、有向グラフにおける閉路検出には、「探索中（アクティブな再帰スタック内）」と「探索完了（バックトラック済み）」を明確に区別する必要がある。
これを行うのが、グラフ理論における「3色着色（Three-Color Coloring）アルゴリズム」である。
ノードの3つの状態
1. WHITE（未訪問：0）: まだ一度も探索されていないノード。
2. GRAY（探索中：1）: 現在の探索パス（再帰スタック）に含まれているノード。探索中にこの状態のノードに再遭遇した場合、そこに循環参照（閉路）が存在する。
3. BLACK（探索完了：2）: そのノードから到達可能なすべての経路を探索し終え、ループが見つからなかったノード。
[WHITE] (未訪問)
│
▼ (訪問開始)
[GRAY ] (探索中: スタックに積まれている) ── (再遭遇!) ──> 【循環参照検出!】
│
▼ (すべての接続先をクリア)
[BLACK] (安全確定)
この状態遷移を再帰呼び出し（Recursive Call）によって実装する。
—
3. 極限のVBA実装：デッドロック検出エンジン
以下に、実戦に耐えうる極限まで最適化されたVBAコードを示す。
このコードは、高精度な時間計測（`QueryPerformanceCounter`）を行い、COM参照を厳密に管理し、検出された循環パスのトレースログを完全に吐き出す。
Option Explicit
‘ ==============================================================================
‘ Windows API: 高精度タイマー（パフォーマンスカウンタ）
‘ ==============================================================================
If VBA7 Then
Private Declare PtrSafe Function QueryPerformanceCounter Lib “kernel32” (lpPerformanceCount As Currency) As Long
Private Declare PtrSafe Function QueryPerformanceFrequency Lib “kernel32” (lpFrequency As Currency) As Long
Else
Private Declare Function QueryPerformanceCounter Lib “kernel32” (lpPerformanceCount As Currency) As Long
Private Declare Function QueryPerformanceFrequency Lib “kernel32″ (lpFrequency As Currency) As Long
End If
‘ ノードの状態定義（3色着色アルゴリズム）
Private Const STATE_WHITE As Byte = 0 ‘ 未探索
Private Const STATE_GRAY As Byte = 1 ‘ 探索中（スタック上：循環検出のフラグ）
Private Const STATE_BLACK As Byte = 2 ‘ 探索完了
‘ グラフ構造保持用モジュール変数
Private gdctGraph As Object ‘ 隣接リスト (Key: TaskID, Value: Collection of Successor TaskIDs)
Private gdctStates As Object ‘ 各ノードの状態 (Key: TaskID, Value: Byte)
Private gcolCurrentPath As Object ‘ 現在の探索スタック（循環パス特定用）
Private gcolDeadlocks As Object ‘ 検出されたデッドロック（循環パス）のリスト
”’
”’
Public Sub DetectProjectCircularDependencies()
Dim curStart As Currency, curEnd As Currency, curFreq As Currency
Dim dblElapsed As Double
QueryPerformanceFrequency curFreq
QueryPerformanceCounter curStart
Debug.Print “=== 循環参照検出エンジン 起動 ===”
‘ 1. メモリ初期化
Set gdctGraph = CreateObject(“Scripting.Dictionary”)
Set gdctStates = CreateObject(“Scripting.Dictionary”)
Set gcolCurrentPath = CreateObject(“System.Collections.ArrayList”) ‘ LIFOスタックとして利用
Set gcolDeadlocks = New Collection
‘ 2. MS Projectからメモリ上へのグラフの転写
On Error GoTo ErrorHandler
Call BuildGraphFromActiveProject
Debug.Print “グラフ構築完了。ノード数: ” & gdctGraph.Count
‘ 3. 3色DFSによる閉路検出
Dim varTaskId As Variant
For Each varTaskId In gdctGraph.Keys
‘ 未探索のノード（WHITE）からDFSを開始
If gdctStates(varTaskId) = STATE_WHITE Then
Call DepthFirstSearch(CLng(varTaskId))
End If
Next varTaskId
‘ 4. 結果出力
QueryPerformanceCounter curEnd
dblElapsed = CDbl(curEnd – curStart) / CDbl(curFreq)
Call ReportResults(dblElapsed)
Proc_Exit:
‘ 5. メモリの明示的解放（VBAガーベジコレクションの徹底）
Set gdctGraph = Nothing
Set gdctStates = Nothing
Set gcolCurrentPath = Nothing
Set gcolDeadlocks = Nothing
Exit Sub
ErrorHandler:
Debug.Print “【致命的エラー】: ” & Err.Description
Resume Proc_Exit
End Sub
”’
”’
Private Sub BuildGraphFromActiveProject()
Dim objProject As MSProject.Project
Dim objTask As MSProject.Task
Dim objDep As MSProject.TaskDependency
Dim colSuccessors As Collection
Dim lngTaskId As Long
Set objProject = MSProject.ActiveProject
‘ 全タスクを走査し、隣接リストのスケルトンを作成
For Each objTask In objProject.Tasks
If Not objTask Is Nothing Then
lngTaskId = objTask.ID
If Not gdctGraph.Exists(lngTaskId) Then
Set colSuccessors = New Collection
Set gdctGraph(lngTaskId) = colSuccessors
gdctStates(lngTaskId) = STATE_WHITE
End If
‘ 後続タスク（Successors）への有向エッジを収集
For Each objDep In objTask.SuccessorDependencies
‘ 削除済みタスクや無効なタスクへのリンクを除外
If Not objDep.To Is Nothing Then
gdctGraph(lngTaskId).Add objDep.To.ID
End If
Set objDep = Nothing ‘ COMオブジェクトの即時解放
Next objDep
End If
Set objTask = Nothing ‘ COMオブジェクトの即時解放
Next objTask
Set objProject = Nothing
End Sub
”’
”’
”’ 現在走査中のタスクID
Private Sub DepthFirstSearch(ByVal lngCurrentNode As Long)
‘ 現在のノードを探索中（GRAY）に設定し、パスにスタック
gdctStates(lngCurrentNode) = STATE_GRAY
gcolCurrentPath.Add lngCurrentNode
Dim colSuccessors As Collection
Set colSuccessors = gdctGraph(lngCurrentNode)
Dim varNextNode As Variant
For Each varNextNode In colSuccessors
Dim lngNextNode As Long
lngNextNode = CLng(varNextNode)
Select Case gdctStates(lngNextNode)
Case STATE_GRAY
‘ 【循環参照検出】
‘ 現在の探索パス（スタック）の中に、探索中（GRAY）のノードに再遭遇した。
‘ これにより、デッドロックを形成する閉路が確定する。
Call RegisterDeadlock(lngNextNode)
Case STATE_WHITE
‘ 未探索ノードであれば、再帰的に深く探索を継続
Call DepthFirstSearch(lngNextNode)
Case STATE_BLACK
‘ 探索完了済みのノード（BLACK）は、既にループフリーであることが証明されているためスルー
‘ （枝刈りによる高速化）
End Select
Next varNextNode
‘ バックトラック：現在のノードを探索完了（BLACK）にし、スタックから除去
gdctStates(lngCurrentNode) = STATE_BLACK
gcolCurrentPath.RemoveAt gcolCurrentPath.Count – 1
End Sub
”’
”’
Private Sub RegisterDeadlock(ByVal lngTargetNode As Long)
Dim strPath As String
Dim i As Long
Dim blnCapture As Boolean
blnCapture = False
strPath = “”
‘ スタックを遡り、閉路を形成している部分のみを抽出する
For i = 0 To gcolCurrentPath.Count – 1
Dim lngNodeId As Long
lngNodeId = gcolCurrentPath.Item(i)
If lngNodeId = lngTargetNode Then
blnCapture = True
End If
If blnCapture Then
strPath = strPath & “TaskID: ” & lngNodeId & ” -> ”
End If
Next i
strPath = strPath & “TaskID: ” & lngTargetNode
gcolDeadlocks.Add strPath
End Sub
”’
”’
Private Sub ReportResults(ByVal dblElapsed As Double)
Debug.Print “————————————————–”
Debug.Print “探索完了。処理時間: ” & Format(dblElapsed, “0.0000”) & ” 秒”
Debug.Print “————————————————–”
If gcolDeadlocks.Count = 0 Then
Debug.Print “【正常】 循環参照は検出されませんでした。WBSはクリーンです。”
Else
Debug.Print “【警告】 ” & gcolDeadlocks.Count & ” 件の循環参照（デッドロック）を検出しました：”
Dim varDeadlock As Variant
Dim lngCount As Long
lngCount = 1
For Each varDeadlock In gcolDeadlocks
Debug.Print ” [閉路 #” & lngCount & “]: ” & varDeadlock
lngCount = lngCount + 1
Next varDeadlock
End If
Debug.Print “==================================================”
End Sub
—
4. アーキテクチャの解説とディープ・ダイブ
このコードが、一般的なVBAスクリプトと一線を画す「プロフェッショナル仕様」である所以を解説する。
1. COMオブジェクトへのアクセス最小化（メモリープロジェクション）
`BuildGraphFromActiveProject` サブルーチンに注目してほしい。ここでは、MS ProjectのCOM構造を走査しているが、処理は「タスクのID」と「接続先（Successors）のID」をメモリ上のDictionaryに格納するだけで終了している。
以降の再帰探索処理（`DepthFirstSearch`）の中では、重たい`MSProject.Task`オブジェクトや`MSProject.TaskDependency`オブジェクトは一切参照せず、すべて高速なLong型の整数値（メモリ上のハッシュテーブル）だけで計算を完結させている。これにより、数千タスクを処理してもミリ秒単位で処理が終了する。
2. 3色着色アルゴリズムによる「枝刈り（Pruning）」
もし、単純なDFSで「すでに訪問したかどうか」の2色（Visited / Unvisited）だけで探索を行うと、合流ノード（複数のパスから合流するノード）に到達するたびに、その先を何度も重複して探索することになり、計算量が最悪の場合 $O(2^N)$ に爆発する。
本アルゴリズムでは、一度安全（ループなし）と判明したノードを `STATE_BLACK` に設定する。以降、別の探索パスからそのノードに出会っても、探索を即時スキップ（枝刈り）するため、計算量は厳密に $O(V + E)$（$V$: 頂点数, $E$: 辺数）に抑えられる。
3. コレクション・スタックによる閉路パスの正確な復元
循環参照が発生した際、「循環が発生している」という事実だけでなく、「どのタスクとどのタスクがループを形成しているのか」のパス（Path）を特定できなければ、デバッグツールとしての価値は半減する。
本実装では、.NET Frameworkが提供する強力な軽量リストオブジェクト `System.Collections.ArrayList` をVBA内部でインスタンス化し、アクティブな探索スタックとして利用している。
これにより、ループの始点（`lngTargetNode`）に遭遇した瞬間、スタック内の該当ノードから現在地までの履歴を正確に抜き出し、`TaskID: 10 -> TaskID: 15 -> TaskID: 12 -> TaskID: 10` のような直感的なデバッグログの出力を可能にしている。
—
5. レガシーとモダンを繋ぐ「究極の守護神」として
MS Projectを用いたWBS自動化ツールを運用するシステム管理者にとって、データの整合性担保は生命線である。
特に、Excelマクロやデータベースなどの外部システムからタスク構造を流し込むバッチ処理を組む場合、この「循環参照検出エンジン」をインポート処理の「プレ・バリデータ（事前検証フェーズ）」として組み込むことを強く推奨する。
インポートを実行する前に、メモリ上で仮想的にグラフを組み立てて本エンジンを実行し、エラーがゼロの場合のみ実際のMS Projectドキュメントへ書き込み（Commit）を行う。
この「二段階コミット」のアーキテクチャを採用することで、データの破損やMS Projectのハングアップを100%未然に防ぐことができる。
卓越したエンジニアリングとは、単に動くコードを書くことではない。
システムの限界（COMバリア）を理解し、数学的アルゴリズム（グラフ理論）を適材適所で適用し、予期せぬ破綻からシステムを守る堅牢な防壁を築くことである。本稿のコードが、あなたの構築するシステムの信頼性を極限まで高める一助となることを確信している。
