読書: 関節点を求める

アルゴリズム設計マニュアル(S.S. スキーナ)を読み返していて細かい誤植があった。 場所は日本語版 アルゴリズム設計マニュアル 上(S.S. スキーナ) p.196, l.1 でサンプルコード内の条件分岐。 誤植な気がしたけど自信が持てなかったので調べたり実装したのでメモを残す。

問題: 関節点

無向グラフ \( G(V,E) \) において\( v /in V \) となる頂点\( v \) で\( G-v \) の連結成分数が\( G \) より大きくなるものを切断点(cut vertex)や関節点(articulation point)と呼ぶ。

アルゴリズム: DFS

著書ではDFSで解いていた。同じくDFSで求められるLowLinkというノード\( v \) の属性を計算すると綺麗に解ける。

無向グラフはDFSを用いて各辺を木辺(tree edge)と逆辺(back edge)に分類できる。 このように作られる木を深さ優先探索木(DFS tree)と呼ぶ。 (逆辺は閉路があることに対応する)

関節点は次の3つのいずれかに該当する。

関節点の候補 定義
子を2つ以上もつDFS treeの根 DFS treeが2以上の子ノードを持つ場合にルートノードは関節点
ブリッジの切断点 \( v \) の子孫から最大1つの逆辺で戻れる点が\( v \) である時の\( v \) とその親(\( parent(v) \) )は関節点
親の切断点 要定義 \( v \) の子孫から最大1つの逆辺で戻れる点が\( v \) の親である時その親(\( parent(v) \) )は関節点

本でみつけた誤植はブリッジの切断点を判定するコードの中にあった。 ブリッジの切断点の親を関節点として登録するコードはルートノードの場合は関節点となるルートノードの条件(子を2つ持つ)を満たすか確認する必要がある。 そうでなければ、ブリッジの端点から伸びるエッジがないため連結成分が増えない。

この検証はDFS treeのルートノードの検証で行う。 そのため関節点の列挙だけを目的にする場合、ブリッジの親側の端点がルートノードの場合は除外して構わない。

ブリッジの切断点と親の切断点は Lowlinkを用いた判定では判定基準が2つに減るため、少しコードが単純化されるように思えた。

まず2つの値を定義する。

定義
\( ord(v) \) DFS tree構築時のアクセス順序(訪問時刻)
\( low(v) \) \( v \) から高々1回の逆辺でたどり着けるノード(\( u \) )の最小訪問時刻(\( \min(ord(u)) \) )

他のブログとかだと関数じゃなくて下付きで記載しているところが多かった。

関節点の候補 定義
子を2つ以上もつDFS treeの根 次数(degree,valency)2以上のDFS treeのルートノード
ブリッジの切断点 ルートノードではない次を満たすノード\( u \) 、ある\( u \) の子ノード\( v \) が存在し\( ord(u) \le low(v) \)

候補が少ないので書くのが楽だ。基準に不等号が入りブリッジの切断点の基準が広い。

実装(Go)

それぞれ実装してみる。基礎となるグラフは隣接リストで表現する。 汚いコードになった。久しぶりにプログラムを書いたうえ一つ目は書き捨てなのに著書に似せて無名関数を使うように書いてしまった。 仕方ない。

著書に近いDFS

著書と近づけるために無名関数を渡す形で実装したc.lateが著書のprocess_vertex_late(int v)に対応してる。 this… とコメントしてるところが著書で漏れている条件。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
	c.late = func(c *context, u int) {
		isRoot := c.parent[u] < 1
		if isRoot {
			if treeOutDegree[u] > 1 {
				articulations[u] = struct{}{}
			}
		} else {
			if reachable[u] == c.parent[u] {
				// parent
				if c.parent[c.parent[u]] > 0 { // parent isn't root
					articulations[c.parent[u]] = struct{}{}
				}
			} else if reachable[u] == u {
				// bridge
				// this conditional branch is required!!
				if c.parent[c.parent[u]] > 0 { // parent isn't root
					articulations[c.parent[u]] = struct{}{}
				}
				if treeOutDegree[u] > 0 { // u have children
					articulations[u] = struct{}{}
				}
			}
		}
		uTime := c.entryTime[reachable[u]]
		pTime := c.entryTime[reachable[c.parent[u]]]
		if uTime < pTime {
			reachable[c.parent[u]] = reachable[u]
		}
	}

Lowlinkを明示的に意識したDFS

lowlink 版はこんな感じになった。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
package main

import (
	"fmt"
)

func main() {
	g := loadGraph()
	for a := range findArticulation(g) {
		fmt.Printf("articulation: %d\n", a)
	}
}

type none struct{}

var mark none = struct{}{}

func findArticulation(g *graph) (articulations map[int]none) {
	// write code as dfs
	s := newDfsState(g)
	s.findArticulation(0, 1, 0)
	return s.articulations
}

type dfsState struct {
	// lowlink
	ord map[int]int
	low map[int]int
	// result
	articulations map[int]none

	// standard dfs
	g          *graph
	discovered map[int]none
	finished   map[int]none
	parent     map[int]int
	childNum   map[int]int
}

func newDfsState(g *graph) *dfsState {
	return &dfsState{
		g:          g,
		ord:        make(map[int]int),
		low:        make(map[int]int),
		discovered: make(map[int]none),
		finished:   make(map[int]none),
		parent:     make(map[int]int),
		childNum:   make(map[int]int),

		articulations: make(map[int]none),
	}
}

func (s *dfsState) findArticulation(p, u int, ord int) int {
	ord++
	s.parent[u] = p
	s.discovered[u] = mark
	s.ord[u] = ord
	s.low[u] = ord
	for _, v := range s.g.edges[u] {
		if v == p {
			continue
		}
		switch s.getEdgeType(u, v) {
		case tree:
			s.childNum[u]++
			ord = s.findArticulation(u, v, ord)
		default:
			// back
			if s.ord[v] < s.low[u] {
				s.low[u] = s.ord[v]
			}
		}
	}
	// late phase
	// set parent's low
	uLow := s.low[u]
	pLow := s.low[s.parent[u]]
	if uLow < pLow {
		s.low[s.parent[u]] = uLow
	}
	// judge articulation
	if isRoot := s.parent[u] < 1; isRoot {
		if s.childNum[u] > 1 {
			s.articulations[u] = mark
		}
	} else if s.low[u] >= s.ord[u] && s.childNum[u] > 1 {
		s.articulations[u] = mark
	}
	s.finished[u] = mark
	return ord + 1
}

type edgeType int

const (
	tree edgeType = 0 + iota
	back
)

func (s dfsState) getEdgeType(u, v int) edgeType {
	if _, ok := s.discovered[v]; !ok {
		return tree
	}
	return back
}

func loadGraph() *graph {
	var n, m int
	fmt.Scan(&n, &m)
	g := newGraph(n)
	var u, v int
	for i := 0; i < m; i++ {
		fmt.Scan(&u, &v)
		g.addEdge(u, v)
	}
	return g
}

type graph struct {
	num   int
	edges map[int][]int
}

func newGraph(num int) *graph {
	return &graph{
		num:   num,
		edges: make(map[int][]int, num),
	}
}

func (g *graph) addEdge(u, v int) {
	g.edges[u] = append(g.edges[u], v)
	g.edges[v] = append(g.edges[v], u)
}
comments powered by Disqus