Open20

Golangでグラフ理論やってみる

数学のグラフ理論の分野における頂点(ちょうてん、英: vertex)あるいは節点(せってん、英: node)とは、グラフを形成する基本的な構成単位である。無向グラフは頂点の集合と辺(edge、向き付けのされていない頂点のペア)の集合で構成され、有向グラフは頂点の集合と弧(arc、向き付けのされている頂点のペア)の集合で構成される。グラフを図示する際、頂点は通常ラベル付けのされた円で表され、辺は各頂点から別の頂点へと伸びる直線あるいは矢で表される。

vertexは頂点
edgeは頂点のペアなので辺

無向グラフやってみる

https://play.golang.org/p/N9QbASf6DEB

無向グラフの場合それぞれnodeのペアを用意しないといけない
例えば、node3とnode4の移動について考えるなら、node4とnode3のペアも必要

graph[3][4] = 1
graph[4][3] = 1

todo ペアを作る部分を関数化する

無向グラフになってないっぽいので、現在修正中

割といい感じに無向グラフを表現できたんじゃないかな
なんかイメージしやすいように駅のダイアグラム的なノリで地名とか適当に入れてみた。

https://play.golang.org/p/UreybFJ9w5p

サンプルグラフの イメージはこんな感じ

	_________5,6
	|    |   |
	1---2    |
	| X |    |
	3---4----|
	|________|
func (g *glink) createVertexesPair(p []place) {
	placeSetter := placeSet{}
	for i := range p {
		for j := i; j < len(p); j++ {
			if j != i {
				placeSetter.vertex1 = p[i]
				placeSetter.vertex2 = p[j]
				g.placeSets = append(g.placeSets, placeSetter)
			}
		}
	}
}

func (g *glink) createEdge(p1 []place, p2 []place) {
	placeSetter := placeSet{}
	for i := range p1 {
		for j := range p2 {
			placeSetter.vertex1 = p1[i]
			placeSetter.vertex2 = p2[j]
			g.placeSets = append(g.placeSets, placeSetter)

		}
	}
}

使い方

package main

import (
	"fmt"
	graph "github.com/Iovesophy/graph-go"
)

func main() {
	samplePlace := []graph.Node{
		graph.Node{ID: 1, Element: "place-A"},
		graph.Node{ID: 2, Element: "place-B"},
		graph.Node{ID: 3, Element: "place-C"},
		graph.Node{ID: 4, Element: "place-D"},
	}
	sampleStation := []graph.Node{
		graph.Node{ID: 5, Element: "station-A"},
		graph.Node{ID: 6, Element: "station-B"},
	}
	g := &graph.Glink{
		NodeData: samplePlace,
		BaseData: sampleStation,
	}

	fmt.Println(g.CreateVertexesPair())
	fmt.Println(g.CreateEdge())
}

上記はv1.0.0時点での書き方

次はグラフオブジェクトの変換をライブラリに組み込む予定
例えば無向グラフから有向グラフに変更など
後、自由にNodeの要素数を変更できてフィールドの型定義をできるようにする

IDはint
Elementはstring型しか使えなかったところをinterface型に置き換え全ての型に対応できるようにした
有向グラフ変換を行うにあたって、区別できるようにインターフェース名を修正した

https://play.golang.org/p/XDfxWXtNN_m

今頂点ペアぐらいしか作ることできない笑
LinkedListを書いてみたので、もうちょっと工夫して組み込もうと思う。

https://play.golang.org/p/Vkiv_fdc3cC

これで頂点の編集を行うようにすればいいのかな。
pythonのnetworkxをしばらく読んでみようと思う。

ログインするとコメントできます