graph

graph

グラフ理論のアルゴリズム向けのデータ構造をGolangで実装したものになります。

How to Install

$ go get github.com/cipepser/goGraphAlgo/...

可視化もできるようにしているので、可視化したい場合は以下もインストールしてください。

$ brew install graphviz
$ go get github.com/awalterschulze/gographviz

How to Use

基本的な操作として、以下ができます。

• 無向グラフ/有向グラフ
• 頂点(Vertex)の追加/削除
• 辺(Edge)の追加/削除

具体的な使い方を以下に示します。 いずれもerrorを返すようにしているのて適宜エラーチェックをしてください。

無向グラフの作成

g := graph.NewGraph()

※内部でisDirectedフィールドを持っていますが、ゼロ値がfalseのためデフォルトで無向グラフになります。

有向グラフの作成

g := graph.NewGraph()
g.SetDir(true)

頂点(Vertex)の追加/削除

g.AddVertex(0) // vertex 0を追加
g.AddVertex(1) // vertex 1を追加
g.AddVertex(2) // vertex 2を追加

g.RemoveVertex(2) // vertex 2を削除
g.RemoveVertex(1) // vertex 1を削除

辺(Edge)の追加/削除

AddEdgeの第3引数はedgeの重み(int)になります。

// edgeを追加する前にvertexの追加が必要
g.AddVertex(0)
g.AddVertex(1)

g.AddEdge(0, 1, 3) // 0→1に重み3のedgeを追加

g.RemoveEdge(0, 1) // 0→1のedgeを削除

可視化

g.Visualize()

Example

簡単な有向グラフを作成し、可視化してみます。

package main

import (
	"github.com/cipepser/goGraphAlgo/graph"
)

func main() {

	g := graph.NewGraph()
	g.SetDir(true)

	g.AddVertex(0)
	g.AddVertex(1)
	g.AddVertex(2)
	g.AddVertex(3)

	g.AddEdge(0, 1, 0)
	g.AddEdge(0, 2, 0)
	g.AddEdge(0, 3, 0)
	g.AddEdge(2, 3, 0)

	if err := g.Visualize(); err != nil {
		panic(err)
	}

}

上記をmain.goとして実行(go run main.go)するとgv.dotファイルが生成されます。 これを以下のようにgraphgizでpngにします。

$ go run main.go
$ dot -T png ./gv.dot -o ./gv.png
$ open ./gv.png

References

• Graphviz - Graph Visualization Software
• gographviz
• graph
• graph-go
• SliceTricks

License

MIT