/
visit.go
47 lines (42 loc) · 1.14 KB
/
visit.go
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
// Copyright 2019 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
package graphalg
import (
"github.com/aclements/go-moremath/graph"
)
// Euler visits a graph using an Euler tour.
//
// For a tree, the Euler tour is well-defined and unique (given an
// ordering of the children of a node). For a general graph, this uses
// the tree formed by the pre-order traversal of the graph.
type Euler struct {
// Enter is called when a node a first visited. It may be nil.
Enter func(n int)
// Exit is called when all of the children of n have been
// visited. It may be nil.
//
// Calls to Enter and Exit are always paired in nested order.
Exit func(n int)
}
// Visit performs a Euler tour over g starting at root and invokes the
// callbacks on e.
func (e Euler) Visit(g graph.Graph, root int) {
visited := NewNodeMarks()
var visit func(n int)
visit = func(n int) {
if e.Enter != nil {
e.Enter(n)
}
visited.Mark(n)
for _, succ := range g.Out(n) {
if !visited.Test(succ) {
visit(succ)
}
}
if e.Exit != nil {
e.Exit(n)
}
}
visit(root)
}