# 機能設計書 74-強連結成分検出

## 概要

本ドキュメントは、Apache Spark GraphXにおける強連結成分（Strongly Connected Components, SCC）検出アルゴリズムの設計を記述する。

### 本機能の処理概要

強連結成分検出は、有向グラフにおいて互いに到達可能な頂点の最大集合を見つけるアルゴリズムである。連結成分（No.73）が無向グラフの接続性を扱うのに対し、強連結成分はエッジの方向を考慮する。各頂点に対して、その頂点が属するSCC内の最小頂点IDをラベルとして割り当てる。

**業務上の目的・背景**：有向グラフにおいて双方向に到達可能なノード群（強連結成分）を特定する必要がある場面で使用される。Webのリンク構造分析、依存関係グラフの循環検出、ソーシャルネットワークにおける密結合コミュニティの検出などに応用される。

**機能の利用シーン**：ソフトウェアモジュール間の循環依存検出、金融取引ネットワークにおける循環取引パターンの検出、交通ネットワークにおける双方向到達可能ゾーンの分析。

**主要な処理内容**：
1. 入次数/出次数が0の頂点を「最終確定」として除外（トリミング）
2. トリミング後に残った頂点にPregelでカラーリング（前方伝播）
3. カラーリング結果に基づくSCC確定（後方伝播）
4. 確定した頂点を除外して残りのグラフで反復
5. 最大numIter回の外部ループで繰り返し

**関連システム・外部連携**：GraphXのグラフ構造データ管理（No.71）とPregelフレームワーク（No.79）に依存。

**権限による制御**：特に権限による制御は行われない。

## 関連画面

本機能に直接関連するUI画面はない。

## 機能種別

計算処理 / グラフアルゴリズム

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| graph | Graph[VD, ED] | Yes | SCC検出の対象グラフ | - |
| numIter | Int | Yes | 最大反復回数 | > 0 |

### 入力データソース

Graph[VD, ED] - GraphXのグラフ構造。頂点属性VDは破棄され、エッジ属性EDは保持される。

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| Graph[VertexId, ED] | Graph | 頂点属性にSCCの最小頂点IDを持つグラフ |

### 出力先

メモリ上のGraph RDD

## 処理フロー

### 処理シーケンス

```
1. 初期化
   ├─ sccGraph: 各頂点を自身のIDで初期化
   └─ sccWorkGraph: 各頂点を (vid, false) で初期化

2. 外部ループ (最大 numIter 回)
   ├─ 2a. トリミング (do-while)
   │   ├─ 入次数/出次数が0の頂点を「最終確定」(isFinal=true) にマーク
   │   ├─ 最終確定頂点のSCC IDをsccGraphに書き込み
   │   ├─ 最終確定頂点をsccWorkGraphから除外
   │   └─ 頂点数が減少しなくなるまで繰り返し
   │
   ├─ 2b. 前方伝播 (Pregel, EdgeDirection.Out)
   │   ├─ 各頂点の最小近傍SCC値を収集
   │   └─ srcAttr < dstAttr なら dstId に srcAttr を送信
   │
   └─ 2c. 後方伝播 (Pregel, EdgeDirection.In)
       ├─ SCCルート (vid == scc値) を最終確定
       └─ 同じカラーで最終確定済みの近傍から後方に伝播

3. 結果
   └─ sccGraph を返却
```

### フローチャート

