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

## 概要

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

### 本機能の処理概要

連結成分検出は、無向グラフ（または有向グラフを無向とみなした場合）において、互いに到達可能な頂点の集合（連結成分）を識別するアルゴリズムである。各頂点に対して、その頂点が属する連結成分内の最小頂点IDをラベルとして割り当てる。

**業務上の目的・背景**：ソーシャルネットワークのコミュニティ検出、Webページのクラスタリング、通信ネットワークの接続性分析、データのリンケージ（同一エンティティの特定）など、グラフ内の接続された部分構造を見つけ出す必要がある場面で使用される。

**機能の利用シーン**：顧客データの名寄せ（同一人物判定）、ネットワーク障害影響範囲の特定、離散したグラフクラスタの分類。

**主要な処理内容**：
1. 各頂点を自身のIDで初期化
2. Pregelフレームワークを使用した反復メッセージパッシング
3. 各エッジで小さい方のラベルを大きい方の頂点に送信
4. 頂点プログラムで受信メッセージと現在値の最小値を採用
5. メッセージがなくなるか最大反復回数に達するまで反復

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

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

## 関連画面

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

## 機能種別

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

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| graph | Graph[VD, ED] | Yes | 連結成分を検出する対象グラフ | - |
| maxIterations | Int | No | 最大反復回数（デフォルト: Int.MaxValue） | > 0 |

### 入力データソース

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

## 出力仕様

### 出力データ

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

### 出力先

メモリ上のGraph RDD

## 処理フロー

### 処理シーケンス

```
1. 初期化
   └─ mapVertices で各頂点を自身のIDで初期化: (vid, _) => vid

2. Pregel反復
   ├─ initialMessage: Long.MaxValue
   ├─ vprog: (id, attr, msg) => math.min(attr, msg)
   ├─ sendMsg: 小さいラベルを大きいラベルの頂点に送信
   │   ├─ srcAttr < dstAttr -> (dstId, srcAttr)
   │   ├─ srcAttr > dstAttr -> (srcId, dstAttr)
   │   └─ srcAttr == dstAttr -> 送信なし
   └─ mergeMsg: (a, b) => math.min(a, b)

3. クリーンアップ
   └─ ccGraph.unpersist()
```

### フローチャート

```mermaid
flowchart TD
    A[入力グラフ] --> B[各頂点を自身のIDで初期化]
    B --> C[Pregel反復開始]
    C --> D[各エッジで小さいラベルを送信]
    D --> E[頂点で最小値を採用]
    E --> F{メッセージあり?}
    F -->|Yes| D
    F -->|No| G[結果グラフ出力]
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-73-01 | ラベル伝播 | 各連結成分内の最小頂点IDがラベルとして全頂点に伝播される | 全エッジ |
| BR-73-02 | 双方向伝播 | EdgeDirection.Eitherを使用し、エッジの両方向でラベルを伝播 | Pregel設定 |
| BR-73-03 | 収束条件 | すべてのエッジで両端の頂点が同じラベルを持つ場合に収束 | 反復終了条件 |

### 計算ロジック

- **頂点プログラム**: `math.min(attr, msg)` (ConnectedComponents.scala 55行目)
- **送信関数**: srcAttr < dstAttrなら(dstId, srcAttr)、逆なら(srcId, dstAttr)、同じなら送信なし (43-51行目)
- **結合関数**: `math.min(a, b)` (57行目)

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

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

## エラー処理

### エラーケース一覧

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

### リトライ仕様

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

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

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

## パフォーマンス要件

- Pregelの反復によりメッセージが減少していくため、収束に近づくと計算量が大幅に減少
- EdgeDirection.Eitherを使用しており、メッセージ送信は必要な方向にのみ行われる

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

特になし。

## 備考

- maxIterationsを指定しない場合はInt.MaxValueが使用され、完全収束まで反復する
- エッジ属性EDは結果グラフにそのまま保持される

---

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

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

### 推奨読解順序

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

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | Graph.scala | `graphx/src/main/scala/org/apache/spark/graphx/Graph.scala` | Graph[VertexId, ED]の出力型を理解する |

#### Step 2: エントリーポイントを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | GraphOps.scala | `graphx/src/main/scala/org/apache/spark/graphx/GraphOps.scala` | connectedComponents()メソッド (445-457行目) |

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

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | ConnectedComponents.scala | `graphx/src/main/scala/org/apache/spark/graphx/lib/ConnectedComponents.scala` | 全体で75行の簡潔な実装。Pregelへの委譲パターンを理解する |

**主要処理フロー**:
- **37-60行目**: run(graph, maxIterations) - メインロジック
- **42行目**: 各頂点を自身のIDで初期化
- **43-51行目**: sendMessage - ラベル比較と送信方向決定
- **52行目**: initialMessage = Long.MaxValue
- **53-57行目**: Pregel呼び出し（vprog, sendMsg, mergeMsg）

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

```
GraphOps.connectedComponents()
    |
    +-- ConnectedComponents.run(graph)
            +-- ConnectedComponents.run(graph, Int.MaxValue)
                    +-- graph.mapVertices { (vid, _) => vid }
                    +-- Pregel(ccGraph, Long.MaxValue, maxIterations, EdgeDirection.Either)
                    |       +-- vprog: math.min(attr, msg)
                    |       +-- sendMsg: 小さいラベルを伝播
                    |       +-- mergeMsg: math.min(a, b)
                    +-- ccGraph.unpersist()
```

### データフロー図

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

Graph[VD, ED] ---> mapVertices(vid => vid) ---> Pregel反復
                                                    |
                                           ラベル伝播(最小ID)
                                                    |
                                                    v
                                           Graph[VertexId, ED]
                                           (各頂点に連結成分IDを持つ)
```

### 関連ファイル一覧

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