Golangでgraphパッケージを書いた

グラフ理論のアルゴリズムで遊ぶための前準備として、graphパッケージを自作してみました。
基本的な操作として、以下ができます。

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

How to Install

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

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

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

How to Use

具体的な使い方を以下に示します。いずれも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

f:id:cipepser:20180127175606p:plain

最後に

今後はこのパッケージを使って、グラフ理論のアルゴリズムを実装していく予定です。 repoはこちら

逆さまにした