```mermaid
flowchart TD
    A[入力グラフ] --> B[sccGraph / sccWorkGraph初期化]
    B --> C{numIter残りあり?}
    C -->|Yes| D[トリミング: 入次数/出次数0の頂点を確定]
    D --> E{頂点数減少?}
    E -->|Yes| D
    E -->|No| F[前方伝播: Pregel EdgeDirection.Out]
    F --> G[後方伝播: Pregel EdgeDirection.In]
    G --> H[確定頂点をsccGraphに書き込み]
    H --> C
    C -->|No| I[sccGraph出力]
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-74-01 | トリミング | 入次数または出次数が0の頂点はSCCに属さないため即座に確定 | 各外部反復の開始時 |
| BR-74-02 | カラーリング | 前方伝播で各頂点に最小到達可能頂点IDをカラーとして割り当て | 前方伝播フェーズ |
| BR-74-03 | SCC確定 | カラールート (vid == color) およびそのカラーの後方到達可能頂点をSCCとして確定 | 後方伝播フェーズ |
| BR-74-04 | 反復除外 | 確定済み頂点はワーキンググラフから除外され、以降の反復に参加しない | サブグラフ化 |

### 計算ロジック

- **前方伝播vprog**: `(math.min(myScc._1, neighborScc), myScc._2)` (StronglyConnectedComponents.scala 91行目)
- **前方伝播sendMsg**: `srcAttr._1 < dstAttr._1` の場合のみ送信 (92-97行目)
- **後方伝播vprog**: `isColorRoot || existsSameColorFinalNeighbor` で最終確定判定 (107-109行目)
- **後方伝播sendMsg**: 同じカラーで自分が最終確定、相手が未確定の場合に送信 (112-120行目)

## データベース操作仕様

GraphXはデータベースを直接操作しない。

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| IllegalArgumentException | 入力検証 | numIter <= 0 | 正の整数を指定 |

### リトライ仕様

RDDの耐障害性メカニズムに従う。

## トランザクション仕様

トランザクション機構は存在しない。

## パフォーマンス要件

- トリミングフェーズにより早期に確定可能な頂点を除外し、後続の反復の計算量を削減
- 各反復でsccGraph.vertices.count() / edges.count() で明示的にマテリアライズ
- prevSccGraph.unpersist() で前回のグラフメモリを解放

## セキュリティ考慮事項

特になし。

## 備考

- 連結成分検出（No.73）とは異なり、有向グラフのエッジ方向を考慮する
- numIterは外部ループの回数であり、各外部ループ内のPregelは収束まで反復する
- 実装は約130行で、トリミング + 前方Pregel + 後方Pregel の3フェーズ構成

---

## コードリーディングガイド

本機能を理解するために参照すべきファイルと、推奨する読み解き順序を以下に示す。

### 推奨読解順序

#### Step 1: データ構造を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | StronglyConnectedComponents.scala | `graphx/src/main/scala/org/apache/spark/graphx/lib/StronglyConnectedComponents.scala` | sccWorkGraphの頂点属性 `(VertexId, Boolean)` = (SCC ID, 最終確定フラグ) を理解する |

**読解のコツ**: sccGraphとsccWorkGraphの2つのグラフが並行して管理される。sccGraphは最終結果用、sccWorkGraphは未確定頂点での作業用。

#### Step 2: アルゴリズム実装を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | StronglyConnectedComponents.scala | `graphx/src/main/scala/org/apache/spark/graphx/lib/StronglyConnectedComponents.scala` | トリミング(52-80行目)、前方Pregel(89-99行目)、後方Pregel(103-121行目)の3フェーズ |

**主要処理フロー**:
- **38行目**: run メソッドのシグネチャ
- **43行目**: sccGraph初期化（各頂点を自身のIDで初期化）
- **45行目**: sccWorkGraph初期化（(vid, false)で初期化）
- **52-80行目**: トリミングループ。出次数/入次数が0の頂点をisFinal=trueにマーク
- **85行目**: カラーを自身のvidにリセット
- **89-99行目**: 前方Pregel - EdgeDirection.Outで最小ラベルを伝播
- **103-121行目**: 後方Pregel - EdgeDirection.Inで同一カラー頂点を確定

### プログラム呼び出し階層図

```
GraphOps.stronglyConnectedComponents(numIter)
    |
    +-- StronglyConnectedComponents.run(graph, numIter)
            |
            +-- [外部ループ: iter < numIter]
                    |
                    +-- [トリミング do-while]
                    |       +-- outerJoinVertices(outDegrees) [出次数0検出]
                    |       +-- outerJoinVertices(inDegrees) [入次数0検出]
                    |       +-- subgraph(vpred = !isFinal) [確定頂点除外]
                    |
                    +-- Pregel(sccWorkGraph, Long.MaxValue, EdgeDirection.Out)
                    |       [前方伝播: 最小カラー伝播]
                    |
                    +-- Pregel(sccWorkGraph, false, EdgeDirection.In)
                            [後方伝播: SCC確定]
```

### データフロー図

```
[入力]                    [処理]                        [出力]

Graph[VD, ED] -----> 初期化 ----> トリミング
                                      |
                              前方Pregel(Out方向)
                                      |
                              後方Pregel(In方向)
                                      |
                              確定頂点をsccGraphに蓄積
                                      |
                                      v
                              Graph[VertexId, ED]
                              (各頂点にSCC IDを持つ)
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| StronglyConnectedComponents.scala | `graphx/src/main/scala/org/apache/spark/graphx/lib/StronglyConnectedComponents.scala` | ソース | 強連結成分検出アルゴリズム実装 |
| GraphOps.scala | `graphx/src/main/scala/org/apache/spark/graphx/GraphOps.scala` | ソース | stronglyConnectedComponents便利メソッド |
| Pregel.scala | `graphx/src/main/scala/org/apache/spark/graphx/Pregel.scala` | ソース | 反復計算基盤 |
| Graph.scala | `graphx/src/main/scala/org/apache/spark/graphx/Graph.scala` | ソース | グラフ抽象クラス |
