Zenn
Open20

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

Kazuya YudaKazuya Yuda

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

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

無向グラフやってみる

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

Kazuya YudaKazuya Yuda

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

graph[3][4] = 1
graph[4][3] = 1
Kazuya YudaKazuya Yuda

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

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

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

	_________5,6
	|    |   |
	1---2    |
	| X |    |
	3---4----|
	|________|
Kazuya YudaKazuya Yuda
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)

		}
	}
}
Kazuya YudaKazuya Yuda

使い方

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())
}
Kazuya YudaKazuya Yuda

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