# 機能設計書 76-最短経路探索

## 概要

本ドキュメントは、Apache Spark GraphXにおける最短経路探索（ShortestPaths）アルゴリズムの設計を記述する。

### 本機能の処理概要

最短経路探索は、指定されたランドマーク頂点の集合に対して、グラフ上のすべての頂点から各ランドマークへの最短経路距離（ホップ数）を計算するアルゴリズムである。結果は、各頂点の属性としてランドマークIDから最短距離へのマップを持つグラフとして返される。

**業務上の目的・背景**：ネットワーク上の特定ノード間の距離計算、到達可能性分析、ネットワーク中心性の指標算出（近接中心性など）に使用される。

**機能の利用シーン**：交通ネットワークでの最短経路計算、SNSにおける「何人の知人を介して到達可能か」の分析、ネットワークの直径計算。

**主要な処理内容**：
1. ランドマーク頂点を距離0で初期化
2. Pregelフレームワークによる反復メッセージパッシング
3. 各エッジでランドマークへの距離をインクリメントして逆方向に伝播
4. 各頂点で受信した距離マップと現在の距離マップを最小値で統合
5. 更新がなくなるまで反復

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

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

## 関連画面

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

## 機能種別

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

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| graph | Graph[VD, ED] | Yes | 最短経路計算の対象グラフ | - |
| landmarks | Seq[VertexId] | Yes | ランドマーク頂点IDのシーケンス | - |

### 入力データソース

Graph[VD, ED] - GraphXのグラフ構造。エッジの重みは考慮されず、ホップ数のみで距離を計算する。

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| Graph[SPMap, ED] | Graph | 頂点属性にランドマークIDから最短距離へのMap[VertexId, Int]を持つグラフ |

SPMap = Map[VertexId, Int] （ランドマークID -> 最短距離のマップ）

### 出力先

メモリ上のGraph RDD

## 処理フロー

### 処理シーケンス

```
1. 初期化
   ├─ ランドマーク頂点: Map(vid -> 0) （自身への距離は0）
   └─ 非ランドマーク頂点: Map() （空マップ）

2. Pregel反復
   ├─ initialMessage: Map() (空マップ)
   ├─ vprog: addMaps(attr, msg) でマップ統合（各キーの最小距離を採用）
   ├─ sendMsg:
   │   ├─ incrementMap(edge.dstAttr) で宛先頂点のマップの全距離を+1
   │   └─ 送信元頂点の現在マップが変化する場合のみ送信
   └─ mergeMsg: addMaps(spmap1, spmap2)

3. 結果
   └─ Graph[SPMap, ED] を返却
```

### フローチャート

```mermaid
flowchart TD
    A[入力グラフ + ランドマークリスト] --> B[ランドマーク頂点を距離0で初期化]
    B --> C[Pregel反復開始]
    C --> D[各エッジでdst側のマップを+1してsrcに送信]
    D --> E[各頂点でマップ統合: 各キーの最小距離]
    E --> F{更新あり?}
    F -->|Yes| D
    F -->|No| G[結果グラフ出力]
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-76-01 | ホップ数距離 | エッジ重みは考慮せず、全エッジの距離は1（ホップ数） | 全エッジ |
| BR-76-02 | マップ統合 | 同じランドマークへの距離は最小値を採用 | addMaps |
| BR-76-03 | 更新判定 | 送信元の現在マップと新マップが異なる場合のみメッセージ送信 | sendMessage |
| BR-76-04 | 到達不能 | あるランドマークに到達不能な頂点のマップにはそのランドマークのエントリがない | 結果解釈 |

### 計算ロジック

- **incrementMap**: `spmap.map { case (v, d) => v -> (d + 1) }` (ShortestPaths.scala 35行目)
- **addMaps**: 両マップのキー和集合について、各キーの最小距離を採用 (37-44行目)
- **vertexProgram**: `addMaps(attr, msg)` (65-67行目)
- **sendMessage**: `incrementMap(edge.dstAttr)` を計算し、srcAttrと異なる場合のみ送信 (69-73行目)

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

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

## エラー処理

### エラーケース一覧

特筆すべきバリデーションエラーはない。空のlandmarksが指定された場合は全頂点の属性が空マップとなる。

### リトライ仕様

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

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

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

## パフォーマンス要件

- ランドマーク数が多い場合、各頂点が保持するマップサイズが大きくなりメモリ使用量が増加
- 更新判定（sendMessage内のaddMaps比較）により不要なメッセージ送信を削減

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

特になし。

## 備考

- エッジの重みを考慮しない（重み付き最短経路には非対応）
- ShortestPathsオブジェクトはSerializableを実装している
- SPMap型エイリアスは`Map[VertexId, Int]`

---

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

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

### 推奨読解順序

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

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | ShortestPaths.scala | `graphx/src/main/scala/org/apache/spark/graphx/lib/ShortestPaths.scala` | SPMap型エイリアスとヘルパー関数(makeMap, incrementMap, addMaps)を理解する |

**読解のコツ**: SPMap = Map[VertexId, Int] は「ランドマークID -> そのランドマークへの最短距離」を表す。incrementMapは全距離を+1する操作。

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

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | ShortestPaths.scala | `graphx/src/main/scala/org/apache/spark/graphx/lib/ShortestPaths.scala` | run メソッド (58-76行目) |

**主要処理フロー**:
- **31行目**: SPMap型エイリアス定義
- **33行目**: makeMap - 可変長引数からMapを構築
- **35行目**: incrementMap - 全距離を+1
- **37-44行目**: addMaps - 2つのマップの各キーで最小距離を採用
- **58-61行目**: 初期化 - ランドマーク頂点はMap(vid -> 0)、他はMap()
- **63行目**: initialMessage = Map()
- **65-67行目**: vertexProgram = addMaps(attr, msg)
- **69-73行目**: sendMessage - dstAttrを+1してsrcに送信（更新がある場合のみ）
- **75行目**: Pregel(spGraph, initialMessage)(vertexProgram, sendMessage, addMaps)

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

```
ShortestPaths.run(graph, landmarks)
    |
    +-- graph.mapVertices [ランドマーク初期化]
    +-- Pregel(spGraph, initialMessage)
            +-- vertexProgram: addMaps(attr, msg)
            +-- sendMessage: incrementMap(edge.dstAttr)
            +-- mergeMsg: addMaps
```

### データフロー図

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

Graph[VD, ED]        ランドマーク初期化
+ Seq[VertexId]       Map(vid -> 0)
                           |
                    Pregel反復
                    (距離マップ伝播)
                           |
                           v
                    Graph[SPMap, ED]
                    (各頂点にランドマーク距離マップ)
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| ShortestPaths.scala | `graphx/src/main/scala/org/apache/spark/graphx/lib/ShortestPaths.scala` | ソース | 最短経路探索アルゴリズム実装 |
| Pregel.scala | `graphx/src/main/scala/org/apache/spark/graphx/Pregel.scala` | ソース | 反復計算基盤 |
| Graph.scala | `graphx/src/main/scala/org/apache/spark/graphx/Graph.scala` | ソース | グラフ抽象クラス |
