goでデータの循環参照をチェックする(gonumパッケージ グラフ入門)

「[Applibot Advent Calendar 2020](https://qiita.com/advent-calendar/2020/applibot)」 6日目の記事になります。
前日は @ref3000 さんの[Cloud Firestore でさくっとオンライン対戦ゲームを作ろう](https://qiita.com/ref3000/items/866cb2fab2c6e3605455) という記事でした!

#目次
[1.はじめに](#1-はじめに)
[2.基礎知識](#2-基礎知識)
[3.要件定義](#3-要件定義)
[4.実装](#4-実装)
[5.まとめと感想](#5-まとめと感想)
[6.おわりに](#6-おわりに)

#1. はじめに
管理者が入力するマスターデータに入れ子構造のデータが必要になり、循環参照が発生するデータを入力されるとロジック側が無限ループになってしまうため、それを回避するために検証機能を追加した話になります。
[gonum](https://github.com/gonum/gonum)パッケージのグラフとライブラリを利用することで簡単に実装することができます。

#2. 基礎知識
本稿を読むにあたってグラフに関する基礎知識があると理解が深まるため、以下に簡単にまとめました。

##2.1 グラフ
ノードと呼ばれる頂点と、エッジと呼ばれる辺で構成されるデータ構造です。
グラフには下記のような種類があり、丸の部分がノード(数字はノードを識別するid)、線の部分がエッジを表しています。

###2.1.1 無向グラフ
各ノードをつなぐエッジに、方向がないグラフを無向グラフと呼びます。
「1 - 2 - 3」の間は相互につながっており、それぞれのノードから参照可能です。
<img alt="simple_undirected_sample.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/21249/ee01d922-26f8-b612-3187-2d95a7e65755.png" width="300">

###2.1.2 有向グラフ
各ノードをつなぐエッジに方向があり、相互につながっているグラフを有向グラフと呼びます。
「1 -> 2」,「1 -> 3」で1は2と3を参照できることを、「2 -> 3」で2は3を参照できることを表します。
3は1,2の両方ともに矢印を持っていないため、1,2を参照することができません。
<img alt="simple_directed_sample.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/21249/49e4636e-577f-9702-fc45-922d17b04e11.png" width="300">

###2.1.3 単純グラフ
無向グラフ、有向グラフで示した例のように、ノード間のエッジが1本のみのものを単純グラフと呼びます。
<img alt="simple_sample1.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/21249/3cf1d29c-b3c9-2a59-03cb-b919d4eee08a.png" width="600">

###2.1.4 多重グラフ
「1 -> 2」, 「2 -> 1」のように、同一ノード間に2つ以上のエッジ(多重辺)を持つものが含まれているグラフを多重グラフと呼びます。
また、「3 -> 3」のように、自分自身へのエッジを持つものが含まれているグラフも多重グラフと呼びます。
<img alt="multi_directed_sample2.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/21249/732aa7b3-8c66-94e4-023b-382d57eb68a9.png" width="300">

##2.2 循環参照
<img alt="multi_directed1_c.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/21249/cbde5b7d-1d28-e9d6-0f70-f8c530667e69.png" width="350">

###2.2.1 閉路
「<font color="#ff9900">1 -> 2 -> 4 -> 1</font>」のように、始点と終点が同じノードになる経路のことを<font color="#ff9900">閉路</font>と呼びます。

###2.2.2 ループ
「<font color="#3c78d8">3 -> 3</font>」のように自分自身へのエッジをもち、自身のノードを参照できるものを、<font color="#3c78d8">ループ</font>と呼びます。

#3. 要件定義
今回検証したいテーブルは、下記のようなrelationのテーブルのデータを二次元配列(スライス)で持っており、こちらに入力されたデータに対して循環参照が発生しないようなチェックを行いたいと思います。

|parent_id|child_id|
|---|---|
|1|2|
|1|3|
|2|1|
|2|3|
|2|4|
|3|3|
|4|1|
|4|5|

上記のテーブルをグラフで表すと下記のようになっており、<font color="#ff9900">オレンジ色</font>の「<font color="#ff9900">1 -> 2 -> 1</font>」、「<font color="#ff9900">1 -> 2 -> 4 -> 1</font>」で<font color="#ff9900">閉路</font>を持っており、<font color="#3c78d8">青色</font>の「<font color="#3c78d8">3 -> 3</font>」で<font color="#3c78d8">ループ</font>をもっています。
<img alt="relation_sample2.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/21249/ae5d1fec-dd5c-0003-34ac-ba84cbd8efa7.png" width="350">

#4. 実装

##4.1 ソースコード

[The Go Playground](https://play.golang.org/p/wqSJ4zqR5-b)で動作確認ができます。

```go
package main

import (
	"fmt"

	"gonum.org/v1/gonum/graph"
	"gonum.org/v1/gonum/graph/multi"
	"gonum.org/v1/gonum/graph/topo"
)

func main() {
	relations := [][]int64{
		{1, 2},
		{1, 3},
		{2, 1},
		{2, 3},
		{2, 4},
		{3, 3},
		{4, 1},
		{4, 5},
	}
	refs := getCircularReferences(relations)
	fmt.Println(refs)
}

func getCircularReferences(relations [][]int64) [][]graph.Node {
	// 参照関係からグラフの生成
	g := multi.NewDirectedGraph()
	for _, rel := range relations {
		// グラフのノードとエッジ生成&登録
		line := g.NewLine(multi.Node(rel[0]), multi.Node(rel[1]))
		g.SetLine(line)
	}

	// 循環参照チェック
	refs := make([][]graph.Node, 0)
	// ループチェック(topo.DirectedCyclesInではループを取得できないため)
	nodes := g.Nodes()
	for nodes.Next() {
		node := nodes.Node()
		// 自身のID間が参照可能であればループしているためrefsに追加
		if g.HasEdgeBetween(node.ID(), node.ID()) {
			refs = append(refs, []graph.Node{node})
		}
	}
	// 閉路チェック
	cycles := topo.DirectedCyclesIn(g)
	refs = append(refs, cycles...)
	return refs
}
```

##4.2 説明
今回は要件的には単純有向グラフですが、データ構造は多重有向グラフであるため、```multi.NewDirectedGraph```を用います。
```g.SetLine```実行時にグラフに存在しないノードはグラフに追加され、グラフの管理下に置かれます。
```topo.DirectedCyclesIn```では閉路を取得可能ですがループは取得できないため、ループチェックの方で自分でグラフの持つ全ノードに対してループが存在するかチェックを行い、存在する場合refsに追加しています。

##4.3 実行結果
下記のようになり、循環参照しているID群を全て取得することができました。

```go
[[3] [1 2 1] [1 2 4 1]]
```

#5. まとめと感想
gonumのグラフパッケージを使うことで簡単に循環参照の検証メソッドを追加することができました。

今回多重有向グラフを用いたように、たとえ要件的には単純有向グラフや木構造で成立するものでも、データ構造が表現可能なグラフで実装しないと異常データの検出が難しくなる場合もあるため、注意が必要だなと感じました。

gonumでは今回作成したグラフ以外にも重み付きグラフなども表現可能で、pathパッケージなどを使うことで「ダイクストラ」や「A*」などのアルゴリズムも利用でき、簡単に最短経路探索なども実装可能です。
アルゴリズム関連のメソッドは自分で実装するとブラックボックスになりがちで、バグなどにも気づきにくいことから、ライブラリを利用しても問題ない状況では今後も積極的に使っていきたいと思いました。

#6. おわりに
「[Applibot Advent Calendar 2020](https://qiita.com/advent-calendar/2020/applibot)」 6日目の記事でした！
明日は @fu11mated さんの[行動ログを吐き出すバッチを作ったら便利だった話](https://qiita.com/fu11mated/items/9fcb0b7f93a5977d5efa)です！