「Applibot Advent Calendar 2020」 6日目の記事になります。
前日は @ref3000 さんのCloud Firestore でさくっとオンライン対戦ゲームを作ろう という記事でした!
#目次
1.はじめに
2.基礎知識
3.要件定義
4.実装
5.まとめと感想
6.おわりに
#1. はじめに
管理者が入力するマスターデータに入れ子構造のデータが必要になり、循環参照が発生するデータを入力されるとロジック側が無限ループになってしまうため、それを回避するために検証機能を追加した話になります。
gonumパッケージのグラフとライブラリを利用することで簡単に実装することができます。
#2. 基礎知識
本稿を読むにあたってグラフに関する基礎知識があると理解が深まるため、以下に簡単にまとめました。
##2.1 グラフ
ノードと呼ばれる頂点と、エッジと呼ばれる辺で構成されるデータ構造です。
グラフには下記のような種類があり、丸の部分がノード(数字はノードを識別するid)、線の部分がエッジを表しています。
###2.1.1 無向グラフ
各ノードをつなぐエッジに、方向がないグラフを無向グラフと呼びます。
「1 - 2 - 3」の間は相互につながっており、それぞれのノードから参照可能です。
###2.1.2 有向グラフ
各ノードをつなぐエッジに方向があり、相互につながっているグラフを有向グラフと呼びます。
「1 -> 2」,「1 -> 3」で1は2と3を参照できることを、「2 -> 3」で2は3を参照できることを表します。
3は1,2の両方ともに矢印を持っていないため、1,2を参照することができません。
###2.1.3 単純グラフ
無向グラフ、有向グラフで示した例のように、ノード間のエッジが1本のみのものを単純グラフと呼びます。
###2.1.4 多重グラフ
「1 -> 2」, 「2 -> 1」のように、同一ノード間に2つ以上のエッジ(多重辺)を持つものが含まれているグラフを多重グラフと呼びます。
また、「3 -> 3」のように、自分自身へのエッジを持つものが含まれているグラフも多重グラフと呼びます。
##2.2 循環参照
###2.2.1 閉路
「1 -> 2 -> 4 -> 1」のように、始点と終点が同じノードになる経路のことを閉路と呼びます。
###2.2.2 ループ
「3 -> 3」のように自分自身へのエッジをもち、自身のノードを参照できるものを、ループと呼びます。
#3. 要件定義
今回検証したいテーブルは、下記のようなrelationのテーブルのデータを二次元配列(スライス)で持っており、こちらに入力されたデータに対して循環参照が発生しないようなチェックを行いたいと思います。
| parent_id | child_id |
|---|---|
| 1 | 2 |
| 1 | 3 |
| 2 | 1 |
| 2 | 3 |
| 2 | 4 |
| 3 | 3 |
| 4 | 1 |
| 4 | 5 |
上記のテーブルをグラフで表すと下記のようになっており、オレンジ色の「1 -> 2 -> 1」、「1 -> 2 -> 4 -> 1」で閉路を持っており、青色の「3 -> 3」でループをもっています。
#4. 実装
##4.1 ソースコード
The Go Playgroundで動作確認ができます。
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群を全て取得することができました。
[[3] [1 2 1] [1 2 4 1]]
#5. まとめと感想
gonumのグラフパッケージを使うことで簡単に循環参照の検証メソッドを追加することができました。
今回多重有向グラフを用いたように、たとえ要件的には単純有向グラフや木構造で成立するものでも、データ構造が表現可能なグラフで実装しないと異常データの検出が難しくなる場合もあるため、注意が必要だなと感じました。
gonumでは今回作成したグラフ以外にも重み付きグラフなども表現可能で、pathパッケージなどを使うことで「ダイクストラ」や「A*」などのアルゴリズムも利用でき、簡単に最短経路探索なども実装可能です。
アルゴリズム関連のメソッドは自分で実装するとブラックボックスになりがちで、バグなどにも気づきにくいことから、ライブラリを利用しても問題ない状況では今後も積極的に使っていきたいと思いました。
#6. おわりに
「Applibot Advent Calendar 2020」 6日目の記事でした！
明日は @fu11mated さんの行動ログを吐き出すバッチを作ったら便利だった話です！