📊
Goでグラフの一筆書きをしてみる
したこと
グラフの一筆書きを求めるアルゴリズムをGolangで書きます。
一筆書きとは、グラフにおいて全ての辺を1度だけ通るような路のことです。一筆書きについては以下の記事を参照してください。
注意点
今回は、あまり計算量などは気にせず、実際に正しい出力が得られることを第一目標に実装しています。かなり無駄があるのでご了承ください。
高速なアルゴリズムが知りたい方は、別の記事をご参考ください。
実装
最終コード
先に完成版を載せておきます。
完成版
main.go
package main
import (
"fmt"
"io"
"os"
)
func main() {
edges := readFile()
G := newAdjacencyList(edges)
p := solve(G)
fmt.Println(p)
}
func solve(G [][]int) []int {
oddNodes := getOddNodes(G)
pathNum := countPath(G)
var p []int
if len(oddNodes) == 1 || len(oddNodes) > 2 {
return p
}
v := -1
if len(oddNodes) == 2 {
// 奇点から奇点へのパスを探して, pに格納する
from := oddNodes[0]
to := oddNodes[1]
p = findPath(G, from, to)
// pをGから削除する
removePath(G, p)
pathNum -= len(p) - 1
}
for pathNum > 0 {
// pから孤立点でない点を探す
for _, n := range p {
if len(G[n]) > 0 {
v = n
break
}
}
// pが空の場合は, Gから任意の孤立点でない点を探す
if len(p) == 0 {
for i := 0; i < len(G); i++ {
if len(G[i]) > 0 {
v = i
break
}
}
}
// vを含むサイクルを見つける
c := findPath(G, v, v)
if len(p) == 0 {
p = c
} else {
idx := 0
for i := 0; i < len(p); i++ {
if p[i] == v {
idx = i
break
}
}
// pのvの部分をcに置き換える
p = append(p[:idx], append(c, p[idx+1:]...)...)
}
// cをGから削除する
removePath(G, c)
pathNum -= len(c) - 1
}
return p
}
func readFile() [][]int {
f, err := os.Open("path/to/input.txt")
if err != nil {
panic(err)
}
defer f.Close()
var numLines [][]int
for {
var from, to int
_, err := fmt.Fscanf(f, "%d,%d\n", &from, &to)
if err == io.EOF {
break
}
numLines = append(numLines, []int{from, to})
}
return numLines
}
func newAdjacencyList(edges [][]int) [][]int {
G := make([][]int, 0)
maxNode := 0
for _, edge := range edges {
from := edge[0]
to := edge[1]
if from > maxNode {
maxNode = from
}
if to > maxNode {
maxNode = to
}
}
for i := 0; i <= maxNode; i++ {
G = append(G, []int{})
}
for _, edge := range edges {
from := edge[0]
to := edge[1]
G[from] = append(G[from], to)
G[to] = append(G[to], from)
}
return G
}
func getOddNodes(G [][]int) []int {
var oddNodes []int
for i, nodes := range G {
if len(nodes)%2 == 1 {
oddNodes = append(oddNodes, i)
}
}
return oddNodes
}
func findPath(G [][]int, from, to int) []int {
var p []int
// 辺を通ったかどうかを記録する
var passed [][]bool
for i := 0; i < len(G); i++ {
passed = append(passed, make([]bool, len(G)))
}
c := from
// fromからtoへのパスを一つ見つける
for {
p = append(p, c)
for _, n := range G[c] {
if !passed[c][n] {
passed[c][n] = true
passed[n][c] = true
c = n
break
}
}
if c == to {
p = append(p, c)
break
}
}
return p
}
func removeEdge(G [][]int, from, to int) {
for i, edge := range G[from] {
if edge == to {
G[from] = append(G[from][:i], G[from][i+1:]...)
break
}
}
for i, edge := range G[to] {
if edge == from {
G[to] = append(G[to][:i], G[to][i+1:]...)
break
}
}
}
func removePath(G [][]int, p []int) {
for i := 0; i < len(p)-1; i++ {
removeEdge(G, p[i], p[i+1])
}
}
func countPath(G [][]int) int {
count := 0
for i := 0; i < len(G); i++ {
count += len(G[i])
}
return count / 2
}
0. グラフを構築する
入力は、辺で結ばれたニ頂点をコンマ区切りで書いたもののリストです。
グラフは隣接リストとして持つことにします。
AtCoderなどでは、入力の1行目に頂点数などがあるのが一般的かと思いますが、少し訳があってこのような形になっています。
また、入力は連結な単純無向グラフであるとします。
入力
func readFile() [][]int {
f, err := os.Open("path/to/input.txt")
if err != nil {
panic(err)
}
defer f.Close()
var numLines [][]int
for {
var from, to int
_, err := fmt.Fscanf(f, "%d,%d\n", &from, &to)
if err == io.EOF {
break
}
numLines = append(numLines, []int{from, to})
}
return numLines
}
func newAdjacencyList(edges [][]int) [][]int {
g := make([][]int, 0)
maxNode := 0
for _, edge := range edges {
from := edge[0]
to := edge[1]
if from > maxNode {
maxNode = from
}
if to > maxNode {
maxNode = to
}
}
for i := 0; i <= maxNode; i++ {
g = append(g, []int{})
}
for _, edge := range edges {
from := edge[0]
to := edge[1]
g[from] = append(g[from], to)
g[to] = append(g[to], from)
}
return g
}
入力の例
0,4
0,1
0,2
0,4
1,3
1,4
2,3
2,4
3,4
1. Eulerグラフ･半Eulerグラフの判定
グラフが一筆書きできるための必要十分条件は、
- グラフがEulerグラフである
- グラフが半Eulerグラフである
のどちらか一方を満たすことです。
それぞれの定義は,
Def
-
G :\Leftrightarrow -
G :\Leftrightarrow
です。(間違ってたらすみません...)
まず、 一筆書きを持つかどうかを調べるために、グラフが(半)Eulerグラフかどうかを調べます。
全ての頂点をチェックして、それぞれの次数を調べるだけです。
奇点の個数のチェック
func getOddNodes(g [][]int) []int {
var oddNodes []int
for i, nodes := range g {
if len(nodes)%2 == 1 {
oddNodes = append(oddNodes, i)
}
}
return oddNodes
}
getOddNodesの戻り値は、奇点(次数が奇数)のリストです。返り値の長さが0ならばEulerグラフ、 2ならば半Eulerグラフ、それ以外ならどちらでもないです。
つまり、返り値の長さが0か2の場合は一筆書きが可能で、それ以外の場合は一筆書きが不可能ということがわかります。
2. 空配列を用意する
空配列pを用意します。
3. (半Eulerグラフの場合)二つの奇点を結ぶパスをp G
二つの奇点を結ぶ任意のパスを探して、グラフから削除します。このとき、どのようなパスを選んでも、グラフは新しいEulerグラフになります。
このアルゴリズムでは、隣接リストをsetで持っておけば、辺の削除を定数時間で行うことができます。しかし、Goはプリミティブ型としてsetを持っていないので、そのままsliceで行っています。
パスの探索
func findPath(G [][]int, from, to int) []int {
var p []int
// 辺を通ったかどうかを記録する
var passed [][]bool
for i := 0; i < len(G); i++ {
passed = append(passed, make([]bool, len(G)))
}
c := from
// fromからtoへのパスを一つ見つける
for {
p = append(p, c)
for _, n := range G[c] {
if !passed[c][n] {
passed[c][n] = true
passed[n][c] = true
c = n
break
}
}
if c == to {
p = append(p, c)
break
}
}
return p
}
パスの削除
func removePath(G [][]int, p []int) {
for i := 0; i < len(p)-1; i++ {
removeEdge(G, p[i], p[i+1])
}
}
func removeEdge(G [][]int, from, to int) {
for i, edge := range G[from] {
if edge == to {
G[from] = append(G[from][:i], G[from][i+1:]...)
break
}
}
for i, edge := range G[to] {
if edge == from {
G[to] = append(G[to][:i], G[to][i+1:]...)
break
}
}
}
4. p v
pから孤立点でない点を一つ選んで、vとします。
pの長さが0のときは、Gから任意の点を一つ選んで、vとします。
vの選択
func solve(G [][]int) []int {
oddNodes := getOddNodes(G)
var p []int
if len(oddNodes) == 1 || len(oddNodes) > 2 {
return p
}
v := -1
if len(oddNodes) == 2 {
// 奇点から奇点へのパスを探して, pに格納する
from := oddNodes[0]
to := oddNodes[1]
p = findPath(G, from, to)
// pをGから削除する
removePath(G, p)
// pから孤立点でない点を探す
for _, n := range p {
if len(G[n]) > 0 {
v = n
break
}
}
}
// 孤立点がない場合, Gから任意の孤立点でない点を選ぶ
if v == -1 {
for i := 0; i < len(G); i++ {
if len(G[i]) > 0 {
v = i
break
}
}
}
return p
}
5. v c G
3.で定義したfindPathを使って求めることができます。
cの探索
c := findPath(G, v, v)
removePath(G, c)
6. p v c
可読性が低いので、あまり良くないかもしれませんが、これで挿入できます。
cの挿入
c := findPaht(G, v, v)
p = append(p[:idx], append(c, p[idx+1:]...)...)
7. 3 ~ 5をG
繰り返し
func solve(G [][]int) {
numPath = countPath(G)
// ...
for numPath > 0 {
// pが空の場合は, Gから任意の孤立点でない点を探す
if len(p) == 0 {
for i := 0; i < len(G); i++ {
if len(G[i]) > 0 {
v = i
break
}
}
}
// vを含むサイクルを見つける
c := findPath(G, v, v)
if len(p) == 0 {
p = c
continue
}
idx := 0
for i := 0; i < len(p); i++ {
if p[i] == v {
idx = i
break
}
}
// pのvの部分をcに置き換える
p = append(p[:idx], append(c, p[idx+1:]...)...)
// cをGから削除する
removePath(G, c)
numPath -= len(c) - 1
}
// ...
}
func countPath(G [][]int) int {
count := 0
for i := 0; i < len(G); i++ {
count += len(G[i])
}
return count / 2
}
入力例
例1
入力例1
0,1
0,3
0,4
1,4
2,3
2,4
3,4
出力例1
[0 1 4 2 3 4 0 3]
例2
少し長いバージョンも試しました
入力例2
0,1
0,2
0,3
0,4
0,5
0,6
0,7
0,8
0,9
0,10
1,2
1,3
1,4
1,5
1,6
1,7
1,9
1,10
2,3
2,4
2,5
2,6
2,7
2,8
2,9
2,10
3,4
3,5
3,6
3,7
3,8
3,9
3,10
4,5
4,6
4,7
4,8
4,9
4,10
5,6
5,7
5,8
5,9
5,10
6,7
6,8
6,9
6,10
7,8
7,9
7,10
8,9
8,10
9,10
出力例2
[1 9 8 10 9 6 7 8 6 10 7 9 4 5 6 4 7 5 8 4 10 5 9 2 3 4 2 5 3 6 2 7 3 8 2 10 3 9 0 10 1 0 2 1 3 0 4 1 5 0 6 1 7 0 8]
例3
出力からもわかる通り、例1と例2はともに半Eulerグラフです。最後に、Eulerグラフの場合も試してみます。
確かに、閉路となっていることがわかります。
0,1
0,2
0,3
0,4
1,2
1,3
1,4
2,3
2,4
3,4
出力例3
[0 3 2 4 3 1 4 0 1 2 0 1 2 0]
まとめ
一応求めることはできましたが、完全には理解しきれていないです。いくつかの事実を認めたので、証明を与えられるようにします。
実装もかなり無駄が多いので、改善したいです。
Discussion