golangによるグラフ理論ライブラリの実装

はじめに

概要

golangでグラフ理論のライブラリを実装しました。
https://github.com/g0nta/goraph

• グラフの設計はNetworkXを参考にしている部分があります。
• まだ無向グラフ、幅優先探索、深さ優先探索しか実装できていません。
• より複雑なアルゴリズム（最小全域木、最短経路、最大フローetc...）を実装しようとすると困るかもしれません。

グラフ理論って何？って方はこちら
雑に言うと道路交通網や人間関係などのネットワーク構造を数学的に抽象化したものです。

なぜ作ったか

学生のころにグラフ理論に関する研究をやっており、グラフ理論には多少関心がありました。
また、golangが熱いという旨の記事をSNSなどで見かけることが多く、golangにも興味がありました。
あとは最近人生の迷子になっており、突破口を見つけるために何かしら作ってみようということで作った次第になります。

基本的な使い方

グラフの構築

IGraphというinterfaceがあり、これを実装するものは全てグラフとみなします。
IGraphは頂点や辺の追加、更新、削除などのメソッドを持ちます。

頂点の追加

頂点はinterface{}型です。なんでも頂点になり得ます。
頂点には属性（attribute）が付随します。頂点の重さや色などはここに記述します。
頂点をグラフに追加するには下記のように書きます。

	g := NewGraph()  //グラフの初期化
	attr := map[string]interface{}{"color": "red"}
	g.AddVertex(1, attr)  //"1"という頂点を追加する。"colorはredである"という属性を付与する

頂点に付随しうる属性は問題によって全然違うため、ライブラリ側で吸収するのは無理と判断し、ユーザー側が付与するようにしています。このあたりはNetworkXを参考にしています。

辺の追加

辺は頂点の2つ組です。一応Edgeという構造体を用意していますが、消そうか悩んでいるところです。
それ以外は基本的に頂点と同じです。
辺をグラフに追加するには下記のように書きます。

	g := NewGraph()
	u := 1
	v := 2
	attr := map[string]interface{}{"weight": 10}
	g.AddEdge(u, v, attr) //{1,2}という辺を追加する。"weightが10である"という属性を付与する。

上記のコードでは頂点u,vを事前にグラフに追加することなく辺を追加しています。
この場合は勝手にu,vがグラフに追加されます。

探索

深さ優先探索（以下DFS：Depth First Search）、幅優先探索（以下BFS：Breadth First Search）の2つを実装しています。
探索と書いていますが実際にやっているのは走査(traversal)です。探索順に頂点を列挙しています。
使用例は下記になります。

package main

import (
	"fmt"

	trv "github.com/g0nta/goraph/algorithms/traversal"
	graph "github.com/g0nta/goraph/graph"
)

func main() {
	// 探索するグラフの構築
	g := graph.NewGraph()
	edges := []graph.Edge{
		graph.Edge{From: "A", To: "B", Attributes: nil},
		graph.Edge{From: "A", To: "C", Attributes: nil},
		graph.Edge{From: "B", To: "C", Attributes: nil},
		graph.Edge{From: "B", To: "D", Attributes: nil},
	}
	g.AddEdges(edges)

	//深さ優先探索のインスタンスを生成
	// 第一引数：探索対象のグラフ
	// 第二引数：「訪問済み」を表す属性名
	// 第三引数：探索開始頂点
	dfs, errDfs := trv.NewDFS(g, "isVisitDFS", "A") 

	// グラフが開始頂点を持ってない場合はエラー
	if errDfs != nil {
		fmt.Println("g doesn't have a start vertex.")
	}

	// 探索する
	fmt.Println("DFS sample.")
	traversalSample(dfs)

	// BFSもDFSと同じ
	bfs, errBfs := trv.NewBFS(g, "isVisitBFS", "A")

	if errBfs != nil {
		fmt.Println("g doesn't have a start vertex.")
	}

	fmt.Println("BFS sample.")
	traversalSample(bfs)
}

func traversalSample(traveler trv.Traveler) {
	// 探索アルゴリズムに応じて頂点を列挙する
	for traveler.Next() {
		fmt.Println(traveler.Value())
	}
}

探索アルゴリズムはtravelerというinterfaceを実装しています。これはNextとValueというメソッドを定義しています。
Nextは次の列挙対象があるかどうかをチェックし、あるならtrue、ないならfalseを返します。
Valueは現在の列挙対象を返します。

「探索」という名前について

「なぜ探索アルゴリズムなのに列挙してるんだよ」というツッコミがあるかもしれません。実際にアルゴリズムでDFS,BFSを使う場合では、「ターゲットの頂点があるかどうか」というより「探索順序」が大事な場合が多かったりします。なのでこのライブラリでは列挙するだけの実装にしています。
「じゃあ深さ優先”走査”とかにしたら？」という意見もあるかもしれませんが、BFS,DFSに関しては”走査”とはあまり言わない気がします。。。”探索(Search)”という言葉が市民権を得ているため、別の言葉を使うと混乱を招くと考え、”探索(Search)”のままにしています。

おわりに（感想）

全体を通して

ライブラリを作ると言うこと

ライブラリの作成自体ほぼ初めて難しかったです。一般性を持たせないといけない関係で、「あれが足りない、これも足りない」と考えばかりが先行してしまい、全然手が進みませんでした。

Done is better than perfect

最終的にかなり諦めました。　Done is better than perfectの精神です。
Doneなのかも怪しいくらい機能は乏しいですが、書き始めの段階で「探索アルゴリズムまでできたら一区切りにしよう」と決めていたので個人的にはDoneした気分でいます。

golangに関して

シンプル

言語仕様自体はかなりシンプル（とはいえこのライブラリではgoroutineやdeferとかは使ってないのでそのあたりはよくわかってませんが）だと思いました。
interfaceやポインタ周りで困りそうだなと思うところはありますが、言語仕様上の罠みたいなのは他の言語に比べて圧倒的になさそうだなという印象でした。

シンプル故に

とはいえ、実際にライブラリを実装しているときは正直かなりまどろっこしかったです。シンプル故に書く時に困るなぁという場面が結構あったように思います。まだ触ったばかりなのでほんとはもっと簡単に書けるのかもしれないですが。。。普段はC#を書いているので、そっちに引っ張られてるところが多分にあったのも困った原因だと思います。