graph

README

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

Documentation

Index

• type Edge
• type Graph
  • func NewGraph() *Graph
  • func (g *Graph) AddEdge(from, to Vertex, weight int) error
  • func (g *Graph) AddVertex(v Vertex) error
  • func (g *Graph) ExistsEdge(from, to Vertex) bool
  • func (g *Graph) ExistsVertex(v Vertex) bool
  • func (g *Graph) GetEdges() []Edge
  • func (g *Graph) GetNeighbours(v Vertex) []Vertex
  • func (g *Graph) GetVertices() []Vertex
  • func (g *Graph) GetWeight(from, to Vertex) (int, error)
  • func (g *Graph) RemoveEdge(from, to Vertex) error
  • func (g *Graph) RemoveVertex(v Vertex) error
  • func (g *Graph) SetDir(dir bool)
  • func (g *Graph) SetWeight(from, to Vertex, weight int) error
  • func (g *Graph) Visualize() error
• type VerSet
  • func NewVerSet() VerSet
  • func (s VerSet) Add(v Vertex) error
  • func (s VerSet) Cardinality() int
  • func (s VerSet) Contains(v Vertex) bool
  • func (s VerSet) Difference(other VerSet) VerSet
  • func (s VerSet) Equal(other VerSet) bool
  • func (s VerSet) Intersect(other VerSet) VerSet
  • func (s VerSet) Remove(v Vertex) error
  • func (s VerSet) Union(other VerSet) VerSet
• type Vertex

Types

type Edge

type Edge struct {
	From Vertex
	To   Vertex
}

Edge represents a edge connects a vertex with another of the graph

type Graph

type Graph struct {
	Vertices      map[Vertex]int
	VerticesCount int
	Edges         map[Edge]int
	EdgesCount    int
	IsDirected    bool
	Neighbours    map[Vertex][]Vertex
}

Graph represents a shape of whole graph To use constructer in my program, the first character of the Identifier's name must be a Unicode upper case

func NewGraph

func NewGraph() *Graph

NewGraph constructs a new graph

func (*Graph) AddEdge

func (g *Graph) AddEdge(from, to Vertex, weight int) error

AddEdge adds an edge difined by `from` and `to` to the graph `g`. If a graph has already have the edge, it returns an error. The graph g must have the vertices `from` and `to`, if `g` don't have `from` or `to`, AddEdge returns an error. The vertices `from` and `to` must be different.

func (*Graph) AddVertex

func (g *Graph) AddVertex(v Vertex) error

AddVertex adds a vertex `v` to the graph `g`. If a graph has already have the vertex `v`, it returns an error

func (*Graph) ExistsEdge

func (g *Graph) ExistsEdge(from, to Vertex) bool

ExistsEdge chech whether the edge difined by `from` and `to` exists in the graph `g`, or not

func (*Graph) ExistsVertex

func (g *Graph) ExistsVertex(v Vertex) bool

ExistsVertex chech whether the vertex `v` exists in the graph `g`, or not

func (*Graph) GetEdges

func (g *Graph) GetEdges() []Edge

GetEdges returns slice of Edges

func (*Graph) GetNeighbours

func (g *Graph) GetNeighbours(v Vertex) []Vertex

GetNeighbours returns the neighbours of the Vertex `v`.

func (*Graph) GetVertices

func (g *Graph) GetVertices() []Vertex

GetVertices returns slice of Vertices

func (*Graph) GetWeight

func (g *Graph) GetWeight(from, to Vertex) (int, error)

GetWeight returns a weight of the edge difined by `from` and `to`. The vertices `from` and `to` must be different. The edge must exist.

func (*Graph) RemoveEdge

func (g *Graph) RemoveEdge(from, to Vertex) error

RemoveEdge removes an edge difined by `from` and `to`, form the graph `g`. The vertices `from` and `to` must be different.

func (*Graph) RemoveVertex

func (g *Graph) RemoveVertex(v Vertex) error

RemoveVertex remove a vertex form the graph `g`.

func (*Graph) SetDir

func (g *Graph) SetDir(dir bool)

SetDir sets `isDirected` to true or false by `dir`

func (*Graph) SetWeight

func (g *Graph) SetWeight(from, to Vertex, weight int) error

SetWeight sets a weight to the edge difined by `from` and `to`. The vertices `from` and `to` must be different. The edge must exist.

func (*Graph) Visualize

func (g *Graph) Visualize() error

Visualize create `gv.png` in your directory, which is generated by the graph `g`.

type VerSet

type VerSet map[Vertex]struct{}

VerSet represents a set of vertices.

func NewVerSet

func NewVerSet() VerSet

NewVerSet constructs a new VerSet.

func (VerSet) Add

func (s VerSet) Add(v Vertex) error

Add adds an `v` to `s`.

func (VerSet) Cardinality

func (s VerSet) Cardinality() int

Cardinality returns the number of elements in the Set.

func (VerSet) Contains

func (s VerSet) Contains(v Vertex) bool

Contains checks whether an `v` exists in `s` or not.

func (VerSet) Difference

func (s VerSet) Difference(other VerSet) VerSet

Difference returns the difference of `s` and `other`. Difference have a referential transparency.

func (VerSet) Equal

func (s VerSet) Equal(other VerSet) bool

Equal checks whether `other` is same as `s` or not.

func (VerSet) Intersect

func (s VerSet) Intersect(other VerSet) VerSet

Intersect returns the Intersection of `s` and `other`. Intersect have a referential transparency.

func (VerSet) Remove

func (s VerSet) Remove(v Vertex) error

Remove removes an `v` from `s`.

func (VerSet) Union

func (s VerSet) Union(other VerSet) VerSet

Union returns the Union of `s` and `other` Union have a referential transparency.

type Vertex

type Vertex uint

Vertex represents a vertex of the graph